On Descriptional Complexity of Partially Parallel Grammars

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

Toggle side column

On Descriptional Complexity of Partially Parallel Grammars

Tomáš MasopustTomáš Masopust,  Alexander MedunaAlexander Meduna
On Descriptional Complexity of Partially Parallel Grammars


Tomáš Masopust, Alexander Meduna
On Descriptional Complexity of Partially Parallel Grammars
Fundamenta Informaticae, 87(3-4):407-415, 2008
  • 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}
}