Skip to Main content Skip to Navigation

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

* Corresponding author
1 CASSIS - Combination of approaches to the security of infinite states systems
FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174), Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
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 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.
Keywords :
Document type :
Reports
Complete list of metadata

Cited literature [41 references]

https://hal.inria.fr/inria-00331479
Contributor : Christophe Ringeissen Connect in order to contact the contributor
Submitted on : Thursday, October 16, 2008 - 6:40:55 PM
Last modification on : Friday, January 21, 2022 - 3:09:38 AM
Long-term archiving on: : Tuesday, October 9, 2012 - 1:55:09 PM

### File

RR-6688.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : inria-00331479, version 1

### Citation

Duc-Khanh Tran, Christophe Ringeissen, Silvio Ranise, Hélène Kirchner. Combination of Convex Theories: Modularity, Deduction Completeness, and Explanation. [Research Report] RR-6688, INRIA. 2008, pp.34. ⟨inria-00331479⟩

Record views

Files downloads