3543 articles – 5276 Notices  [english version]

inria-00543801, version 1

Combining decision procedures by (model-)equality propagation

Diego Caminha B. De Oliveira 1, David Déharbe 2, Pascal Fontaine () 1

Science of Computer Programming 240, 2 July 2009 (2010) 113-128

Résumé : Formal methods in software and hardware design often generate formulas that need to be validated, either interactively or automatically. Among the automatic tools, SMT (Satisfiability Modulo Theories) solvers are particularly suitable to discharge such proof obligations, since their input language is equational logic with symbols from various useful decidable fragments such as uninterpreted symbols, linear arithmetic, and usual data-structures like arrays or lists. In this paper, we present an approach to combine decision procedures and propositional solvers into an SMT-solver. This approach is based not only on the exchange of deducible equalities between decision procedures, but also on the generation of model equalities by decision procedures. This extends nicely the classical Nelson-Oppen combination procedure in a simple platform to smoothly combine convex and non-convex theories. We show the soundness and completeness of this approach using an original abstract framework to represent and reason about SMT-solvers. We then describe an algorithmic translation of this method, implemented in the kernel of the veriT solver.

  • 1 :  MOSEL (LORIA)
  • INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
  • 2 :  Universidade Federal de Rio Grande do Norte (UFRN)
  • Universidade Federal de Rio Grande do Norte
  • Domaine : Informatique/Logique en informatique
  • Mots-clés : automatic theorem proving – SMT solvers – combination of decision procedures
 
  • inria-00543801, version 1
  • oai:hal.inria.fr:inria-00543801
  • Contributeur : 
  • Soumis le : Lundi 6 Décembre 2010, 16:33:59
  • Dernière modification le : Mercredi 22 Juin 2011, 14:33:09