City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

SAT and Satisfiability Modulo Theories (R. Bruttomesso, University of Lugano)
Seminar on Computer Science

What: Lecture
When: Saturday, 18 September 2010, 17:20–18:55
Where: ПОМИ РАН
Slides: csseminar_lecture_180910.pdf

Description

Satisfiability Modulo Theories (SMT) is the problem of deciding a quantifier-free formula modulo a background theory T. State-of-the-art SMT-Solvers are based on the DPLL(T) model, which efficiently combines a DPLL SAT-Solver, used to handle disjucntive choices, and a Theory Solver, a decision procedure for T, used to solve conjunctions of constraints. In this lecture we review the DPLL approach to SAT and extend it to DPLL(T) approach. Also we examine some useful theories, commonly used in the formal analysis of software, by sketching the main ideas behind the algorithms used to solve them.