Počet záznamů: 1
A Hierarchy Result for Read-Once Branching Programs with Restricted Parity Nondeterminism
- 1.
SYSNO ASEP 0405528 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 A Hierarchy Result for Read-Once Branching Programs with Restricted Parity Nondeterminism Překlad názvu Výsledek o hierarchii pro read-once rozhodovací diagramy s omezeným nedeterminismem paritního typu Tvůrce(i) Savický, Petr (UIVT-O) SAI, RID, ORCID
Sieling, D. (DE)Zdroj.dok. Theoretical Computer Science. - : Elsevier - ISSN 0304-3975
Roč. 340, č. 3 (2005), s. 594-605Poč.str. 12 s. Jazyk dok. eng - angličtina Země vyd. NL - Nizozemsko Klíč. slova read-once branching programs ; restricted parity nondeterminism ; lower bounds on complexity ; hierarchy Vědní obor RIV BA - Obecná matematika CEP LN00A056 GA MŠMT - Ministerstvo školství, mládeže a tělovýchovy CEZ AV0Z10300504 - UIVT-O (2005-2011) UT WOS 000231662700007 EID SCOPUS 23844433375 DOI 10.1016/j.tcs.2005.03.016 Anotace Restricted branching programs are considered in complexity theory in order to study the space complexity of sequential computations and in applications as a data structure for Boolean functions. In this paper (parity,k)-branching programs and (disjunction,k)-branching programs are considered, i.e., branching programs starting with a parity- (disjunction-)node with a fan-out of k whose successors are k read-once branching programs. This model is motivated by the investigation of the power of nondeterminism in branching programs and of similar variants that have been considered as a data structure. Lower bound methods and hierarchy results for polynomial size (parity,k)- and (disjunction,k)-branching programs with respect to k are presented. Pracoviště Ústav informatiky Kontakt Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800 Rok sběru 2006
Počet záznamů: 1