Title :
On the complexity of minimizing the OBDD size for incompletely specified functions
Author :
Sauerhoff, Martin ; Wegener, Ingo
Author_Institution :
Fachbereich Inf., Dortmund Univ., Germany
fDate :
11/1/1996 12:00:00 AM
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 :
Boolean functions; computational complexity; decision theory; minimisation; NP-complete problem; OBDD size minimization; approximation algorithm; circuit CAD; complexity; incompletely specified Boolean function; ordered binary decision diagram; sequential machine verification; Approximation algorithms; Automata; Binary decision diagrams; Boolean functions; Circuits; Data structures; Heuristic algorithms; Minimization; Polynomials;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
