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

Tomáš MasopustTomáš Masopust, Alexander MedunaAlexander Meduna

Download

Tomáš Masopust, Alexander Meduna
Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvemen
Proc. of 11th International Workshop on Descriptional Complexity of Formal Systems (DCFS), 183-192, 2009

Details
Bibtex

KurzfassungAbstract
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.
Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems

@inproceedings{MM2009,
  author    = {Tom{\'{a}}{\v{s}} Masopust and Alexander Meduna},
  title     = {Descriptional Complexity of Three-Nonterminal Scattered Context
               Grammars: An Improvemen},
  booktitle = {Proc. of 11th International Workshop on Descriptional Complexity
               of Formal Systems (DCFS)},
  year      = {2009},
  pages     = {183-192}
}