Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F09%3APU82608" target="_blank" >RIV/00216305:26230/09:PU82608 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement

Popis výsledku v původním jazyce

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 duringa 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 rewrittenduring any derivation step can be limited by a small constant regardless of other factors.<br>

Název v anglickém jazyce

Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement

Popis výsledku anglicky

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 duringa 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 rewrittenduring any derivation step can be limited by a small constant regardless of other factors.<br>

Druh

D - Stať ve sborníku

CEP obor

BD - Teorie informace

OECD FORD obor

—

Projekt

<a href="/cs/project/GA201%2F07%2F0005" target="_blank" >GA201/07/0005: Multiinformační technologie: Teorie, modely a metody</a><br>

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2009

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of 11th International Workshop on Descriptional Complexity of Formal Systems

ISBN

978-3-940961-31-0

ISSN

—

e-ISSN

—

Počet stran výsledku

11

Strana od-do

—

Název nakladatele

Otto-von-Guericke-University of Magdeburg

Místo vydání

Magdeburg

Místo konání akce

Magdeburg

Datum konání akce

6. 7. 2009

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—