Počet záznamů: 1
Simple restriction in context-free rewriting
- 1.0346739 - MÚ 2011 RIV US eng J - Článek v odborném periodiku
Masopust, Tomáš
Simple restriction in context-free rewriting.
Journal of Computer and System Sciences. Roč. 76, č. 8 (2010), s. 837-846. ISSN 0022-0000. E-ISSN 1090-2724
Výzkumný záměr: CEZ:AV0Z10190503
Klíčová slova: formal languages * context-free grammar * rewriting system * derivation restriction * generative power
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 1.631, rok: 2010
http://www.sciencedirect.com/science/article/pii/S0022000010000437
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 λ-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.
Trvalý link: http://hdl.handle.net/11104/0187680
Název souboru Staženo Velikost Komentář Verze Přístup Masopust3.pdf 2 216.8 KB Vydavatelský postprint vyžádat
Počet záznamů: 1