ASIG: An all-solution SAT solver for CNF formulas
Authors:
- 1 August 2009
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 508-513
Abstract
An all-solution Boolean satisfiability (SAT) solver aims to find all the satisfying assignments. In this paper, we introduce ASIG, an all-solution solver for satisfiability problems. ASIG operates on conjunctive normal forms (CNFs) instead of circuits or hybrid representations as most other all-solution solvers did. ASIG prevents the same solution from being found again by creating a blocking clause from a solution and adding it into the clause database. To ensure efficiency, ASIG embeds an incremental mechanism into zchaff to avoid starting search from scratch in searching for a new solution. ASIG also implements some other blocking clause management strategies such as earlier termination and blocking clause merging to further improve efficiency. All our work is tested and analyzed on a set of CNF benchmarks.Keywords
This publication has 9 references indexed in Scilit:
- EHSATProceedings of the 39th conference on Design automation - DAC '02, 2007
- Integrating Observability Don't Cares in All-Solution SAT Solvers2006
- How many solutions does a SAT instance have?2004
- SAT-based algorithms for logic minimization2004
- Satisfiability-Based Algorithms for Boolean OptimizationAnnals of Mathematics and Artificial Intelligence, 2004
- SAT-based unbounded symbolic model checking2003
- Symbolic model checking using SAT procedures instead of BDDs2003
- Applying SAT Methods in Unbounded Symbolic Model Checking2002
- Test pattern generation using Boolean satisfiabilityIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1992