Cooperating Distributed Grammar Systems with Permitting Grammars as Components

CSUHAJ-VARJÚ, Erzsébet, Tomáš MASOPUST a György VASZIL. Cooperating Distributed Grammar Systems with Permitting Grammars as Components. Romanian Journal of Information Science and Technology. Romanian Academy, 2009, roč. 12, č. 2, s. 175-189. ISSN 1453-8245.

Základní údaje

• Originální název: Cooperating Distributed Grammar Systems with Permitting Grammars as Components
• Autoři: CSUHAJ-VARJÚ, Erzsébet, Tomáš MASOPUST a György VASZIL.
• Vydání: Romanian Journal of Information Science and Technology, Romanian Academy, 2009, 1453-8245.

Další údaje

• Originální jazyk: angličtina
• Typ výsledku: Článek v odborném periodiku
• Obor: 10201 Computer sciences, information science, bioinformatics
• Utajení: není předmětem státního či obchodního tajemství
• WWW: URL
• Impakt faktor: Impact factor: 0.075
• Organizační jednotka: Fakulta informatiky
• UT WoS: 000277059200005
• Klíčová slova anglicky: Cooperating distributed grammar system; permitting grammars; left-permitting grammars; generative power.
• Štítky: Cooperating distributed grammar system, generative power., left-permitting grammars, permitting grammars
• Příznaky: Mezinárodní význam, Recenzováno

Anotace

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.

Anotace česky

Článek studuje kooperující distribuované gramatické systémy pracující v terminálním módu, kde komponenty jsou varianty povolujících gramatik. Ukazuje, že ačkoliv je třída povolujících jazyků ostře vnořena do třídy random context jazyků, jsou třídy random context jazyků a jazyků generovaných povolujícími kooperujícími distribuovanými gramatickými systémy shodné. Navíc, pokud jsou komponenty tzv. levě-povolující gramatiky, pak kooperující distribuované gramatické systémy s terminálním módem charakterizují třídu kontextových jazyků, či jazyků typu 0, pokud připustíme vymazávací pravidla. Článek dále uvádí výsledky z popisné složitosti, zejména to, že počet komponent může být ohraničen a v případě levě-povolujících gramatik s vymazávacími pravidly dokonce společně s počtem neterminálů.