Detail publikace

On Descriptional Complexity of Partially Parallel Grammars

MASOPUST, T.; MEDUNA, A. On Descriptional Complexity of Partially Parallel Grammars. Fundamenta Informaticae, 2008, vol. 87, no. 3, p. 407-415. ISSN: 0169-2968.
Název česky
O popisné složitosti částečně paralelních gramatik
Typ
článek v časopise
Jazyk
anglicky
Autoři
Masopust Tomáš, doc. RNDr., Ph.D. (CK-SZZ)
Meduna Alexandr, prof. RNDr., CSc. (UIFS)
URL
Klíčová slova

formal languages, scattered context grammars, multisequential grammars, multicontinuous grammars, descriptional complexity

Abstrakt

Článek upravuje některé výsledky týkající se popisné složitostičástečně paralelních gramatik. Ukazuje, že každý rekurzívně spočetnýjazyk je generovaný gramatikou s rozptýleným kontextem se čtyřmineterminály a ne více jak čtyřmi pravidly, která nejsou bezkontextová,multisekvenční gramatikou mající dva neterminály a dva selektory amulticontinuous gramatikou mající tři neterminály a dva selektory.

Rok
2008
Strany
407–415
Časopis
Fundamenta Informaticae, roč. 87, č. 3, ISSN 0169-2968
UT WoS
000262368900006
BibTeX 
@article{BUT49466,
  author="Tomáš {Masopust} and Alexandr {Meduna}",
  title="On Descriptional Complexity of Partially Parallel Grammars",
  journal="Fundamenta Informaticae",
  year="2008",
  volume="87",
  number="3",
  pages="407--415",
  issn="0169-2968",
  url="http://fi.mimuw.edu.pl/vol87.html"
}
Nahoru