Počet záznamů: 1

Simple restriction in context-free rewriting

  1. 1.
    0346739 - MU-W 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
    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 souboruStaženoVelikostKomentářVerzePřístup
    Masopust3.pdf2216.8 KBVydavatelský postprintvyžádat