Number of the records: 1
A Hierarchy Result for Read-Once Branching Programs with Restricted Parity Nondeterminism
- 1.0405528 - UIVT-O 330906 RIV NL eng J - Journal Article
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
R&D Projects: GA MŠMT LN00A056
Institutional research plan: CEZ:AV0Z10300504
Keywords : read-once branching programs * restricted parity nondeterminism * lower bounds on complexity * hierarchy
Subject RIV: BA - General Mathematics
Impact factor: 0.743, year: 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.
Permanent Link: http://hdl.handle.net/11104/0125686
Number of the records: 1