MASOPUST Tomáš and MEDUNA Alexander. Descriptional Complexity of ThreeNonterminal Scattered Context Grammars: An Improvement. In: Proceedings of 11th International Workshop on Descriptional Complexity of Formal Systems. Magdeburg: OttovonGuerickeUniversity of Magdeburg, 2009, pp. 235245. ISBN 9783940961310. 
Publication language:  english 

Original title:  Descriptional Complexity of ThreeNonterminal Scattered Context Grammars: An Improvement 

Title (cs):  Popicná složitost gramatik s rozptýleným kontextem se třemi neterminály: vylepšení 

Pages:  235245 

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:  9783940961310 

Publisher:  OttovonGuerickeUniversity 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 ThreeNonterminal Scattered
Context Grammars: An Improvement},
pages = {235245},
booktitle = {Proceedings of 11th International Workshop on Descriptional
Complexity of Formal Systems},
year = {2009},
location = {Magdeburg, DE},
publisher = {OttovonGuerickeUniversity of Magdeburg},
ISBN = {9783940961310},
language = {english},
url = {http://www.fit.vutbr.cz/research/view_pub.php?id=8940}
} 