On the descriptional complexity of scattered context grammars

PublikationenPublications

• Nach AutorBy Author
  • Tomáš MasopustTomáš Masopust
• Nach ForschungsgruppeBy Research Group
  • Wissensbasierte SystemeKnowledge-Based Systems

Toggle side column

On the descriptional complexity of scattered context grammars

Tomáš MasopustTomáš Masopust

• ISSN: 0304-3975
• Download
• DOI Link

Tomáš Masopust
On the descriptional complexity of scattered context grammars
Theoretical Computer Science, 410(1):108-112, 2009

• Details
• Bibtex

• 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}
}