Bounded Number of Parallel Productions in Scattered Context Grammars with Three Nonterminals

• Autorzy: Masopust T.
• Języki publikacji: EN

Abstrakty

EN

Scattered context grammars with three nonterminals are known to be computationally complete. So far, however, it was an open problem whether the number of parallel productions can be bounded along with three nonterminals. In this paper, we prove that every recursively enumerable language is generated by a scattered context grammar with three nonterminals and five parallel productions, each of which simultaneously rewrites no more than nine nonterminals.

Słowa kluczowe

EN

scattered context grammars; parallel productions; descriptional complexity; generative power

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 99, nr 4
• Strony: 473--480
• Opis fizyczny: Bibliogr. 16 poz.

Twórcy

autor

Masopust T.

• Institute of Mathematics, Czech Academy of Sciences Zizkova 22, 616 62 Brno, Czech Republic,

Bibliografia

• [1] Fernau, H.: Scattered Context Grammars with Regulation, Ann. Univ. Bucharest, Math.-Informatics Series, 45(1), 1996, 41-49.
• [2] Geffert, V.: Context-Free-Like Forms for the Phrase-Structure Grammars, MFCS (M. Chytil, L. Janiga, V. Koubek, Eds.), LNCS 324, Springer, 1988.
• [3] Gonczarowski, J.,Warmuth,M. K.: Scattered Versus Context-Sensitive Rewriting, Acta Inform., 27(1), 1989, 81-95.
• [4] Greibach, S., Hopcroft, J.: Scattered Context Grammars, J. Comput. System Sci., 3(3), 1969, 233-247.
• [5] Latteux, M., Turakainen, P.: On characterizations of recursively enumerable languages, Acta Inform., 28(2), 1990, 179-186.
• [6] Masopust, T.: Formal Models: Regulation and Reduction, Ph.D. Thesis, Brno University of Technology, 2007, http://www.fit.vutbr.cz/research/view pub.php.en?id=8553.
• [7] Masopust, T.: On the Descriptional Complexity of Scattered Context Grammars, Theoret. Comput. Sci., 410(1), 2009, 108-112.
• [8] Masopust, T., Meduna, A.: Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement, DCFS, Otto-von-Guericke-Universit¨at,Magdeburg, Germany, 2009, Electronic Proceedings in Theoretical Computer Science, 3, doi:10.4204/EPTCS.3.17.
• [9] Masopust, T., Techet, J.: Leftmost Derivations of Propagating Scattered Context Grammars: A New Proof, Discrete Math. Theor. Comput. Sci., 10(2), 2008, 39-46.
• [10] Meduna, A.: Generative Power of Three-Nonterminal Scattered Context Grammars, Theoret. Comput. Sci., 246(1-2), 2000, 279-284.
• [11] Meduna, A.: Terminating left-hand sides of scattered context productions, Theoret. Comput. Sci., 237(1-2), 2000, 423-427.
• [12] Meduna, A., Techet, J.: Scattered Context Grammars and Their Applications, Witpress, 2010, To appear.
• [13] Milgram, D., Rosenfeld, A.: A Note on Scattered Context Grammars, Inform. Process. Lett., 1(2), 1971, 47-50.
• [14] Salomaa, A.: Formal languages, Academic Press, New York, 1973.
• [15] Vaszil, G.: On the descriptional complexity of some rewriting mechanisms regulated by context conditions, Theoret. Comput. Sci., 330(2), 2005, 361-373.
• [16] Virkkunen, V.: On Scattered Context Grammars, Acta Univ. Oulu. Ser. A Sci. Rerum Natur., 6, 1973, 75-82.