Automatic Combinability of Rewriting-Based Satisfiability Procedures

Hélène Kirchner 1 Silvio Ranise 2 Christophe Ringeissen 2 Duc-Khanh Tran 2
1 PROTHEO - Constraints, automatic deduction and software properties proofs
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
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 : We address the problems of combining satisfiability procedures and consider two combination scenarios: (i) the combination within the class of rewriting-based satisfiability procedures and (ii) the Nelson-Oppen combination of rewriting-based satisfiability procedures and arbitrary satisfiability procedures. In each scenario, we use meta-saturation, which schematizes saturation of the set containing the axioms of a given theory and an arbitrary set of ground literals, to syntactically decide sufficient conditions for the combinability of rewriting-based satisfiability procedures. For (i), we give a sufficient condition for the modular termination of meta-saturation. When meta-saturation for the union of theories halts, it yields a rewriting-based satisfiability procedure for the union. For (ii), we use meta-saturation to prove the stable infiniteness of the component theories and deduction completeness of their rewriting-based satisfiability procedures. These properties are important to establish the correctness of the Nelson-Oppen combination method and to obtain an efficient implementation.
Type de document :
Communication dans un congrès
Miki Hermann, Andrei Voronkov. 13th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning - LPAR 2006, Nov 2006, Phnom Penh/Cambodia, Springer, 4246, pp.542--556, 2006, Lecture Notes in Artificial Intelligence. 〈10.1007/11916277〉
Liste complète des métadonnées
https://hal.inria.fr/inria-00117261
Contributeur : Christophe Ringeissen <>
Soumis le : jeudi 30 novembre 2006 - 16:34:49
Dernière modification le : jeudi 15 février 2018 - 08:48:09

Lien texte intégral

openaccess

Identifiants

Collections

INRIA | UNIV-FCOMTE | UNIV-BM | FEMTO-ST | UNIV-BM-THESE | LORIA | UNIV-LORRAINE

Citation

Hélène Kirchner, Silvio Ranise, Christophe Ringeissen, Duc-Khanh Tran. Automatic Combinability of Rewriting-Based Satisfiability Procedures. Miki Hermann, Andrei Voronkov. 13th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning - LPAR 2006, Nov 2006, Phnom Penh/Cambodia, Springer, 4246, pp.542--556, 2006, Lecture Notes in Artificial Intelligence. 〈10.1007/11916277〉. 〈inria-00117261〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

122

Contact


archive-ouverte@inria.fr