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, Lecture Notes in Computer Science 5457. Tarragona, Spain, 2009, s. 554-565. ISSN 0302-9743.

Základní údaje

• Originální název: A Note on the Generative Power of Some Simple Variants of Context-Free Grammars Regulated by Context Conditions
• Název česky: O generativní síle několika jednoduchých variant bezkontextových gramatik s kontextovými podmínkami
• Autoři: MASOPUST, Tomáš.
• Vydání: Tarragona, Spain, LATA 2009, Lecture Notes in Computer Science 5457, od s. 554-565, 2009.

Další údaje

• Typ výsledku: Stať ve sborníku
• Utajení: není předmětem státního či obchodního tajemství
• WWW: URL
• Impakt faktor: Impact factor: 0.402 v roce 2005
• Organizační jednotka: Fakulta informatiky
• ISSN: 0302-9743
• UT WoS: 000265784300047
• Klíčová slova anglicky: Formal languages; context condition; context-free grammar; random context grammar; semi-conditional grammar; simple semi-conditional grammar; erasing production; generative power.
• Štítky: context condition, context-free grammar, erasing production, formal languages, generative power., random context grammar, semi-conditional grammar, simple semi-conditional grammar
• Příznaky: Mezinárodní význam, Recenzováno

Anotace

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.

Anotace česky

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ů.