.png){kind=icon}
.png){kind=icon}
Return
Strategies for solving the Boolean satisfiability problem using binary decision diagrams
.png){kind=icon}
PRE
AI
DOI：10.1016/S1383-7621(01)00011-X.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The Boolean satisfiability (SAT) problem is the problem of finding a solution to the equation f = 1, where f is a Boolean formula to be satisfied. Binary decision diagrams (BDDs) have been widely used to solve this problem; each of the individual output requirements of a multiple-output function is represented as a BDD and the conjunction of these requirements (product BDD) provides all satisfying solutions. However, these techniques suffer from BDD size explosion problems. This paper presents two BDD-based algorithms to solve the SAT problem that attempt to contain the growth of BDD size while identifying solutions quickly. The first algorithm, called BSAT, is a recursive, backtracking algorithm that uses an exhaustive search to find a SAT solution. It exploits the well-known unate recursive paradigm to reduce the effective size of search space for the SAT problem. We recursively apply orthonormal expansion on highly binate functions that may eventually lead to unate cofactors. The second algorithm, called IS-USAT (for INCOMPLETE-SEARCH-USAT), incorporates an incomplete search to find a solution. The search is incomplete inasmuch as it is restricted to only those regions that have a high likelihood of containing the solution, discarding the rest. Using our techniques we were able to find SAT solutions not only for all MCNC and ISCAS benchmarks, but also for a variety of industry standard designs, solutions for many of which could not be found by contemporary BDD-based SAT techniques. (C) 2001 Elsevier Science B.V. All rights reserved.
Keywords:
Boolean satisfiability
Unate and binate functions
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
4.1
Papers:
3.0K
Citations:
4.2K
Organization
No organization information available