A Hierarchy Result for Read-Once Branching Programs with Restricted Parity Nondeterminism

0405528 - UIVT-O 330906 RIV NL eng J - Článek v odborném periodiku
Savický, Petr - Sieling, D.
A Hierarchy Result for Read-Once Branching Programs with Restricted Parity Nondeterminism.
[Výsledek o hierarchii pro read-once rozhodovací diagramy s omezeným nedeterminismem paritního typu.]
Theoretical Computer Science. Roč. 340, č. 3 (2005), s. 594-605. ISSN 0304-3975. E-ISSN 1879-2294
Grant CEP: GA MŠMT LN00A056
Výzkumný záměr: CEZ:AV0Z10300504
Klíčová slova: read-once branching programs * restricted parity nondeterminism * lower bounds on complexity * hierarchy
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 0.743, rok: 2005

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.

Omezené rozhodovací diagramy jsou ve výpočtové složitosti zkoumány s cílem zkoumat prostorovou složitost sekvenčních výpočtů a v aplikacích jako datová struktura pro reprezentci Booleovských funkcí. V tomto článku jsou zkoumány (parity,k)-rozhodovací diagramy a (disjunktion,k)-rozhodovací diagramy, tj. rozhodovací diagramy začínající paritním nebo disjunktivním uzlem stupně k, jehož následníci jsou tvořeny k read-once rozhodovacími diagramy. Tento model je motivován studiem síly nedeterminismu v rozhodovacích diagramech jak z hlediska výpočtové složitosti tak z hlediska datových struktur. Jsou prezentovány metody pro dolní odhady a výsledek o hierarchii polynomiálně velkých (parity,k)-rozhodovacích diagramů a (disjunktion,k)-rozhodovacích diagramů vzhledem k parametru k.
Trvalý link: http://hdl.handle.net/11104/0125686