A Note on the Generative Power of Some Simple Variants of Context-Free Grammars Regulated by Context Conditions

From International Center for Computational Logic

Toggle side column

A Note on the Generative Power of Some Simple Variants of Context-Free Grammars Regulated by Context Conditions

Tomáš MasopustTomáš Masopust
A Note on the Generative Power of Some Simple Variants of Context-Free Grammars Regulated by Context Conditions


Tomáš Masopust
A Note on the Generative Power of Some Simple Variants of Context-Free Grammars Regulated by Context Conditions
In A. H. Dediu, A. M. Ionescu, C. Martín-Vide, eds., Proc. of 3rd International Conference Language and Automata Theory and Applications (LATA), volume 5457 of LNCS, 554-565, 2009. Springer
  • KurzfassungAbstract
    This paper answers three open questions concerning the generative power of some simple variants of context-free grammars regulated by context conditions. Specifically, it discusses the generative power of so-called context-free semi-conditional grammars (which are random context grammars where permitting and forbidding sets are replaced with permitting and forbidding strings) where permitting and forbidding strings of each production are of length no more than one, and of simple semi-conditional grammars where, in addition, no production has attached both a permitting and a forbidding string. Finally, this paper also presents some normal form results, an overview of known results, and unsolved problems.
  • Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-00982-2_47.
@inproceedings{M2009,
  author    = {Tom{\'{a}}{\v{s}} Masopust},
  title     = {A Note on the Generative Power of Some Simple Variants of
               Context-Free Grammars Regulated by Context Conditions},
  editor    = {A. H. Dediu and A. M. Ionescu and C. Mart{\'{\i}}n-Vide},
  booktitle = {Proc. of 3rd International Conference Language and Automata
               Theory and Applications (LATA)},
  series    = {LNCS},
  volume    = {5457},
  publisher = {Springer},
  year      = {2009},
  pages     = {554-565},
  doi       = {10.1007/978-3-642-00982-2_47}
}