An implicit formulation for exact BDD minimization of incompletely specified functions
Arlindo L. Oliveira, Luca P. Carloni, Tiziano Villa, Alberto Luigi Sangiovanni-Vincentelli · 1997
This paper addresses the problem of binary decision diagram (BDD) minimization in the presence of don’t care sets. Specifically, given an incompletely specified function g and a fixed ordering of the variables, we propose an exact algorithm for selecting f such that f is a cover for g and the binary decision diagram for f is of minimum size. We proved that this problem is NP-complete. Here we show that the BDD minimization problem can be formulated as a binate covering problem and solved using implicit enumeration techniques similar to the ones used in the reduction of incompletely specified finite state machines.