ABSTRACT
The Binary Decision Diagram (BDD) data structure can be viewed as an optimized representation of minimal deterministic finite-state automata (DFA) for Boolean function on-sets. For this idea to pay off in practice, the Boolean variables must be ordered as per their semantic correlation. This chapter provides an intuitive overview of what BDD algorithms end up doing. The representation and manipulation of Boolean functions is central to computing theory and practice. For pedagogical purposes, Boolean functions are commonly represented using truth-tables. The chapter demonstrates that for larger functions, with the right decoding order of the variables, BDDs (and minimal DFA) can indeed be far more compact. On the other hand, truth-tables are guaranteed to be exponential for any N-input Boolean function. BDDs exhibit another curious fact: their size tends to blow up during BDD manipulations. Measures such as dynamic reordering of the variables are often able to minimize many of these bloated BDDs.
