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" }