Conference paper

MASOPUST Tomáš. A Note on the Generative Power of Some Simple Variants of Context-Free Grammars Regulated by Context Conditions. In: LATA 2009 proceedings. Springer-Verlag Berlin Heidelberg: Springer Verlag, 2009, pp. 554-565. ISBN 978-3-642-00981-5. ISSN 0302-9743.
Publication language:english
Original title:A Note on the Generative Power of Some Simple Variants of Context-Free Grammars Regulated by Context Conditions
Title (cs):O generativní síle několika jednoduchých variant bezkontextových gramatik s kontextovými podmínkami
Pages:554-565
Proceedings:LATA 2009 proceedings
Conference:International Conference on Language and Automata Theory and Applications
Series:Lecture notes in computer science
Place:Springer-Verlag Berlin Heidelberg, ES
Year:2009
ISBN:978-3-642-00981-5
Journal:Lecture Notes in Computer Science, Vol. 2009, No. 5457, DE
ISSN:0302-9743
Publisher:Springer Verlag
URL:http://grammars.grlmc.com/LATA2009/ [HTML]
Keywords
Formal languages; context condition; context-free grammar; random context grammar; semi-conditional grammar; simple semi-conditional grammar; erasing production; generative power.

Annotation
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{
   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},
   pages = {554--565},
   booktitle = {LATA 2009 proceedings},
   series = {Lecture notes in computer science},
   journal = {Lecture Notes in Computer Science},
   volume = {2009},
   number = {5457},
   year = {2009},
   location = {Springer-Verlag Berlin Heidelberg, ES},
   publisher = {Springer Verlag},
   ISBN = {978-3-642-00981-5},
   ISSN = {0302-9743},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php?id=8846}
}

Your IPv4 address: 54.224.187.45
Switch to IPv6 connection

DNSSEC [dnssec]