Descriptional complexity of semi-conditional grammars

PublikationenPublications

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

Toggle side column

Descriptional complexity of semi-conditional grammars

Tomáš MasopustTomáš Masopust,  Alexander MedunaAlexander Meduna

• ISSN: 0020-0190
• Download
• DOI Link

Tomáš Masopust, Alexander Meduna
Descriptional complexity of semi-conditional grammars
Information Processing Letters, 104(1):29-31, 2007

• Details
• Bibtex

• 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}
}