Detail publikace

On the Descriptional Complexity of Scattered Context Grammars

MASOPUST, T. On the Descriptional Complexity of Scattered Context Grammars. Theoretical Computer Science, 2009, vol. 410, no. 1, p. 108-112. ISSN: 0304-3975.
Název česky
O popisné složitosti gramatik s rozptýleným kontextem
Typ
článek v časopise
Jazyk
anglicky
Autoři
Masopust Tomáš, doc. RNDr., Ph.D. (CK-SZZ)
URL
Klíčová slova

scattered context grammar; descriptional complexity.

Abstrakt

V článku je dokázáno, že každý rekurzívně spočetný jazyk je generovaný gramatikou s rozptýleným kontextem s nejvýše čtyřmi neterminály a třemi pravidly, která nejsou bezkontextová. V závěru je rovněž podán přehled výsledků a otevřených problémů z této problematiky.

Rok
2009
Strany
108–112
Časopis
Theoretical Computer Science, roč. 410, č. 1, ISSN 0304-3975
UT WoS
000262997100011
BibTeX 
@article{BUT49470,
  author="Tomáš {Masopust}",
  title="On the Descriptional Complexity of Scattered Context Grammars",
  journal="Theoretical Computer Science",
  year="2009",
  volume="410",
  number="1",
  pages="108--112",
  issn="0304-3975",
  url="http://dx.doi.org/10.1016/j.tcs.2008.10.017"
}
Nahoru