A bisimulation between DPLL(T) and a proof-search strategy for the focused sequent calculus - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2013

A bisimulation between DPLL(T) and a proof-search strategy for the focused sequent calculus

Résumé

We describe how the Davis-Putnam-Logemann-Loveland proced- ure DPLL is bisimilar to the goal-directed proof-search mechanism described by a standard but carefully chosen sequent calculus. We thus relate a procedure described as a transition system on states to the gradual completion of incomplete proof-trees. For this we use a focused sequent calculus for polarised clas- sical logic, for which we allow analytic cuts. The focusing mech- anisms, together with an appropriate management of polarities, then allows the bisimulation to hold: The class of sequent calculus proofs that are the images of the DPLL runs finishing on UNSAT, is identified with a simple criterion involving polarities. We actually provide those results for a version DPLL(T ) of the procedure that is parameterised by a background theory T for which we can decide whether conjunctions of literals are con- sistent. This procedure is used for Satisfiability Modulo Theor- ies (SMT) generalising propositional SAT. For this, we extend the standard focused sequent calculus for propositional logic in the same way DPLL(T ) extends DPLL: with the ability to call the de- cision procedure for T . DPLL(T ) is implemented as a plugin for P SYCHE, a proof- search engine for this sequent calculus, to provide a sequent- calculus based SMT-solver.
Fichier principal
Vignette du fichier
DPLL-LK.pdf (306.69 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00854426 , version 1 (27-08-2013)

Identifiants

Citer

Mahfuza Farooque, Stéphane Lengrand, Assia Mahboubi. A bisimulation between DPLL(T) and a proof-search strategy for the focused sequent calculus. LFMTP - International Workshop on Logical Frameworks and Meta-Languages: Theory and Practice - 2013, Sep 2013, Boston, United States. ⟨10.1145/2503887.2503892⟩. ⟨hal-00854426⟩
394 Consultations
218 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More