Počet záznamů: 1
Bounded Number of Parallel Productions in Scattered Context Grammars with Three Nonterminals
- 1.
SYSNO ASEP 0345656 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 Bounded Number of Parallel Productions in Scattered Context Grammars with Three Nonterminals Tvůrce(i) Masopust, Tomáš (MU-W) RID, ORCID, SAI Zdroj.dok. Fundamenta Informaticae. - : IOS Press - ISSN 0169-2968
Roč. 99, č. 4 (2010), s. 473-480Poč.str. 8 s. Jazyk dok. eng - angličtina Země vyd. NL - Nizozemsko Klíč. slova Scattered context grammars ; parallel productions ; descriptional complexity ; generative power Vědní obor RIV BA - Obecná matematika CEZ AV0Z10190503 - MU-W (2005-2011) UT WOS 000279638200005 EID SCOPUS 77954729583 DOI 10.3233/FI-2010-258 Anotace 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. 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