A new algorithm for the binate covering problem and its application to the minimization of Boolean relations
- 1 January 1992
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
The binate covering problem (BCP) is the problem of finding a minimum cost assignment to variables that is a solution of a Boolean equation f=1. It is a generalization of the set covering (or unate covering) problem, where f is positive unate, and is generally given as a table with rows corresponding to the set elements and the columns corresponding to the subsets. Previous methods have considered the case when f is given as a product-of-sum formula or as a binary decision diagram (BDD). A branch-and-bound algorithm for the BCP that assumes f is expressed as the conjunction of multiple BDDs is presented. The BCP solver that has been implemented can be applied to several problems, including exact minimization of Boolean relations, for which results are presented. It has been possible to solve large, difficult problems (up to 4692 variables) which could not be solved by the product of sum based method.Keywords
This publication has 12 references indexed in Scilit:
- An exact minimizer for Boolean relationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Variable ordering and selection of FSM traversalPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Exact and heuristic algorithms for the minimization of incompletely specified state machinesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Minimization of symbolic relationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- An iterative algorithm for the binate covering problemPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Universal logic design algorithm and its application to the synthesis of two-level switching circuitsIEE Proceedings E Computers and Digital Techniques, 1989
- Multiple-Valued Minimization for PLA OptimizationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1987
- Graph-Based Algorithms for Boolean Function ManipulationIEEE Transactions on Computers, 1986
- A Method for Minimizing the Number of Internal States in Incompletely Specified Sequential NetworksIEEE Transactions on Electronic Computers, 1965
- Minimization of Boolean Functions*Bell System Technical Journal, 1956