Publication details
Two Power-Decreasing Derivation Restrictions in Generalized Scattered Context Grammars
| Authors | |
|---|---|
| Year of publication | 2008 |
| Type | Article in Periodical |
| Magazine / Source | Acta Cybernetica |
| MU Faculty or unit | |
| Citation | |
| Web | http://www.inf.u-szeged.hu/actacybernetica/edb/Author/MASOPUST-TOMAS.xml |
| Keywords | scattered context grammar, grammatical generalization, derivation restriction, generative power |
| Description | 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. |