×

Left-forbidding cooperating distributed grammar systems. (English) Zbl 1207.68174

Summary: A left-forbidding grammar, introduced in this paper, is a context-free grammar, where a set of nonterminal symbols is attached to each context-free production. Such a production can rewrite a nonterminal provided that no symbol from the attached set occurs to the left of the rewritten nonterminal in the current sentential form. The present paper discusses cooperating distributed grammar systems with left-forbidding grammars as components and gives some new characterizations of language families of the Chomsky hierarchy. In addition, it also proves that twelve nonterminals are enough for cooperating distributed grammar systems working in the terminal derivation mode with two left-forbidding components (including erasing productions) to characterize the family of recursively enumerable languages.

MSC:

68Q42 Grammars and rewriting systems
68M14 Distributed systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Csuhaj-Varjú, E.; Dassow, J., On cooperating/distributed grammar systems, Journal of Information Processing and Cybernetics (EIK), 26, 1-2, 49-63 (1990) · Zbl 0693.68041
[2] Csuhaj-Varjú, E.; Dassow, J.; Kelemen, J.; Păun, G., (Grammar Systems: A Grammatical Approach to Distribution and Cooperation. Grammar Systems: A Grammatical Approach to Distribution and Cooperation, Topics in Computer Mathematics, vol. 5 (1994), Gordon and Breach Science Publishers: Gordon and Breach Science Publishers Yverdon) · Zbl 0925.68286
[3] Dassow, J.; Păun, G.; Rozenberg, G., Grammar systems, (Handbook of Formal Languages, Vol. 2 (1997), Springer: Springer Berlin), 155-213
[4] A.P.J. van der Walt, Random context languages, in: IFIP Congress, vol. 1, 1971, pp. 66-68.; A.P.J. van der Walt, Random context languages, in: IFIP Congress, vol. 1, 1971, pp. 66-68.
[5] van der Walt, A. P.J.; Ewert, S., A shrinking lemma for random forbidding context languages, Theoretical Computer Science, 237, 1-2, 149-158 (2000) · Zbl 0939.68057
[6] Ewert, S.; van der Walt, A. P.J., A pumping lemma for random permitting context languages, Theoretical Computer Science, 270, 1-2, 959-967 (2002) · Zbl 0988.68099
[7] Masopust, T., On the terminating derivation mode in cooperating distributed grammar systems with forbidding components, International Journal of Foundations of Computer Science, 20, 2, 331-340 (2009) · Zbl 1178.68303
[8] Csuhaj-Varjú, E.; Masopust, T.; Vaszil, G., Cooperating distributed grammar systems with permitting grammars as components, Romanian Journal of Information Science and Technology, 12, 2, 175-189 (2009)
[9] Křivka, Z.; Masopust, T., A note on the cooperation in rewriting systems with context-dependency checking, (11th Italian Conference on Theoretical Computer Science (2009)), 129-135
[10] Z. Křivka, T. Masopust, Cooperating distributed grammar systems with random context grammars as components (manuscript).; Z. Křivka, T. Masopust, Cooperating distributed grammar systems with random context grammars as components (manuscript).
[11] Salomaa, A., Formal Languages (1973), Academic Press: Academic Press New York · Zbl 0262.68025
[12] Kasai, T., An hierarchy between context-free and context-sensitive languages, Journal of Computer and System Sciences, 4, 5, 492-508 (1970) · Zbl 0212.02705
[13] Meduna, A.; Horvath, G., On state grammars, Acta Cybernetica, 8, 3, 237-245 (1988) · Zbl 0654.68097
[14] Geffert, V., Context-free-like forms for the phrase-structure grammars, (Chytil, M.; Janiga, L.; Koubek, V., MFCS. MFCS, Lecture Notes in Computer Science, vol. 324 (1988), Springer), 309-317 · Zbl 0652.68095
[15] Hauschildt, D.; Jantzen, M., Petri net algorithms in the theory of matrix grammars, Acta Informatica, 31, 8, 719-728 (1994) · Zbl 0834.68064
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.