On the descriptional complexity of scattered context grammars

From International Center for Computational Logic

Toggle side column

On the descriptional complexity of scattered context grammars

Tomáš MasopustTomáš Masopust
On the descriptional complexity of scattered context grammars


Tomáš Masopust
On the descriptional complexity of scattered context grammars
Theoretical Computer Science, 410(1):108-112, 2009
  • KurzfassungAbstract
    This paper proves that every recursively enumerable language is generated by a scattered context grammar with no more than four nonterminals and three non-context-free productions. In its conclusion, it gives an overview of the results and open problems concerning scattered context grammars and languages.
  • Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems
@article{M2009,
  author  = {Tom{\'{a}}{\v{s}} Masopust},
  title   = {On the descriptional complexity of scattered context grammars},
  journal = {Theoretical Computer Science},
  volume  = {410},
  number  = {1},
  year    = {2009},
  pages   = {108-112},
  doi     = {10.1016/j.tcs.2008.10.017}
}