loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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
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.