Detail publikace

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

Originální název

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

Anglický název

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

Jazyk

en

Originální abstrakt

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.

Anglický abstrakt

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.

BibTex


@inproceedings{BUT33771,
  author="Tomáš {Masopust}",
  title="A Note on the Generative Power of Some Simple Variants of Context-Free Grammars Regulated by Context Conditions",
  annote="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.",
  address="Springer Verlag",
  booktitle="LATA 2009 proceedings",
  chapter="33771",
  edition="Lecture notes in computer science",
  howpublished="print",
  institution="Springer Verlag",
  journal="Lecture Notes in Computer Science (IF 0,513)",
  number="5457",
  year="2009",
  month="january",
  pages="554--565",
  publisher="Springer Verlag",
  type="conference paper"
}