On Metalinear CD Grammar Systems

• Autorzy: Sunckel B.
• Języki publikacji: EN

Abstrakty

EN

Metalinear CD grammar systems are defined to be context-free CD grammar systems where each component consists of metalinear productions. The maximal number of nonterminals in a starting production is the width of a CD grammar system. It will be shown that the width of metalinear CD grammar systems induces an infinite hierarchy of language classes. In addition, it is established that metalinear CD grammar systems of a certain width generate language classes that do not contain all context-free languages but contain some context-sensitive languages. The resulting language classes are closed under union, intersection with regular languages, homomorphism and inverse homomorphism. They are not closed under concatenation, Kleene closure, intersection and complement.

Słowa kluczowe

EN

cooperating distributed grammar systems; metalinear grammars

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 76, nr 3
• Strony: 383--397
• Opis fizyczny: bibliogr. 7 poz.

Twórcy

autor

Sunckel B.

• Institute of Informatics, Johann Wolfgang Goethe-Universität, Postfach 11 19 32, D-60054 Frankfurt am Main, Germany,

Bibliografia

• [1] Bordihn, H., Sunckel, B.: On active symbols in CD grammar systems, Proceedings of the Seventh International Workshop on Desriptional Complexity of Formal Systems (DCFS 2005) (C. Merheghetti, B. Palano, G. Pighizzini, D.Wotschke, Eds.), Rapporto Technico 06-05, Dipartimento di Informatica e Communicazione, Università degli Studi di Milano, Milano, Italy, 2005.
• [2] Csuhaj-Varjú, E., Dassow, J., Kelemen, J., Pǎun, G.: Grammar Systems: A Grammatical Approach to Distribution and Cooperation, Gordon and Breach, London, 1994.
• [3] Dassow, J., Pǎun, G.: Regulated Rewriting in Formal Language Theory, Springer, Berlin, 1989.
• [4] Dassow, J., Pǎun, G., Rozenberg, G.: Grammar Systems, in: Handbook of Formal Languages (G. Rozenberg, A. Salomaa, Eds.), vol. 2, Springer-Verlag, Berlin, 1997, 155-213.
• [5] Hopcroft, J. E., Ullman, J. D.: Introduction to Automata Theory, Languages and Computation, Addison-Wesley, London, 1979.
• [6] Rozenberg, G., Vermeir, D.: On metalinear ET0L systems, Fundamenta Informaticae 3(1), 1980, 15-36.
• [7] Sunckel, B.: On the descriptional complexity of metalinear CD grammar systems, in: Pre-proceedings of the Sixth International Workshop on Desriptional Complexity of Formal Systems (DCFS 2004) (L. Ilie, D. Wotschke, Eds.), Report No. 619, Department of Computer Science, The University of Western Ontario, London, Ontario, Canada, 2004, (To appear in International Journal of Foundations of Computer Science.).