Descriptional complexity of semi-conditional grammars

From International Center for Computational Logic

Toggle side column

Descriptional complexity of semi-conditional grammars

Tomáš MasopustTomáš Masopust,  Alexander MedunaAlexander Meduna
Descriptional complexity of semi-conditional grammars


Tomáš Masopust, Alexander Meduna
Descriptional complexity of semi-conditional grammars
Information Processing Letters, 104(1):29-31, 2007
  • KurzfassungAbstract
    The descriptional complexity of semi-conditional grammars is studied. It is proved that every recursively enumerable language is generated by a semi-conditional grammar of degree (2,1) with no more than seven conditional productions and eight nonterminals.
  • Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems
@article{MM2007,
  author  = {Tom{\'{a}}{\v{s}} Masopust and Alexander Meduna},
  title   = {Descriptional complexity of semi-conditional grammars},
  journal = {Information Processing Letters},
  volume  = {104},
  number  = {1},
  year    = {2007},
  pages   = {29-31},
  doi     = {10.1016/j.ipl.2007.05.002}
}