Left Random Context ET0L Grammars

• Autorzy: Meduna A. , Zemek P.
• Języki publikacji: EN

Abstrakty

EN

Consider ET0L grammars. Modify them such that a set of permitting symbols and a set of forbidding symbols are attached to each of their rules, just like in random context grammars. A rule like this can rewrite a symbol if each of its permitting symbols occurs to the left of the symbol to be rewritten in the current sentential form while each of its forbidding symbols does not occur there. ET0L grammars modified in this way are referred to as left random context ET0L grammars, and they represent the principal subject of the investigation in this paper. We prove that these grammars characterize the family of recursively enumerable languages, and without erasing rules, they characterize the family of context-sensitive languages. We also introduce a variety of special cases of these grammars and establish their generative power. In the conclusion, we put all the achieved results into the context of formal language theory as a whole and formulate several open questions.

Słowa kluczowe

EN

regulated rewriting; ET0L grammars; random context; left variants; generative power; language families

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 123, nr 3
• Strony: 289--304
• Opis fizyczny: Bibliogr. 27 poz.

Twórcy

autor

Meduna A.

• Faculty of Information Technology, Brno University of Technology Boˇzetˇechova 1/2, Brno 612 66, Czech Republic

autor

Zemek P.

• Faculty of Information Technology, Brno University of Technology Boˇzetˇechova 1/2, Brno 612 66, Czech Republic

Bibliografia

• [1] Beek, M., Csuhaj-Varjú, E., Holzer, M., Vaszil, G.: On Competence in CD Grammar Systems, in: Developments in Language Theory, vol. 3340 of Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 2005, 3–14.
• [2] Beek, M., Csuhaj-Varjú, E., Holzer, M., Vaszil, G.: On Competence in CD Grammar Systems with Parallel Rewriting, International Journal of Foundations of Computer Science, 18(6), 2007, 1425–1439.
• [3] Bordihn, H., Holzer, M.: Grammar Systems with Negated Conditions in their Cooperation Protocols, Journal of Universal Computer Science, 6(12), 2000, 1165–1184.
• [4] Bordihn, H., Holzer, M.: Random Context in Regulated Rewriting Versus Cooperating Distributed Grammar Systems, in: Language and Automata Theory and Applications, vol. 5196 of Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 2008, 125–136.
• [5] Csuhaj-Varjú, E., Dassow, J., Vaszil, G.: Some New Modes of Competence-Based Derivations in CD Grammar Systems, in: Developments in Language Theory, vol. 5257 of Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 2008, 228–239.
• [6] 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), 2009, 175–189.
• [7] Csuhaj-Varjú, E., P˘aun, G., Salomaa, A.: Conditional Tabled Eco-Grammar Systems, Journal of Universal Computer Science, 1(5), 1995, 252–268.
• [8] Dassow, J.: On Cooperating Distributed Grammar Systems with Competence Based Start and Stop Conditions, Fundamenta Informaticae, 76(3), 2007, 293–304.
• [9] Dassow, J., P˘aun, G.: Regulated Rewriting in Formal Language Theory, Springer, New York, 1989.
• [10] Fernau, H., Holzer, M., Freund, R.: Hybrid modes in cooperating distributed grammar systems: internal versus external hybridization, Theoretical Computer Science, 259, 2001, 405–426.
• [11] Goldefus, F., Masopust, T., Meduna, A.: Left-Forbidding Cooperating Distributed Grammar Systems, Theoretical Computer Science, 20(3), 2010, 1–11.
• [12] Lamm, E., Unger, R., Eds.: Biological Computation, 3rd edition, Humana Press, New York, 2004.
• [13] Meduna, A.: Automata and Languages: Theory and Applications, Springer, London, 2000.
• [14] Meduna, A., ˇSvec, M.: Forbidding ET0L Grammars, Theoretical Computer Science, 2003(306), 2003, 449–469.
• [15] Meduna, A., ˇSvec, M.: Grammars with Context Conditions and Their Applications, Wiley, New Jersey, 2005.
• [16] Meduna, A., Zemek, P.: One-Sided Random Context Grammars, Acta Informatica, 48(3), 2011, 149–163.
• [17] Penttonen, M.: One-sided and two-sided context in formal grammars, Information and Control, 25(4), 1974, 371–392.
• [18] Rozenberg, G., Salomaa, A.: Mathematical Theory of L Systems, Academic Press, Orlando, 1980.
• [19] Rozenberg, G., Salomaa, A.: The Book of L, Springer-Verlag, New York, 1986.
• [20] Rozenberg, G., Salomaa, A., Eds.: Lindenmayer Systems: Impacts on Theoretical Computer Science, Computer Graphics, and Developmental Biology, Springer, London, 1992.
• [21] Rozenberg, G., Salomaa, A., Eds.: Handbook of Formal Languages, Vol. 1: Word, language, grammar, Springer, New York, 1997.
• [22] Rozenberg, G., Salomaa, A., Eds.: Handbook of Formal Languages, Vol. 2: Linear Modeling: Background and Application, Springer, New York, 1997.
• [23] Rozenberg, G., Solms, S. H. V.: Priorities on context conditions in rewriting systems, Information Sciences, 14(1), 1978, 15–50.
• [24] Salomaa, A.: Formal Languages, Academic Press, London, 1973.
• [25] Solms, S. H. V.: Some Notes on ET0L Languages, International Journal of Computer Mathematics, 5, 1976, 285–296.
• [26] Sosık, P.: The Power of Catalysts and Priorities in Membrane Systems, Grammars, 6(1), 2003, 13–24.
• [27] Švec, M.: Simple Semi-Conditional ET0L Grammars, Proceedings of the International Conference and Competition Student EEICT 2003, Faculty of Electrical Engineering and Communication BUT, 2003.