Two power-decreasing derivation restrictions in generalized scattered context grammars

Masopust, Tomáš; Meduna, Alexander; Šimácek, Jiří: Two power-decreasing derivation restrictions in generalized scattered context grammars. Acta cybernetica, (18) 4. pp. 783-793. (2008)

[img] Cikk, tanulmány, mű
Masopust_2008_ActaCybernetica.pdf

Letöltés (146kB)

Absztrakt (kivonat)

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.

Mű típusa: Cikk, tanulmány, mű
Befoglaló folyóirat/kiadvány címe: Acta cybernetica
Kötet/évfolyam: 18
Szám: 4
ISSN: 0324-721X
Nyelv: angol
Rovatcím: Regular papers
Kulcsszavak: Természettudomány, Informatika
Megjegyzések: Bibliogr.: p. 792-793.; Abstract
A feltöltés ideje: 2016. okt. 15. 12:25
Utolsó módosítás: 2018. jún. 05. 14:51
URI: http://acta.bibl.u-szeged.hu/id/eprint/12847
Bővebben:
Tétel nézet Tétel nézet