2009
Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement
MASOPUST, Tomáš a Alexander MEDUNAZákladní údaje
Originální název
Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement
Autoři
MASOPUST, Tomáš a Alexander MEDUNA
Vydání
Magdeburg, Proceedings of 11th International Workshop on Descriptional Complexity of Formal Systems, od s. 235-245, 2009
Nakladatel
Otto-von-Guericke-Universität Magdeburg, Germany
Další údaje
Jazyk
angličtina
Typ výsledku
Stať ve sborníku
Obor
10201 Computer sciences, information science, bioinformatics
Utajení
není předmětem státního či obchodního tajemství
Označené pro přenos do RIV
Ne
Organizační jednotka
Fakulta informatiky
ISBN
978-3-940961-31-0
Klíčová slova anglicky
Scattered context grammars, descriptional complexity, generative power
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 6. 7. 2009 23:34, doc. RNDr. Tomáš Masopust, Ph.D., DSc.
V originále
Recently, it has been shown that every recursively enumerable language can be generated by a scattered context grammar with no more than three nonterminals. However, in that construction, the maximal number of nonterminals simultaneously rewritten during a derivation step depends on many factors, such as the cardinality of the alphabet of the generated language and the structure of the generated language itself. This paper improves the result by showing that the maximal number of nonterminals rewritten during any derivation step can be limited by a small constant regardless of other factors.
Česky
Nedávno bylo ukázáno, že každý rekurzívně spočetný jazyk lze generovat gramatikou s rozptýleným kontextem s nejvýše třemi neterminály. V této konstrukci však počet současně přepisovaných neterminálů zavisí na mnoha faktorech, jako je kardinalita abecedy generovaného jazyka a struktura daného jazyka vůbec. Tento článek vylepšuje původní konstrukci tak, že v každém kroku derivace se přepíše nejvýše fixní počet symbolů bez ohledu na generovaný jazyk.