MASOPUST, Tomáš. On the Descriptional Complexity of Scattered Context Grammars. Theoretical Computer Science. Amsterdam, North Holland: Elsevier Science Publishers, 2009, roč. 410, s. 108-112. ISSN 0304-3975.
Další formáty:   BibTeX LaTeX RIS
Základní údaje
Originální název On the Descriptional Complexity of Scattered Context Grammars
Název česky O popisné složitosti gramatik s rozptýleným kontextem
Autoři MASOPUST, Tomáš.
Vydání Theoretical Computer Science, Amsterdam, North Holland, Elsevier Science Publishers, 2009, 0304-3975.
Další údaje
Typ výsledku Článek v odborném periodiku
Utajení není předmětem státního či obchodního tajemství
WWW URL
Impakt faktor Impact factor: 0.943
Organizační jednotka Fakulta informatiky
UT WoS 000262997100011
Klíčová slova anglicky scattered context grammar; descriptional complexity
Štítky descriptional complexity, scattered context grammar
Příznaky Mezinárodní význam, Recenzováno
Změnil Změnil: doc. RNDr. Tomáš Masopust, Ph.D., DSc., učo 4030. Změněno: 29. 6. 2009 15:20.
Anotace
This paper proves that every recursively enumerable language is generated by a scattered context grammar with no more than four nonterminals and three non-context-free productions. In its conclusion, it gives an overview of the results and open problems concerning scattered context grammars and languages.
Anotace česky
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.
VytisknoutZobrazeno: 12. 6. 2024 04:00