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

• Originální 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í
• WWW: URL
• Impakt faktor: Impact factor: 1.631
• 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

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.