Minimizing ROBDD size of incompletely specified multiple output functions

The size of ROBDD is essential in many applications. In this paper we propose a heuristic that minimizes ROBDD size for incompletely specified multiple output functions. Our technique involves giving a new interpretation of ROBDDs with an extra variable, Z for incompletely specified functions. This new interpretation allows us to assign don´t cares to either the on-set or the off-set yielding an efficient minimization of ROBDD size. The extra variable Z carries the information of the don´t cares and preserves the flexibility of choosing the best cover for a given incompletely specified function. Starting from the top level of an ROBDD, we minimize greedily the number of nodes at every level by assigning as few don´t cares as possible to either the on-set or the off-set. We propagate the remaining unused don´t cares to lower levels of an ROBDD by moving the extra variable downwards. We performed three sets of experiments. The results are very encouraging.<>