book · 1997
An implicit formulation for exact BDD minimization of incompletely specified functions
See where this sits in the topic map →Summary AI-generated
- TL;DR
- This paper addresses the problem of binary decision diagram (BDD) minimization when working with incompletely specified functions and don't care sets.
- Problem
- Given an incompletely specified function and a fixed variable ordering, finding a function cover that yields a BDD of minimum size is proven to be an NP-complete problem.
- Method
- The authors propose an exact algorithm that formulates the BDD minimization problem as a binate covering problem.
- Results
- The problem can be effectively solved using implicit enumeration techniques similar to those used in the reduction of incompletely specified finite state machines.
- Contributions
- An exact algorithm and implicit formulation for BDD minimization of incompletely specified functions under a fixed variable ordering.
- Limitations
- Not specified in the abstract.
- Takeaways
- Exact BDD minimization with don't care sets can be translated into a binate covering problem and solved via implicit enumeration.
- Applications
- Not specified in the abstract.
- Topics
- Not specified in the abstract.
- For industry
- Not specified in the abstract.
- Why it matters
- Not specified in the abstract.
Abstract
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.