Počet záznamů: 1  

Simple restriction in context-free rewriting

  1. 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 souboruStaženoVelikostKomentářVerzePřístup
    Masopust3.pdf2216.8 KBVydavatelský postprintvyžádat
     
Počet záznamů: 1  

  Tyto stránky využívají soubory cookies, které usnadňují jejich prohlížení. Další informace o tom jak používáme cookies.