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

Duc-Khanh Tran 1 Christophe Ringeissen 2 Silvio Ranise 3 Hélène Kirchner 4
2 CASSIS - Combination of approaches to the security of infinite states systems
FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies, INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : 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 framework to design cooperation schemas between such procedures while maintaining modularity of their interfaces. First, we use the 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.
Type de document :
Article dans une revue
Journal of Symbolic Computation, Elsevier, 2010, Automated Deduction: Decidability, Complexity, Tractability, 45 (2), pp.261-286. 〈10.1016/j.jsc.2008.10.006〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00428583
Contributeur : Christophe Ringeissen <>
Soumis le : jeudi 29 octobre 2009 - 11:28:23
Dernière modification le : jeudi 15 février 2018 - 08:48:09

Lien texte intégral

Identifiants

Citation

Duc-Khanh Tran, Christophe Ringeissen, Silvio Ranise, Hélène Kirchner. Combination of Convex Theories: Modularity, Deduction Completeness, and Explanation. Journal of Symbolic Computation, Elsevier, 2010, Automated Deduction: Decidability, Complexity, Tractability, 45 (2), pp.261-286. 〈10.1016/j.jsc.2008.10.006〉. 〈inria-00428583〉

Partager

Métriques

Consultations de la notice

244