ON THE SIZE OF BINARY DECISION DIAGRAMS REPRESENTING BOOLEAN FUNCTIONS

We consider the size of the representation of Boolean functions by sev eral classes of binary decision diagrams (BDDs) (also called branching programs), namely the classes of arbitrary BDDs of real time BDD (RBD D) (i.e, BDDs where each computation path is limited to the number of variables), of free BDDs (FBDDs) (also called read-once-only branching programs), of ordered BDDs (OBDDS) i.e. FBDDs where variables are tes ted in the same order along all paths), and binary decision trees (BDT s). Using well-known techniques, we first establish asymptotically sha rp bounds as a function of n on the minimum size of arbitrary BDDs rep resenting almost all Boolean functions of n variables and provide asym ptotic lower and upper bounds, differing only by a factor of two, on t he minimum size OBDDs representing almost all Boolean functions of n v ariables. We then, using a method to obtain exponential lower bounds o n complexity of computation of Boolean functions by RBDD, FBDD and OBD D that originated in (Breitbart, 1968), present the highest such bound s to date and also present improved bounds on the relative economy of description of particular Boolean functions by the above classes of BD Ds. For each nontrivial pair of BDD classes considered, we exhibit inf inite families of Boolean functions representable much more concisely by BDDs in one class than by BDDs in the other.