2009 39th International Symposium on Multiple-Valued Logic Evaluation of Cardinality Constraints on SMT-Based Debugging Naha, Okinawaw, Japan May 21-May 23 ISBN: 978-0-7695-3607-1
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISMVL.2009.28
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.
Index Terms:
Satisfiable Modulo Theory (SMT), cardinality constraint, debugging
Citation:
Andre Sülflow, Robert Wille, Görschwin Fey, Rolf Drechsler, "Evaluation of Cardinality Constraints on SMT-Based Debugging," ismvl, pp.298-303, 2009 39th International Symposium on Multiple-Valued Logic, 2009 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||