Evaluation of Cardinality Constraints on SMT-Based Debugging
Authors:
- Andre SülflowASAndre Sülflow
- Robert WilleRWRobert Wille
- Görschwin FeyGFGörschwin Fey
- Rolf DrechslerRDRolf Drechsler
- 1 January 2009
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 298-303
Abstract
For formal verification of hardware satisfiability modulo theory (SMT) solvers are increasingly applied. Today's state-of-the-art SMT solvers use different techniques like term-rewriting, abstraction, or bit-blasting. The performance does not only depend on the underlying decision problem but also on the encoding of the original problem into an SMT instance. In this work, encodings for cardinality constraints in SMT are investigated. Three different encodings are considered: an adder network, an encoding with multiplexors, and a newly proposed encoding with shifters. The encodings are analyzed with respect to size and complexity. The experimental evaluation on debugging instances that contain cardinality constraints shows the strong influence of the encoding on the resulting run-times.Keywords
This publication has 16 references indexed in Scilit:
- Z3: An Efficient SMT Solver2008
- Towards Robust CNF Encodings of Cardinality Constraints2007
- Formalizing Dangerous SAT Encodings2007
- A Fast Linear-Arithmetic Solver for DPLL(T)2006
- Post-verification debugging of hierarchical designs2005
- The MathSAT 3 SystemLecture Notes in Computer Science, 2005
- DPLL(T): Fast Decision Procedures2004
- GRASP: a search algorithm for propositional satisfiabilityIEEE Transactions on Computers, 1999
- Graph-Based Algorithms for Boolean Function ManipulationIEEE Transactions on Computers, 1986
- A machine program for theorem-provingCommunications of the ACM, 1962