Article4033

PublikationenPublications

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

Toggle side column

Bounded Number of Parallel Productions in Scattered Context Grammars with Three Nonterminals

Tomáš MasopustTomáš Masopust

• ISSN: 0169-2968
• Download

Tomáš Masopust
Bounded Number of Parallel Productions in Scattered Context Grammars with Three Nonterminals
Fundamenta Informaticae, 99(4):473-480, 2010

• Details
• Bibtex

• KurzfassungAbstract
  Scattered context grammars with three nonterminals are known to be computationally complete. So far, however, it was an open problem whether the number of parallel productions can be bounded along with three nonterminals. In this paper, we prove that every recursively enumerable language is generated by a scattered context grammar with three nonterminals and five parallel productions, each of which simultaneously rewrites no more than nine nonterminals.
• Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems

@article{M2010,
  author  = {Tom{\'{a}}{\v{s}} Masopust},
  title   = {Bounded Number of Parallel Productions in Scattered Context
             Grammars with Three Nonterminals},
  journal = {Fundamenta Informaticae},
  volume  = {99},
  number  = {4},
  year    = {2010},
  pages   = {473-480}
}