Wegener I. Branching Programs and Binary Decision Diagrams. Theory and Applications

Society for Industrial and Applied Mathematics, 2000, -419 p.Research on the complexity of Boolean functions has a more than fifty-year-old history. For a long time, research has been focused on circuits and the circuit complexity of Boolean functions. The open problems in circuit complexity are now so hard that not much progress has been made during the past 10 years. However, many new results have been obtained on the communication complexity of Boolean functions and on branching programs (BPs) and binary decision diagrams (BDDs) (which are synonyms) representing Boolean functions. The theory of communication complexity has been described by Kushilevitz and Nisan (1997) and Hromkovic (1997) and now seems to be the right time to present a comprehensive monograph on all aspects of BPs and BDDs including theory and applications.
Theoretical research on BPs has been motivated mainly by relations between their size and the space complexity of Turing machines and, in particular, by the general aim to develop lower bound techniques. Applications of restricted variants of BDDs as data structures or representation types for Boolean functions have led to many new, important, and interesting problems. There is a trade-off between the size of the class of functions representable in polynomial size by some variant of BDDs and the difficulty or complexity of performing operations on the representations. Hence, one has to compare the various representation types. For this reason, upper and lower bound techniques are developed and the representation size of important and selected functions is estimated. Moreover, simulations between the representation types are investigated. For a list of essential operations, one looks for efficient algorithms or proofs showing that they are inherently difficult. The applications of such representations of Boolean functions are manifold: verification; automata theory; model checking; further CAD applications such as synthesis, simulation, test generation, timing analysis, and technology mapping; and applications in optimization algorithms for, e.g., integer programming and network flow, combinatorics, and genetic programming.
The aim of this monograph is to present state-of-the-art knowledge on BPs and BDDs. Before typical applications are discussed, the complexity theoretical and algorithmic properties of various types of BPs and BDDs are investigated.BPs and Decision Trees (DTs)
Ordered Binary Decision Diagrams (OBDDs)
The OBDD Size of Selected Functions
The Variable-Ordering Problem
Free BDDs (FBDDs) and Read-Once BPs
BDDs with Repeated Tests
Decision Diagrams (DDs) Based on Other Decomposition Rules
Integer-Valued DDs
Nondeterministic DDs
Randomized BDDs and Algorithms
Summary of the Theoretical Results
Applications in Verification and Model Checking
Further CAD Applications
Applications in Optimization, Counting, and Genetic Programming