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
Pages:783-793
Book:Acta Cybernetica
Place:Szeged, HU
Year:2008
Journal:Acta Cybernetica, Vol. 18, No. 4, US
ISSN:0324-721X
URL:http://www.inf.u-szeged.hu/actacybernetica/edb/vol18n4/Masopust_2008_ActaCybernetica.xml [HTML]
Keywords
scattered context grammar, grammatical generalization, derivation restriction, generative power.
Annotation
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.
BibTeX:
@ARTICLE{
   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 = {http://www.fit.vutbr.cz/research/view_pub.php?id=8546}
}

Your IPv4 address: 50.16.97.96
Switch to IPv6 connection

DNSSEC [dnssec]