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

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche

Toggle side column

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

Tomáš MasopustTomáš Masopust,  Alexander MedunaAlexander Meduna
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
  • 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}
}