On Descriptional Complexity of Partially Parallel Grammars

• Autorzy: Masopust T. , Meduna A.
• Języki publikacji: EN

Abstrakty

EN

This paper presents some new results concerning the descriptional complexity of partially parallel grammars. Specifically, it proves that every recursively enumerable language is generated (i) by a four-nonterminal scattered context grammar with no more than four non-context-free productions, (ii) by a two-nonterminal multisequential grammar with no more than two selectors, or (iii) by a three-nonterminalmulticontinuous grammar with no more than two selectors.

Słowa kluczowe

EN

formal languages; scattered context grammars; multisequential grammars; multicontinuous grammars; descriptional complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 87, nr 3-4
• Strony: 407--415
• Opis fizyczny: bibliogr. 14 poz.

Twórcy

autor

Masopust T.

autor

Meduna A.

• Faculty of Information Technology, Brno University of Technology, Boˇzetˇechova 2, Brno 61266, Czech Republic,

Bibliografia

• [1] Dassow, J., Păun, G.: Regulated Rewriting in Formal Language Theory, Springer-Verlag, Berlin, 1989.
• [2] Geffert, V.: Context-Free-Like Forms for the Phrase-Structure Grammars, MFCS (M. Chytil, L. Janiga, V. Koubek, Eds.), 324, Springer, 1988.
• [3] Geffert, V., Pighizzini, G., Eds.: Proceedings of the 9th InternationalWorkshop on Descriptional Complexity of Formal Systems, DCFS 2007, High Tatras, Slovakia, July 20 - 22, 2007.
• [4] Greibach, S., Hopcroft, J.: Scattered Context Grammars, Journal of Computer and System Sciences, 3, 1969, 233-247.
• [5] Gruska, J.: On a Classification of Context-Free Languages, Kybernetika, 13, 1967, 22-29.
• [6] Gruska, J.: The Descriptional Complexity of Context-Free Languages, Proceedings of the 2nd MFCS Conference, 1973.
• [7] Kleijn, H. C. M., Rozenberg, G.: Multi Grammars, International Journal of Computer Mathematics, 12, 1983, 177-201.
• [8] Masopust, T.: Formal Models: Regulation and Reduction, Ph.D. Thesis, Faculty of Information Technology, Brno, 2007.
• [9] Meduna, A.: Six-NonterminalMulti-Sequential Grammars Characterize the Family of Recursively Enumerable Languages, International Journal of Computer Mathematics, 65, 1997, 179-189.
• [10] Meduna, A.: Descriptional Complexity of Multi-Continuous Grammars, Acta Cybernetica, 13, 1998, 375-384.
• [11] Meduna, A.: Generative Power of Three-Nonterminal Scattered Context Grammars, Theoretical Computer Science, 246, 2000, 279-284.
• [12] Meduna, A.: Descriptional Complexity of Scattered Rewriting and Multirewriting: An Overview, Journal of Automata, Languages and Combinatorics, 7, 2002, 571-577.
• [13] Salomaa, A.: Formal Languages, Academic Press, New York, 1973.
• [14] Vaszil, G.: On the Descriptional Complexity of Some Rewriting Mechanisms Regulated by Context Conditions, Theoretical Computer Science, 330, 2005, 361-373.