Descriptional Complexity of Grammars Regulated by Context Conditions

Tomáš MasopustTomáš Masopust, Alexander MedunaAlexander Meduna

Download

Tomáš Masopust, Alexander Meduna
Descriptional Complexity of Grammars Regulated by Context Conditions
Proc. of Language and Automata Theory and Applications (LATA), 403-412, 2007

Details
Bibtex

KurzfassungAbstract
This paper improves several well-known results concerning the descriptional complexity of grammars regulated by context conditions. Specifically, it proves that every recursively enumerable language is generated (A) by a context-conditional grammar of degree (2, 1) with no more than seven conditional productions and eight nonterminals, (B) by a generalized forbidding grammar of degree two with no more than eight conditional productions and ten nonterminals, or (C) by a simple semi-conditional grammar of degree (2, 1) with no more than nine conditional productions and ten nonterminals.
Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems

@inproceedings{MM2007,
  author    = {Tom{\'{a}}{\v{s}} Masopust and Alexander Meduna},
  title     = {Descriptional Complexity of Grammars Regulated by Context
               Conditions},
  booktitle = {Proc. of Language and Automata Theory and Applications (LATA)},
  year      = {2007},
  pages     = {403-412}
}