Partition-based decision heuristics for image computation using SAT and BDDs
Authors:
- Zijiang YangZYZijiang Yang
- P. AsharPAP. Ashar
- Lintao ZhangLZLintao Zhang
- S. MalikSMS. Malik
- 13 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 286-292
Abstract
Methods based on Boolean satisfiability (SAT) typically use a conjunctive normal form (CNF) representation of the Boolean formula, and exploit the structure of the given problem through use of various decision heuristics and implication methods. We propose a new decision heuristic based on separator-set induced partitioning of the underlying CNF graph. It targets those variables whose choice generates clause partitions with disjoint variable supports. This can potentially improve performance of SAT applications by decomposing the problem dynamically within the search. In the context of a recently proposed image computation method combining SAT and BDDs, this results in simpler BDD subproblems. We provide algorithms for CNF partitioning - one based on a clause-variable dependency matrix, and another based on standard hypergraph partitioning techniques, and also for the use of partitioning information in decision heuristics for SAT. The effectiveness of the proposed partition-based heuristic is shown with practical results for reachability analysis of benchmark sequential circuits.Keywords
This publication has 10 references indexed in Scilit:
- Biasing symbolic search by means of dynamic activity profiles2002
- Equivalence checking combining a structural SAT-solver, BDDs, and simulation2002
- To split or to conjoin2000
- Checking Safety Properties Using Induction and a SAT-Solver2000
- Border-Block Triangular Form and Conjunction Schedule in Image Computation2000
- SAT-Based Image Computation with Application in Reachability Analysis2000
- VIS: A system for verification and synthesis1996
- Symbolic model checking for sequential circuit verificationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1994
- Verification of synchronous sequential machines based on symbolic execution1990
- Graph-Based Algorithms for Boolean Function ManipulationIEEE Transactions on Computers, 1986