Journal article

MASOPUST Tomáš, MEDUNA Alexander and ŠIMÁČEK Jiří. Two Power-Decreasing Derivation Restrictions in Generalized Scattered Context Grammars. Acta Cybernetica. 2008, vol. 18, no. 4, pp. 783-793. ISSN 0324-721X.
Publication language:english
Original title:Two Power-Decreasing Derivation Restrictions in Generalized Scattered Context Grammars
Title (cs):Dvě omezení snižující sílu zobecněných gramatik s rozptýleným kontextem
Book:Acta Cybernetica
Place:Szeged, HU
Journal:Acta Cybernetica, Vol. 18, No. 4, US
scattered context grammar, grammatical generalization, derivation restriction, generative power.
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.
   author = {Tom{\'{a}}{\v{s}} Masopust and Alexander Meduna and
	Ji{\v{r}}{\'{i}} {\v{S}}im{\'{a}}{\v{c}}ek},
   title = {Two Power-Decreasing Derivation Restrictions in Generalized
	Scattered Context Grammars},
   pages = {783--793},
   booktitle = {Acta Cybernetica},
   journal = {Acta Cybernetica},
   volume = {18},
   number = {4},
   year = {2008},
   location = {Szeged, HU},
   ISSN = {0324-721X},
   language = {english},
   url = {}

Your IPv4 address:
Switch to IPv6 connection

DNSSEC [dnssec]