Detail publikace

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

MASOPUST Tomáš. 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, roč. 2009. Springer-Verlag Berlin Heidelberg: Springer Verlag, 2009, s. 554-565. ISBN 978-3-642-00981-5. ISSN 0302-9743.
Název česky
O generativní síle několika jednoduchých variant bezkontextových gramatik s kontextovými podmínkami
Typ
článek ve sborníku konference
Jazyk
angličtina
Autoři
Masopust Tomáš, RNDr., Ph.D. (UIFS FIT VUT)
URL
Abstrakt

V článku jsou zodpovězeny tři otevřené problémy týkající se generativní síly několika variant bezkontextových gramatik regulovaných kontextovými podmínkami. Zejména je diskutována generativní sila tzv. bezkontextových polopodmínkových gramatik (jenž jsou random context gramatiky, kde povolující a zakazující množiny jsou nahrazeny povolujícími a zakazujícími řetězci), kde povolující a zakazující řetězce každého pravidla jsou délky nejvýše jedna, a jednoduchých polopodmínkových gramatik, kde navíc žádné pravidlo nemá přiřazen jak povolující, tak i zakazující řetězec. Konečně, článek také prezentuje několik normálních forem, přehled známých výsledků a otevřených problémů.

Rok
2009
Strany
554-565
Časopis
Lecture Notes in Computer Science, roč. 2009, č. 5457, ISSN 0302-9743
Sborník
LATA 2009 proceedings
Řada
Lecture notes in computer science
Konference
International Conference on Language and Automata Theory and Applications, Tarragona, ES
ISBN
978-3-642-00981-5
Vydavatel
Springer Verlag
Místo
Springer-Verlag Berlin Heidelberg, ES
UT WoS
000265784300047
BibTeX 
@INPROCEEDINGS{FITPUB8846,
   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 = "https://www.fit.vut.cz/research/publication/8846"
}
Nahoru