Abstract of Paper

A Hierarchy Result for Read-Once Branching Programs with Restricted Parity Nondeterminism
by Petr Savicky, Detlef Sieling


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 for these variants of branching
programs are presented, which allow to prove even hierarchy results
for polynomial size $(\oplus,k)$- and $(\vee,k)$-branching programs
with respect to $k$.