Počet záznamů: 1

Bounded Number of Parallel Productions in Scattered Context Grammars with Three Nonterminals

  1. 1.
    0345656 - MU-W 2011 RIV NL eng J - Článek v odborném periodiku
    Masopust, Tomáš
    Bounded Number of Parallel Productions in Scattered Context Grammars with Three Nonterminals.
    Fundamenta Informaticae. Roč. 99, č. 4 (2010), s. 473-480 ISSN 0169-2968
    Výzkumný záměr: CEZ:AV0Z10190503
    Klíčová slova: Scattered context grammars * parallel productions * descriptional complexity * generative power
    Kód oboru RIV: BA - Obecná matematika
    Impakt faktor: 0.522, rok: 2010
    http://iospress.metapress.com/content/f883562g5j612614/?issue=4&genre=article&spage=473&issn=0169-2968&volume=99

    Scattered context grammars with three nonterminals are known to be computationally complete. So far, however, it was an open problem whether the number of parallel productions can be bounded along with three nonterminals. In this paper, we prove that every recursively enumerable language is generated by a scattered context grammar with three nonterminals and five parallel productions, each of which simultaneously rewrites no more than nine nonterminals.
    Trvalý link: http://hdl.handle.net/11104/0186871
    Název souboruStaženoVelikostKomentářVerzePřístup
    Masopust4.pdf171 KBVydavatelský postprintvyžádat