Almost the same types of restricted branching programs (or binary decision diagrams BDDs) are considered in complexity theory and in applications like hardware verification. These models are read-once branching programs (free BDDs) and certain types of oblivious branching programs (ordered and indexed BDDs with k layers). The complexity of the ... more >>>

In unrestricted branching programs all variables may be tested arbitrarily often on each path. But exponential lower bounds are only known, if on each path the number of tests of each variable is bounded (Borodin, Razborov and Smolensky (1993)). We examine branching programs in which for each path the number ... more >>>