Conference paper

MASOPUST Tomáš and MEDUNA Alexander. Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement. In: Proceedings of 11th International Workshop on Descriptional Complexity of Formal Systems. Magdeburg: Otto-von-Guericke-University of Magdeburg, 2009, pp. 235-245. ISBN 978-3-940961-31-0.
Publication language:english
Original title:Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement
Title (cs):Popicná složitost gramatik s rozptýleným kontextem se třemi neterminály: vylepšení
Pages:235-245
Proceedings:Proceedings of 11th International Workshop on Descriptional Complexity of Formal Systems
Conference:11th International Workshop on Descriptional Complexity of Formal Systems
Place:Magdeburg, DE
Year:2009
ISBN:978-3-940961-31-0
Publisher:Otto-von-Guericke-University of Magdeburg
URL:http://cgi.cse.unsw.edu.au/~rvg/eptcs/content.cgi?DCFS2009 [HTML]
Keywords
Scattered context grammars, descriptional complexity, generative power
Annotation
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.
BibTeX:
@INPROCEEDINGS{
   author = {Tom{\'{a}}{\v{s}} Masopust and Alexander Meduna},
   title = {Descriptional Complexity of Three-Nonterminal Scattered
	Context Grammars: An Improvement},
   pages = {235--245},
   booktitle = {Proceedings of 11th International Workshop on Descriptional
	Complexity of Formal Systems},
   year = {2009},
   location = {Magdeburg, DE},
   publisher = {Otto-von-Guericke-University of Magdeburg},
   ISBN = {978-3-940961-31-0},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php?id=8940}
}

Your IPv4 address: 54.145.183.43
Switch to IPv6 connection

DNSSEC [dnssec]