Detail publikace

Cooperating Distributed Grammar Systems with Permitting Grammars as Components

CSUHAJ-VARJÚ, E.; MASOPUST, T.; VASZIL, G. Cooperating Distributed Grammar Systems with Permitting Grammars as Components. Romanian Journal of Information Science and Technology (ROMJIST), 2009, vol. 12, no. 2, p. 175-189. ISSN: 1453-8245.
Název česky
Kooperující distribuované gramatické systémy s povolujícími gramatikami jako komponentami
Typ
článek v časopise
Jazyk
anglicky
Autoři
Csuhaj-Varjú Erzsébet
Masopust Tomáš, doc. RNDr., Ph.D. (CK-SZZ)
Vaszil György
URL
Klíčová slova

Cooperating distributed grammar systems, permitting grammars, left-permitting grammars, generative power.

Abstrakt

Č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ů.

Rok
2009
Strany
175–189
Časopis
Romanian Journal of Information Science and Technology (ROMJIST), roč. 12, č. 2, ISSN 1453-8245
BibTeX 
@article{BUT47968,
  author="Erzsébet {Csuhaj-Varjú} and Tomáš {Masopust} and György {Vaszil}",
  title="Cooperating Distributed Grammar Systems with Permitting Grammars as Components",
  journal="Romanian Journal of Information Science and Technology (ROMJIST)",
  year="2009",
  volume="12",
  number="2",
  pages="175--189",
  issn="1453-8245",
  url="http://www.imt.ro/romjist/"
}
Nahoru