Počet záznamů: 1

Left-forbidding cooperating distributed grammar systems

  1. 1.
    0346740 - MU-W 2011 RIV NL eng J - Článek v odborném periodiku
    Goldefus, F. - Masopust, Tomáš - Meduna, A.
    Left-forbidding cooperating distributed grammar systems.
    Theoretical Computer Science. Roč. 411, 40-42 (2010), s. 3661-3667 ISSN 0304-3975
    Výzkumný záměr: CEZ:AV0Z10190503
    Klíčová slova: cooperating distributed grammar system * cooperating derivation mode * left-forbidding grammar * generative power * descriptional complexity
    Kód oboru RIV: BA - Obecná matematika
    Impakt faktor: 0.838, rok: 2010
    http://www.sciencedirect.com/science/article/pii/S0304397510003440

    A left-forbidding grammar, introduced in this paper, is a context-free grammar, where a set of nonterminal symbols is attached to each context-free production. Such a production can rewrite a nonterminal provided that no symbol from the attached set occurs to the left of the rewritten nonterminal in the current sentential form. The present paper discusses cooperating distributed grammar systems with left-forbidding grammars as components and gives some new characterizations of language families of the Chomsky hierarchy. In addition, it also proves that twelve nonterminals are enough for cooperating distributed grammar systems working in the terminal derivation mode with two left-forbidding components (including erasing productions) to characterize the family of recursively enumerable languages.
    Trvalý link: http://hdl.handle.net/11104/0187681
    Název souboruStaženoVelikostKomentářVerzePřístup
    Masopust1.pdf2301.3 KBVydavatelský postprintvyžádat