From the title of this monograph, one may easily infer its subject matter. Briefly, a Branching Program (BP) (or a Binary Decision Diagram (BDD)) that represents a Boolean function B_n is specified by a Boolean variable set X_n = {x_1,...,x_n} and a directed acyclic graph G = (V, A). The inner nodes of G get labels from X_n and the sinks get labels from {0, 1}. Each inner node has out-degree two with one edge labeled 0 and the other labeled 1. (The sinks have out-degree zero.) Each node v ∈ V represents a Boolean function function f_v as follows: for an input string a ∈ {0, 1}~n, f_v(a) equals the value of the sink reached by following the path in G that begins at node v and traverses along the edges labeled by the value of a_i leaving the node(s) labeled by x_i. That is, each input a ∈ {0, 1}~n activates the a_i-edge leaving every x_i-node so that, for any v ∈ V, f_v(a) equals the label of the sink reached by following the activated path starting at node v. The investigations into BPs and BDDs had for many years proceeded independently by theoreticians and practitioners, respectively. Theoreticians studied BPs as restricted computational models in the hope of proving lower bounds on explicitly defined Boolean functions. On the other hand, (computer science) practitioners were largely motivated by the development of efficient data structures for Boolean functions, particularly ones that balance the need for efficient algorithms for various operations and the space required to store the structure in memory.
展开▼
