VARIABLE ORDERINGS AND THE SIZE OF OBDDS FOR RANDOM PARTIALLY SYMMETRICAL BOOLEAN FUNCTIONS

The size of ordered binary decision diagrams (OBDDs) strongly depends on the chosen variable ordering. It is an obvious heuristic to use sym metric variable orderings, i.e., variable orderings where symmetric va riables are arranged adjacently. In order to evaluate this heuristic, methods for estimating the OBDD size for random partially symmetric fu nctions are presented. Characterizations of cases where, with high pro bability, only symmetric variable orderings and, with high probability , only nonsymmetric variable orderings lead to minimum OBDD size are o btained. For this analysis estimates for the number of different block s of random Boolean matrices are used. (C) 1998 John Wiley & Sons, Inc . Random Struct. Alg., 13, 49-70, 1998.