GOLDEFUS, Filip, Tomáš MASOPUST a Alexander MEDUNA. Left-forbidding cooperating distributed grammar systems. Theoretical Computer Science. Amsterdam, North Holland: Elsevier Science Publishers, 2010, roč. 411, 40-42, s. 3661-3667. ISSN 0304-3975.
Další formáty:   BibTeX LaTeX RIS
Základní údaje
Originální název Left-forbidding cooperating distributed grammar systems
Autoři GOLDEFUS, Filip, Tomáš MASOPUST a Alexander MEDUNA.
Vydání Theoretical Computer Science, Amsterdam, North Holland, Elsevier Science Publishers, 2010, 0304-3975.
Další údaje
Originální jazyk angličtina
Typ výsledku Článek v odborném periodiku
Obor 10201 Computer sciences, information science, bioinformatics
Stát vydavatele Česká republika
Utajení není předmětem státního či obchodního tajemství
WWW URL
Impakt faktor Impact factor: 0.838
Organizační jednotka Fakulta informatiky
UT WoS 000281942400012
Klíčová slova anglicky Cooperating distributed grammar system; Cooperating derivation mode; Left-forbidding grammar; Generative power; Descriptional complexity
Příznaky Mezinárodní význam, Recenzováno
Změnil Změnil: doc. RNDr. Tomáš Masopust, Ph.D., DSc., učo 4030. Změněno: 25. 10. 2010 14:21.
Anotace
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.
VytisknoutZobrazeno: 12. 6. 2024 02:54