Context-Free and E0L Derivations over Free Groups

• Autorzy: Meduna A. , Bildo R. , Blatny' P.
• Języki publikacji: EN

Abstrakty

EN

In the context-free and E0L grammars discussed in this pa- per, the derivations are introduced over free groups rather than free monoids. It is proved that both grammars with derivations introduced in this way characterize the family of recursively enumerable languages in a very succinct way. Specifically, this characterization is based on the eight-nonterminal context-free grammars and six-nonterminal E0L grammars over free groups.

Słowa kluczowe

EN

context-free grammars; E0L grammars; derivations; free groups

• Wydawca: Wydawnictwo Uniwersytetu Jagiellońskiego
• Czasopismo: Schedae Informaticae
• Rocznik: 2007
• Tom: Vol. 16
• Strony: 9--20
• Opis fizyczny: Bibliogr. 10 poz.

Twórcy

autor

Meduna A.

autor

Bildo R.

autor

Blatny' P.

• Brno University of Technology, Faculty of Information Technology Bozetechova 2, 612 66 Brno, Czech Republic,

Bibliografia

• [1] Ito M.; Algebraic Theory of Automata and Languages, World Scientific, 2004.
• [2] Jacobson N.; Basic Algebra, 2nd ed., W.H. Freeman, New York 1989.
• [3] Kuroda S.Y.; Classes of Languages and Linear Bounded Automata, Inform. Control, 7, 1964, pp. 207–223.
• [4] Mateescu A., Salomaa A.; Aspects of Classical Language Theory, in: G. Rozenberg, A. Salomaa, (eds.), Handbook of Formal Languages, Vol. 1, Springer, 1997.
• [5] Meduna A.; Automata and Languages: Theory and Applications, Springer, London 2005.
• [6] Meduna A.; Context Free Derivations on Word Monoids, Acta Informatica, 27,1990, pp. 781–786.
• [7] Meduna A., Švec M.; Grammars with Context Conditions and Their Applications, Wiley, New York, US, 2004.
• [8] Meduna A., Kolář D.; Homogenous Grammars with a Reduced Number of Non-Context-Free Productions, Information Processing Letters, 81, 2002, pp. 253–257.
• [9] Meduna A.; Symbiotic E0L Systems. Artificial Life: Gramatical Models Bucharest 1995, pp. 122–129.
• [10] Salomaa A.; Formal Languages, Academic Press, New York 1973.