Geodesic
Multigenerative grammar systems and matrix grammars
Kybernetika, Tome 46 (2010) no. 1, pp. 68-82
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

Multigenerative grammar systems are based on cooperating context-free grammatical components that simultaneously generate their strings in a rule-controlled or nonterminal-controlled rewriting way, and after this simultaneous generation is completed, all the generated terminal strings are combined together by some common string operations, such as concatenation, and placed into the generated languages of these systems. The present paper proves that these systems are equivalent with the matrix grammars. In addition, we demonstrate that these systems with any number of grammatical components can be transformed to equivalent two-component versions of these systems. The paper points out that if these systems work in the leftmost rewriting way, they are more powerful than the systems working in a general way.
Multigenerative grammar systems are based on cooperating context-free grammatical components that simultaneously generate their strings in a rule-controlled or nonterminal-controlled rewriting way, and after this simultaneous generation is completed, all the generated terminal strings are combined together by some common string operations, such as concatenation, and placed into the generated languages of these systems. The present paper proves that these systems are equivalent with the matrix grammars. In addition, we demonstrate that these systems with any number of grammatical components can be transformed to equivalent two-component versions of these systems. The paper points out that if these systems work in the leftmost rewriting way, they are more powerful than the systems working in a general way.
Classification : 68Q05, 68Q45
Keywords: multigenerative grammar systems; simultaneously controlled derivations; matrix grammars 
@article{KYB_2010_46_1_a4,
     author = {Luk\'a\v{s}, Roman and Meduna, Alexander},
     title = {Multigenerative grammar systems and matrix grammars},
     journal = {Kybernetika},
     pages = {68--82},
     year = {2010},
     volume = {46},
     number = {1},
     mrnumber = {2666895},
     zbl = {1209.68289},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2010_46_1_a4/}
}
TY  - JOUR
AU  - Lukáš, Roman
AU  - Meduna, Alexander
TI  - Multigenerative grammar systems and matrix grammars
JO  - Kybernetika
PY  - 2010
SP  - 68
EP  - 82
VL  - 46
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/KYB_2010_46_1_a4/
LA  - en
ID  - KYB_2010_46_1_a4
ER  - 
%0 Journal Article
%A Lukáš, Roman
%A Meduna, Alexander
%T Multigenerative grammar systems and matrix grammars
%J Kybernetika
%D 2010
%P 68-82
%V 46
%N 1
%U http://geodesic.mathdoc.fr/item/KYB_2010_46_1_a4/
%G en
%F KYB_2010_46_1_a4
Lukáš, Roman; Meduna, Alexander. Multigenerative grammar systems and matrix grammars. Kybernetika, Tome 46 (2010) no. 1, pp. 68-82. http://geodesic.mathdoc.fr/item/KYB_2010_46_1_a4/

[1] E. Csuhaj-Varju, J. Dassow, J. Kelemen, and Ch. Păun: Grammar Systems: A Grammatical Approach to Distribution and Cooperation. Gordon and Breach, London 1994. | MR

[2] E. Csuhaj-Varju and G. Vaszil: On context-free parallel communicating grammar systems: Synchronization, communication, and normal forms. Theoret. Comput. Sci. 255 (2001), 511–538. | MR

[3] E. Csuhaj-Varju and G. Vaszil: Parallel communicating grammar systems with incomplete information communication. Develop. Language Theory (2001), 381–392. | MR

[4] J. Dassow: On cooperating distributed grammar systems with competence based start and stop conditions. Fund. Inform. 76 (2007), 293–304. | MR | Zbl

[5] J. Dassow and G. Păun: Regulated Rewriting in Formal Language Theory. Springer-Verlag, New York 1989. | MR

[6] J. Dassow, G. Păun, and G. Rozenberg: Grammar systems. In: Handbook of Formal Languages (G. Rozenberg and A. Salomaa, eds.), Springer, Berlin 1997. | MR

[7] J. Dassow, G. Păun, and A. Salomaa: Grammars with controlled derivations. In: Handbook of Formal Languages (G. Rozenberg and A. Salomaa, eds.), Springer, Berlin (1997). | MR

[8] H. Fernau: Parallel communicating grammar systems with terminal transmission. Acta Inform. 37 (2001), 511–540. | MR | Zbl

[9] H. Fernau and M. Holzer: Graph-controlled cooperating distributed grammar systems with singleton components. In: Proc. Third Internat. Workshop on Descriptional Complexity of Automata, Grammars, and Related Structures, Vienna 2001, pp. 79–90. | MR

[10] J. Gaso and M. Nehez: Stochastic cooperative distributed grammar systems and random graphs. Acta Inform. 39 (2003), 119–140. | MR

[11] M. A. Harrison: Introduction to Formal Language Theory. Addison-Wesley, London 1978. | MR | Zbl

[12] A. Meduna: Automata and Languages: Theory and Applications. Springer, London 2000. | MR | Zbl

[13] A. Meduna: Two-way metalinear PC grammar systems and their descriptional complexity. Acta Cybernet. 16 (2003), 126–137. | MR | Zbl

[14] A. Meduna and R. Lukas: Multigenerative grammar systems. Schedae Inform. 15 (2006), 175–188.

[15] G. Păun, A. Salomaa, and S. Vicolov: On the generative capacity of parallel communicating grammar systems. Internat. J. Comput. Math. 45 (1992), 45–59.

[16] G. Rozenberg and A. Salomaa, eds.: Handbook of Formal Languages. Springer, Berlin 1997.

[17] A. Salomaa: Formal Languages. Academic Press, New York 1973. | MR | Zbl

[18] G. Vaszil: On simulating non-returning PC grammar systems with returning systems. Theoret. Comput. Sci. 209 (1998), 1–2, 319–329. | MR | Zbl