Publication Details

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

MASOPUST, T. A Note on the Generative Power of Some Simple Variants of Context-Free Grammars Regulated by Context Conditions. In LATA 2009 proceedings. Lecture Notes in Computer Science. Lecture notes in computer science. Springer-Verlag Berlin Heidelberg: Springer Verlag, 2009. p. 554-565. ISBN: 978-3-642-00981-5. ISSN: 0302-9743.
Czech title
O generativní síle několika jednoduchých variant bezkontextových gramatik s kontextovými podmínkami
Type
conference paper
Language
English
Authors
Masopust Tomáš, doc. RNDr., Ph.D. (CM-SFE)
URL
Keywords

Formal languages; context condition; context-free grammar; random context grammar; semi-conditional grammar; simple semi-conditional grammar; erasing production; generative power.

Abstract

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.

Published
2009
Pages
554–565
Journal
Lecture Notes in Computer Science, vol. 2009, no. 5457, ISSN 0302-9743
Proceedings
LATA 2009 proceedings
Series
Lecture notes in computer science
ISBN
978-3-642-00981-5
Publisher
Springer Verlag
Place
Springer-Verlag Berlin Heidelberg
UT WoS
000265784300047
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",
  booktitle="LATA 2009 proceedings",
  year="2009",
  series="Lecture notes in computer science",
  journal="Lecture Notes in Computer Science",
  volume="2009",
  number="5457",
  pages="554--565",
  publisher="Springer Verlag",
  address="Springer-Verlag Berlin Heidelberg",
  isbn="978-3-642-00981-5",
  issn="0302-9743",
  url="http://grammars.grlmc.com/LATA2009/"
}
Back to top