Descriptional Complexity of Grammars Regulated by Context Conditions

From International Center for Computational Logic

Toggle side column

Descriptional Complexity of Grammars Regulated by Context Conditions

Tomáš MasopustTomáš Masopust,  Alexander MedunaAlexander Meduna
Tomáš Masopust, Alexander Meduna
Descriptional Complexity of Grammars Regulated by Context Conditions
Proc. of Language and Automata Theory and Applications (LATA), 403-412, 2007
  • 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}
}