We develop a theory of communication within branching
programs that provides exponential lower bounds on the
size of branching programs that are bounded
alternating. Our theory is based on the algebraic
concept of ω-branching programs, `ω :
Nhskip-3.7mm Ilongrightarrow R` semiring
homomorphism, that generalizes ordinary branching
programs, ω-branching programs and
MODp-branching programs. Due to certain exponential
lower and polynomial upper bounds on the size of
bounded alternating ω-branching programs we are
able to separate the corresponding classical complexity
clases cal NLba, co-cal NLba, `opluscal
L_ba, MOD_p-cal L_ba, p` prime, from each other,
and from that classes corresponding to oblivious linear
length-bounded branching programs investigated in the
past.
