Přístupnostní navigace
E-přihláška
Vyhledávání Vyhledat Zavřít
Detail publikace
MASOPUST, T.
Originální název
A Note on the Generative Power of Some Simple Variants of Context-Free Grammars Regulated by Context Conditions
Typ
článek ve sborníku ve WoS nebo Scopus
Jazyk
angličtina
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.
Klíčová slova
Formal languages; context condition; context-free grammar; random context grammar; semi-conditional grammar; simple semi-conditional grammar; erasing production; generative power.
Autoři
Rok RIV
2009
Vydáno
3. 1. 2009
Nakladatel
Springer Verlag
Místo
Springer-Verlag Berlin Heidelberg
ISBN
978-3-642-00981-5
Kniha
LATA 2009 proceedings
Edice
Lecture notes in computer science
ISSN
0302-9743
Periodikum
Lecture Notes in Computer Science
Ročník
Číslo
5457
Stát
Spolková republika Německo
Strany od
554
Strany do
565
Strany počet
12
URL
http://grammars.grlmc.com/LATA2009/
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/" }