On the complexity of minimizing the OBDD size for incompletely specified functions
Open Access
- 1 November 1996
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 15 (11) , 1435-1437
- https://doi.org/10.1109/43.543775
Abstract
The problem of constructing an OBDD cover of minimal size for an incompletely specified Boolean function arises in several applications in the CAD domain, e.g., the verification of sequential machines and the construction of OBDD's for incompletely specified circuits. The complexity of this problem is determined. The decision problem is NP-complete. Efficient approximation algorithms exist only if NP=P.Keywords
This publication has 5 references indexed in Scilit:
- Minimizing ROBDD size of incompletely specified multiple output functionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- New techniques for efficient verification with implicitly conjoined BDDsPublished by Association for Computing Machinery (ACM) ,1994
- Heuristic minimization of BDDs using don't caresPublished by Association for Computing Machinery (ACM) ,1994
- Graph-Based Algorithms for Boolean Function ManipulationIEEE Transactions on Computers, 1986
- State Reduction in Incompletely Specified Finite-State MachinesIEEE Transactions on Computers, 1973