On Metalinear CD Grammar Systems

Issue title: SPECIAL ISSUE ON DEVELOPMENTS IN GRAMMAR SYSTEMS

Article type: Research Article

Authors: Sunckel, Bettina

Affiliations: Institute of Informatics, Johann Wolfgang Goethe-Universität, Postfach 11 19 32 D-60054 Frankfurt am Main, Germany. E-mail: sunckel@psc.informatik.uni-frankfurt.de

Abstract: 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.

Keywords: Cooperating distributed grammar systems, metalinear grammars

Journal: Fundamenta Informaticae, vol. 76, no. 3, pp. 383-397, 2007