Detail publikace

Descriptional Complexity of Multi-Parallel Grammars

MASOPUST, T. Descriptional Complexity of Multi-Parallel Grammars. Information Processing Letters, 2008, vol. 108, no. 2, p. 68-70. ISSN: 0020-0190.
Název česky
Popisná složitost multi-paralelních gramatik
Typ
článek v časopise
Jazyk
anglicky
Autoři
Masopust Tomáš, doc. RNDr., Ph.D. (CK-SZZ)
URL
Klíčová slova

formal languages, multi-parallel grammars, descriptional complexity

Abstrakt

Článek diskutuje popisnou složitost multi-paralelních gramatik s ohledem k počtu neterminálů, selektorů a délce selektorů. Dokazuje, že libovolný rekurzivně spočetný jazyk lze generovat multi-paralelní gramatikou s nejvýše sedmi neterminály a čtyřmi selektory délky pět.

Rok
2008
Strany
68–70
Časopis
Information Processing Letters, roč. 108, č. 2, ISSN 0020-0190
UT WoS
000259435800005
BibTeX 
@article{BUT48168,
  author="Tomáš {Masopust}",
  title="Descriptional Complexity of Multi-Parallel Grammars",
  journal="Information Processing Letters",
  year="2008",
  volume="108",
  number="2",
  pages="68--70",
  issn="0020-0190",
  url="http://dx.doi.org/10.1016/j.ipl.2008.04.002"
}
Nahoru