On the Descriptional Complexity of Scattered Context Grammars

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.

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í

Odkazy

URL

Impakt faktor

Impact factor: 0.943

Označené pro přenos do RIV

Ne

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

---

Anotace

V originále

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.

Č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.