Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR01-017 | 14th February 2001 00:00

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

RSS-Feed




TR01-017
Authors: Petr Savicky, Detlef Sieling
Publication: 19th February 2001 14:37
Downloads: 3594
Keywords: 


Abstract:

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 (\oplus,k)-branching programs and (\vee,k)-branching
programs are considered, i.e., branching programs starting with a
\oplus- (or \vee-)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 (\oplus,k)- and (\vee,k)-branching programs
with respect to k are presented.



ISSN 1433-8092 | Imprint