Multigenerative grammar systems and matrix grammars

Roman Lukáš; Alexander Meduna

Kybernetika (2010)

  • Volume: 46, Issue: 1, page 68-82
  • ISSN: 0023-5954

Abstract

top
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.

How to cite

top

Lukáš, Roman, and Meduna, Alexander. "Multigenerative grammar systems and matrix grammars." Kybernetika 46.1 (2010): 68-82. <http://eudml.org/doc/37712>.

@article{Lukáš2010,
abstract = {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.},
author = {Lukáš, Roman, Meduna, Alexander},
journal = {Kybernetika},
keywords = {multigenerative grammar systems; simultaneously controlled derivations; matrix grammars; multigenerative grammar systems; simultaneously controlled derivations; matrix grammars},
language = {eng},
number = {1},
pages = {68-82},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Multigenerative grammar systems and matrix grammars},
url = {http://eudml.org/doc/37712},
volume = {46},
year = {2010},
}

TY - JOUR
AU - Lukáš, Roman
AU - Meduna, Alexander
TI - Multigenerative grammar systems and matrix grammars
JO - Kybernetika
PY - 2010
PB - Institute of Information Theory and Automation AS CR
VL - 46
IS - 1
SP - 68
EP - 82
AB - 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.
LA - eng
KW - multigenerative grammar systems; simultaneously controlled derivations; matrix grammars; multigenerative grammar systems; simultaneously controlled derivations; matrix grammars
UR - http://eudml.org/doc/37712
ER -

References

top
  1. Grammar Systems: A Grammatical Approach to Distribution and Cooperation, Gordon and Breach, London 1994. MR1475215
  2. On context-free parallel communicating grammar systems: Synchronization, communication, and normal forms, Theoret. Comput. Sci. 255 (2001), 511–538. MR1819088
  3. Parallel communicating grammar systems with incomplete information communication, Develop. Language Theory (2001), 381–392. MR1961495
  4. On cooperating distributed grammar systems with competence based start and stop conditions, Fund. Inform. 76 (2007), 293–304. Zbl1112.68074MR2311441
  5. Regulated Rewriting in Formal Language Theory, Springer-Verlag, New York 1989. MR1067543
  6. Grammar systems, In: Handbook of Formal Languages (G. Rozenberg and A. Salomaa, eds.), Springer, Berlin 1997. MR1470009
  7. Grammars with controlled derivations, In: Handbook of Formal Languages (G. Rozenberg and A. Salomaa, eds.), Springer, Berlin (1997). MR1470008
  8. Parallel communicating grammar systems with terminal transmission, Acta Inform. 37 (2001), 511–540. Zbl0977.68050MR1824842
  9. 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. MR1990453
  10. Stochastic cooperative distributed grammar systems and random graphs, Acta Inform. 39 (2003), 119–140. MR1963124
  11. Introduction to Formal Language Theory, Addison-Wesley, London 1978. Zbl0411.68058MR0526397
  12. Automata and Languages: Theory and Applications, Springer, London 2000. Zbl0951.68056MR1778364
  13. Two-way metalinear PC grammar systems and their descriptional complexity, Acta Cybernet. 16 (2003), 126–137. Zbl1060.68055MR2071407
  14. Multigenerative grammar systems, Schedae Inform. 15 (2006), 175–188. 
  15. On the generative capacity of parallel communicating grammar systems, Internat. J. Comput. Math. 45 (1992), 45–59. 
  16. Handbook of Formal Languages, Springer, Berlin 1997. 
  17. Formal Languages, Academic Press, New York 1973. Zbl0895.00028MR0438755
  18. On simulating non-returning PC grammar systems with returning systems, Theoret. Comput. Sci. 209 (1998), 1–2, 319–329. Zbl0915.68106MR1647546

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.