Faculty of Information Technology, BUT

Publication Details

Cooperating Distributed Grammar Systems with Permitting Grammars as Components

CSUHAJ-VARJÚ Erzsébet, MASOPUST Tomáš and VASZIL György. Cooperating Distributed Grammar Systems with Permitting Grammars as Components. Romanian Journal of Information Science and Technology (ROMJIST), vol. 12, no. 2, pp. 175-189. ISSN 1453-8245.
Czech title
Kooperující distribuované gramatické systémy s povolujícími gramatikami jako komponentami
Type
journal article
Language
english
Authors
Csuhaj-Varjú Erzsébet, D.Sc. ( unknown)
Masopust Tomáš, RNDr., Ph.D. (DIFS FIT BUT)
Vaszil György, PhD ()
URL
Keywords
Cooperating distributed grammar systems, permitting grammars, left-permitting grammars, generative power.
Abstract
This paper studies cooperating distributed grammar systems working in the terminal derivation mode where the components are variants of permitting grammars. It proves that although the family of permitting languages is strictly included in the family of random context languages, the families of random context languages and languages generated by permitting cooperating distributed grammar systems in the above mentioned derivation mode coincide. Moreover, if the components are so-called left-permitting grammars, then cooperating distributed grammar systems in the terminal mode characterize the class of context-sensitive languages, or if erasing rules are allowed, the class of recursively enumerable languages. Descriptional complexity results are also presented. It is shown that the number of permitting components can be bounded, in the case of left-permitting components with erasing rules even together with the number of nonterminals.

Published
2009
Pages
175-189
Journal
Romanian Journal of Information Science and Technology (ROMJIST), vol. 12, no. 2, ISSN 1453-8245
Publisher
Romanian Academy, Publishing House of the Romanian Academy
BibTeX
@ARTICLE{FITPUB8880,
   author = "Erzs\'{e}bet Csuhaj-Varj\'{u} and Tom\'{a}\v{s} Masopust and Gy\"{o}rgy Vaszil",
   title = "Cooperating Distributed Grammar Systems with Permitting Grammars as Components",
   pages = "175--189",
   journal = "Romanian Journal of Information Science and Technology (ROMJIST)",
   volume = 12,
   number = 2,
   year = 2009,
   ISSN = "1453-8245",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8880"
}
Back to top