EFFICIENT ALGORITHMS FOR THE TRANSFORMATION BETWEEN DIFFERENT TYPES OF BINARY DECISION DIAGRAMS

The problem of transforming an FBDD (free binary decision diagram) P o n n variables or a pi'OBDD (ordered binary decision diagram with respe ct to the variable ordering pi') P for the Boolean function f into the reduced pi OBDD Q for f is considered. The algorithms run in time O(\ P\ \Q\ log \Q\) (where, e.g., \P\ is the size of P) and need space O(\ P\ + n . \Q\), if P may be an FBDD, or O(\P\ + \Q\), if P is known to be an OBDD. The problem is important for the improvement of given vari able orderings, e.g., by simulated annealing or genetic algorithms, an d in the situation where incompatible representations of functions hav e to be made compatible.