Simple restriction in context-free rewriting

MASOPUST, Tomáš. Simple restriction in context-free rewriting. Journal of Computer and System Sciences. Elsevier, 2010, roč. 76, č. 8, s. 837-846. ISSN 0022-0000.

Základní údaje

Originální název

Simple restriction in context-free rewriting

Autoři

MASOPUST, Tomáš

Vydání

Journal of Computer and System Sciences, Elsevier, 2010, 0022-0000

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Česká republika

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL

Impakt faktor

Impact factor: 1.631

Označené pro přenos do RIV

Ne

Organizační jednotka

Fakulta informatiky

UT WoS

000281501900010

Klíčová slova anglicky

Formal languages; Context-free grammar; Rewriting system; Derivation restriction; Generative power

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

Many rewriting systems with context-free productions and with controlled derivations have been studied. On one hand, these systems preserve the simplicity of applications of context-free productions and, on the other hand, they increase the generative power to cover more aspects of natural and programming languages. However, with erasing productions, many of these systems are computationally complete. It gives rise to a natural question of what are the simplest restrictions of the derivation process of context-free grammars to obtain the universal power. In this paper, we present such a simple restriction introducing so-called restricted context-free rewriting systems. These systems are context-free grammars with a function assigning a nonterminal coupled with + or - to each nonterminal. A production is applicable if it is applicable as a context-free production and if the symbol assigned to the left-hand side of the production is coupled with +, then this symbol has to appear in the sentential form, while if coupled with -, it must not appear in the sentential form. This restriction is simpler than most of the other restrictions, since the context conditions are assigned to nonterminals, not to productions, and their type is the simplest possible -- a nonterminal.