On Descriptional Complexity of Partially Parallel Grammars

Tomáš MasopustTomáš Masopust, Alexander MedunaAlexander Meduna

ISSN: 0169-2968
Download

Tomáš Masopust, Alexander Meduna
On Descriptional Complexity of Partially Parallel Grammars
Fundamenta Informaticae, 87(3-4):407-415, 2008

Details
Bibtex

KurzfassungAbstract
This paper presents some new results concerning the descriptional complexity of partially parallel grammars. Specifically, it proves that every recursively enumerable language is generated (i) by a four-nonterminal scattered context grammar with no more than four non-context-free productions, (ii) by a two-nonterminal multisequential grammar with no more than two selectors, or (iii) by a three-nonterminalmulticontinuous grammar with no more than two selectors.
Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems

@article{MM2008,
  author  = {Tom{\'{a}}{\v{s}} Masopust and Alexander Meduna},
  title   = {On Descriptional Complexity of Partially Parallel Grammars},
  journal = {Fundamenta Informaticae},
  volume  = {87},
  number  = {3-4},
  year    = {2008},
  pages   = {407-415}
}