ON THE GENERATIVE CAPACITY OF CERTAIN CLASSES OF COOPERATING GRAMMAR SYSTEMS

Article type: Research Article

Authors: Dassow, Jürgen | Paun, Gheorghe | Vicolov, Sorina

Affiliations: Otto-von-Guericke-University Magdeburg, Department of Mathematics PSF 4120, D-39016 Magdeburg, Germany | Institute of Mathematics of the Romanian Academy of Sciences Str. Academiei 14, B-70109 Bucuresti, Romania

Note: [] Research supported by Alexander von Humboldt Foundation

Abstract: The paper looks for necessary conditions for a language to be generated by a cooperating distributed grammar system with modes = k and ≥ k of derivation. It is proved that the length set of such languages contains infinite arithmetical progressions. Some consequences of this result are derived, concerning the power of these grammars and the closure properties of the corresponding families. Then, one proves that these systems can generate non-semi-linear languages. (Both these questions were formulated as open problems in the field literature.)

DOI: 10.3233/FI-1995-2232

Journal: Fundamenta Informaticae, vol. 22, no. 3, pp. 217-226, 1995