2008
Two Power-Decreasing Derivation Restrictions in Generalized Scattered Context Grammars
MASOPUST, Tomáš; Alexander MEDUNA a Jiří ŠIMÁČEKZákladní údaje
Originální název
Two Power-Decreasing Derivation Restrictions in Generalized Scattered Context Grammars
Název česky
Dvě omezení snižující sílu zobecněných gramatik s rozptýleným kontextem
Autoři
MASOPUST, Tomáš; Alexander MEDUNA a Jiří ŠIMÁČEK
Vydání
Acta Cybernetica, Szeged, University Szeged, 2008, 0324-721X
Další údaje
Typ výsledku
Článek v odborném periodiku
Utajení
není předmětem státního či obchodního tajemství
Odkazy
Organizační jednotka
Fakulta informatiky
Klíčová slova anglicky
scattered context grammar, grammatical generalization, derivation restriction, generative power
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 19. 12. 2008 15:54, doc. RNDr. Tomáš Masopust, Ph.D., DSc.
V originále
The present paper introduces and discusses generalized scattered context grammars that are based upon sequences of productions whose left-hand sides are formed by nonterminal strings, not just single nonterminals. It places two restrictions on the derivations in these grammars. More specifically, let k be a positive integer. The first restriction requires that all rewritten symbols occur within the first k symbols of the first continuous block of nonterminals in the sentential form during every derivation step. The other restriction defines derivations over sentential forms containing no more than k occurrences of nonterminals. As its main result, the paper demonstrates that both restrictions decrease the generative power of these grammars to the power of context-free grammars.
Česky
Článek zavádí a diskutuje zobecněné gramatiky s rozptýleným kontextem založené na sekvencích pravidel, jejichž levé strany jsou tvořeny řetězci neterminálů místo standardního jednoho neterminálu. Studovány jsou dvě omezení v těchto gramatikách. První omezení vyžaduje, aby se všechny přepisované symboly jakéhokoliv derivačního kroku vyskytovaly v prvních k symbolech prvního souvislého bloku neterminálů. Druhé pak definuje derivace, jejichž jednotlivé větné formy nemají více než k neterminálů. Hlavním výsledkem článku je, že obě omezení vedou ke snížení síly těchto gramatik na sílu bezkontextových gramatik.