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

Tomáš Masopust
Alexander Meduna

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 simultaneously rewritten during any derivation step can be limited by a small constant regardless of other factors.

In Jürgen Dassow, Giovanni Pighizzini and Bianca Truthe: Proceedings Eleventh International Workshop on Descriptional Complexity of Formal Systems (DCFS 2009), Magdeburg, Germany, July 6-9, 2009, Electronic Proceedings in Theoretical Computer Science 3, pp. 183–192.
Published: 30th July 2009.

ArXived at: http://dx.doi.org/10.4204/EPTCS.3.17 bibtex PDF

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org