Descriptional complexity of multi-parallel grammars

Tomáš MasopustTomáš Masopust

ISSN: 0020-0190
Download
DOI Link

Tomáš Masopust
Descriptional complexity of multi-parallel grammars
Information Processing Letters, 108(2):68-70, 2008

Details
Bibtex

KurzfassungAbstract
This paper studies the descriptional complexity of multi-parallel grammars with respect to the number of nonterminals and selectors, and the length of these selectors. As a result, it proves that every recursively enumerable language is generated by a multi-parallel grammar with no more than seven nonterminals and four selectors of length five.
Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems

@article{M2008,
  author  = {Tom{\'{a}}{\v{s}} Masopust},
  title   = {Descriptional complexity of multi-parallel grammars},
  journal = {Information Processing Letters},
  volume  = {108},
  number  = {2},
  year    = {2008},
  pages   = {68-70},
  doi     = {10.1016/j.ipl.2008.04.002}
}