Přístupnostní navigace
E-přihláška
Vyhledávání Vyhledat Zavřít
Detail publikace
MASOPUST, T. MEDUNA, A.
Originální název
Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement
Typ
článek ve sborníku mimo WoS a Scopus
Jazyk
angličtina
Originální abstrakt
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.
Klíčová slova
Scattered context grammars, descriptional complexity, generative power
Autoři
MASOPUST, T.; MEDUNA, A.
Rok RIV
2009
Vydáno
6. 7. 2009
Nakladatel
Otto-von-Guericke-University of Magdeburg
Místo
Magdeburg
ISBN
978-3-940961-31-0
Kniha
Proceedings of 11th International Workshop on Descriptional Complexity of Formal Systems
Strany od
235
Strany do
245
Strany počet
11
URL
http://cgi.cse.unsw.edu.au/~rvg/eptcs/content.cgi?DCFS2009
BibTex
@inproceedings{BUT33782, author="Tomáš {Masopust} and Alexandr {Meduna}", title="Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement", booktitle="Proceedings of 11th International Workshop on Descriptional Complexity of Formal Systems", year="2009", pages="235--245", publisher="Otto-von-Guericke-University of Magdeburg", address="Magdeburg", isbn="978-3-940961-31-0", url="http://cgi.cse.unsw.edu.au/~rvg/eptcs/content.cgi?DCFS2009" }