Publication details
Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement
| Authors | |
|---|---|
| Year of publication | 2009 |
| Type | Article in Proceedings |
| Conference | Proceedings of 11th International Workshop on Descriptional Complexity of Formal Systems |
| MU Faculty or unit | |
| Citation | |
| Field | Informatics |
| Keywords | Scattered context grammars, descriptional complexity, generative power |
| Description | 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. |