Počet záznamů: 1
Left-forbidding cooperating distributed grammar systems
- 1.
SYSNO ASEP 0346740 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název Left-forbidding cooperating distributed grammar systems Tvůrce(i) Goldefus, F. (CZ)
Masopust, Tomáš (MU-W) RID, ORCID, SAI
Meduna, A. (CZ)Zdroj.dok. Theoretical Computer Science. - : Elsevier - ISSN 0304-3975
Roč. 411, 40-42 (2010), s. 3661-3667Poč.str. 7 s. Jazyk dok. eng - angličtina Země vyd. NL - Nizozemsko Klíč. slova cooperating distributed grammar system ; cooperating derivation mode ; left-forbidding grammar ; generative power ; descriptional complexity Vědní obor RIV BA - Obecná matematika CEZ AV0Z10190503 - MU-W (2005-2011) UT WOS 000281942400012 EID SCOPUS 77956095170 DOI doi:10.1016/j.tcs.2010.06.010 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. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2011
Počet záznamů: 1