Combination of disjoint theories: beyond decidability

Pascal Fontaine 1 Stephan Merz 1 Christoph Weidenbach 2
1 VERIDIS - VERIfication pour les systèmes DIStribués
Inria Nancy - Grand Est, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications : UMR7503
Abstract : Combination of theories underlies the design of satisfiability modulo theories (SMT) solvers. The Nelson-Oppen framework can be used to build a decision procedure for the combination of two disjoint decidable stably infinite theories. We here study combinations involving an arbitrary first-order theory. Decidability is lost, but refutational completeness is preserved. We consider two cases and provide complete (semi-)algorithms for them. First, we show that it is possible under minor technical conditions to combine a decidable (not necessarily stably infinite) theory and a disjoint finitely axiomatized theory, obtaining a refutationally complete procedure. Second, we provide a refutationally complete procedure for the union of two disjoint finitely axiomatized theories, that uses the assumed procedures for the underlying theories without modifying them.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-00747271
Contributor : Pascal Fontaine <>
Submitted on : Tuesday, October 30, 2012 - 9:57:15 PM
Last modification on : Thursday, February 21, 2019 - 2:02:02 PM

Identifiers

Collections

Citation

Pascal Fontaine, Stephan Merz, Christoph Weidenbach. Combination of disjoint theories: beyond decidability. IJCAR - 6th International Joint Conference on Automated Reasoning - 2012, Jun 2012, Manchester, United Kingdom. pp.256-270, ⟨10.1007/978-3-642-31365-3_21⟩. ⟨hal-00747271⟩

Share

Metrics

Record views

246