8481 articles  [english version]

inria-00331479, version 1

Combination of Convex Theories: Modularity, Deduction Completeness, and Explanation

Duc-Khanh Tran () 1, Christophe Ringeissen (Auteur à contacter de préférence) 1, Silvio Ranise 1, Hélène Kirchner () 2

N° RR-6688 (2008)

Résumé : Decision procedures are key components of theorem provers and constraint satisfaction systems. Their modular combination is of prime interest for building efficient systems, but their effective use is often limited by poor interface capabilities, when such procedures only provide a simple ``sat/unsat'' answer. In this paper, we develop a rule-based framework to design cooperation schemas between such procedures while maintaining modularity of their interfaces. First, we use the rule-based framework to specify and prove the correctness of classic combination schemas by Nelson-Oppen and Shostak. Second, we introduce the concept of deduction complete satisfiability procedures, we show how to build them for large classes of theories, then we provide a schema to modularly combine them. Third, we consider the problem of modularly constructing explanations for combinations by re-using available proof-producing procedures for the component theories.

  • 1 :  CASSIS (INRIA Lorraine - LORIA / LIFC)
  • INRIA – CNRS : FRE2661 – Université de Franche-Comté – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
  • 2 :  INRIA Bordeaux - Sud-Ouest (INRIA Bordeaux - Sud-Ouest)
  • INRIA
  • Domaine : Informatique/Logique en informatique
  • Mots-clés : Decision Procedure – Satisfiability Modulo Theories – Combination – Deduction Completeness – Conflict Set
  • Référence interne : RR-6688
 
  • inria-00331479, version 1
  • oai:hal.inria.fr:inria-00331479
  • Contributeur : 
  • Soumis le : Jeudi 16 Octobre 2008, 18:40:55
  • Dernière modification le : Jeudi 16 Octobre 2008, 21:10:06