Bound-Set Preserving ROB DD Variable Orderings May Not Be Optimum.

This paper reports a result concerning the relation between the best variable orderings of an FIOBDD Gj and the decomposition structure of the Boolean function f represented by Gj. It was stated in [1] that, if f has a decomposition of type f(X) = g(h1(Y1), h2(Y2), … , hk(Yk)), where (Y1), i ϵ (1, 2, … ,k), is a partition of X, then one of the orderings which keeps the variables within the sets (Yi) adjacent is a best ordering for Gj. Using a counterexample, we show that this statement is incorrect. [ABSTRACT FROM AUTHOR]