*salle A. Turing CE4*

25 November 2013 - 11h30

A Bisimulation between DPLL(T) and a Proof-Search Strategy for the Focused Sequent Calculus

by Mahfuza Farooque from École polytechnique

Abstract: We describe how the Davis-Putnam-Logemann-Loveland procedure 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 classical logic,

for which we allow analytic cuts. The focusing mechanisms, 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 consistent. This procedure is used

for Satisfiability Modulo Theories (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 decision procedure for T.

DPLL(T) is implemented as a plugin for Psyche, a proof-search engine for

this sequent calculus, to provide a sequent-calculus based SMT-solver.