Detail publikace
A Note on the Generative Power of Some Simple Variants of Context-Free Grammars Regulated by Context Conditions
Formal languages; context condition; context-free grammar; random context grammar; semi-conditional grammar; simple semi-conditional grammar; erasing production; generative power.
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ů.
@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/"
}