Branching programs are a well established computation model for Boolean functions, especially read-once branching programs have been studied intensively. In this paper the expressive power of nondeterministic read-once branching programs, more precisely the class of functions representable in polynomial size, is investigated. For that reason two restricted models of nondeterministic read-once branching programs are defined and a lower bound method is presented. Furthermore, the first exponential...
Branching programs are a well-established computation model for boolean functions, especially read-once branching programs (BP1s) have been studied intensively. Recently two restricted nondeterministic (parity) BP1 models, called nondeterministic (parity) graph-driven BP1s and well-structured nondeterministic (parity) graph-driven BP1s, have been investigated. The consistency test for a BP-model is the test whether a given BP is really a BP of model . Here it is proved that the consistency test...
Branching programs are a well-established computation model for boolean functions,
especially read-once branching programs (BP1s) have been studied intensively.
Recently two restricted nondeterministic (parity)
BP1 models,
called nondeterministic (parity) graph-driven BP1s and well-structured
nondeterministic (parity) graph-driven BP1s,
have been investigated. The consistency test for a BP-model is the test
whether a given BP is really a BP of model .
Here it is proved that the consistency...
Branching programs are a well established computation model for
Boolean functions, especially read-once branching programs have
been studied intensively.
In this paper the expressive power of nondeterministic read-once branching
programs, more precisely the class of functions
representable in polynomial size, is investigated.
For that reason two restricted models of nondeterministic read-once
branching programs are defined and a lower bound method is presented.
Furthermore, the first exponential...
Ordered binary decision diagrams (OBDDs) and several more general BDD models
have turned out to be representations of Boolean functions which are useful
in applications like verification, timing analysis, test pattern generation or
combinatorial optimization.
The hidden weighted bit function (HWB) is of particular interest, since it
seems to be the simplest function with exponential OBDD size.
The complexity of this function with respect to different circuit models,
formulas, and various...
Download Results (CSV)