Přístupnostní navigace
E-přihláška
Vyhledávání Vyhledat Zavřít
Detail publikace
MASOPUST, T. GOLDEFUS, F. MEDUNA, A.
Originální název
Left-Forbidding Cooperating Distributed Grammar Systems
Typ
článek v časopise ve Scopus, Jsc
Jazyk
angličtina
Originální abstrakt
A left-forbidding grammar 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 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 with two left-forbidding components (including erasing productions) to characterize the family of all recursively enumerable languages.
Klíčová slova
Cooperating distributed grammar system, cooperating derivation mode, left-forbidding grammar, generative power, descriptional complexity.
Autoři
MASOPUST, T.; GOLDEFUS, F.; MEDUNA, A.
Rok RIV
2010
Vydáno
30. 4. 2010
Nakladatel
Elsevier Science
Místo
Paris
ISSN
0304-3975
Periodikum
Theoretical Computer Science
Ročník
411
Číslo
40
Stát
Nizozemsko
Strany od
3661
Strany do
3667
Strany počet
7
BibTex
@article{BUT50510, author="Tomáš {Masopust} and Filip {Goldefus} and Alexandr {Meduna}", title="Left-Forbidding Cooperating Distributed Grammar Systems", journal="Theoretical Computer Science", year="2010", volume="411", number="40", pages="3661--3667", doi="10.1016/j.tcs.2010.06.010", issn="0304-3975" }