Detail publikace

On the Descriptional Complexity of Scattered Context Grammars

MASOPUST Tomáš. On the Descriptional Complexity of Scattered Context Grammars. Theoretical Computer Science, roč. 410, č. 1, 2009, s. 108-112. ISSN 0304-3975.
Název česky
O popisné složitosti gramatik s rozptýleným kontextem
Typ
článek v časopise
Jazyk
angličtina
Autoři
Masopust Tomáš, RNDr., Ph.D. (UIFS FIT VUT)
URL
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
Vydavatel
Elsevier Science
UT WoS
000262997100011
BibTeX 
@ARTICLE{FITPUB8778,
   author = "Tom\'{a}\v{s} Masopust",
   title = "On the Descriptional Complexity of Scattered Context Grammars",
   pages = "108--112",
   journal = "Theoretical Computer Science",
   volume = 410,
   number = 1,
   year = 2009,
   ISSN = "0304-3975",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8778"
}
Nahoru