Tesis doctoral de Albert Oliveras Llunell
When solving a problem by means of automated theorem proving there are two important decisions to make: how to express and how to solve the problem. The choice of the logic in which to formalize the problem is usually based on the expressivity and the automation of the logic. Not surprisingly, the more expressive the logic the lower degree of automation it supports. Hence, one has to find the right balance between these two concepts. Ver the last ten years, propositional logic has been shown to be very useful, due to its degree of automation, in areas such as electronic design automation, verification, artificial intelligence and operations research. Thanks to recent advances in the dpll algorithm for propositional satisfiability (sat), propositional solvers are becoming the tool of choice for attacking more and more practical problems. Owever, for many applications encoding the problems into propositional logic is not the right choice. Frequently, a better alternative is to express the problems in a richer nonpropositional logic. This is why both the dpll procedure and its enhancements have been adapted for handling satisfiability problems in more expressive logics. In particular, they have been used to build efficient algorithms for the satisfiability modulo theories problem (smt): deciding the satisfiability of ground first-order formulas with respect to background theories such as the integer or real numbers, the theory of equality, of arrays and so on. He topic of this thesis is the development of dpll(t), a new approach to smt. It is based on a general propositional engine dpll(x), whose parameter x is instantiated with a solver for a theory t of interest thus giving a dpll(t) system for deciding satisfiability of formulas modulo the theory t. He introduction of this approach is done by means of our abstract dpll framework. Apart from providing a simple and clean presentation of our approach, this framework also allows one to model the various existing techniq
Datos académicos de la tesis doctoral «The dpll(t) approach to satisfiability y modulo theories«
- Título de la tesis: The dpll(t) approach to satisfiability y modulo theories
- Autor: Albert Oliveras Llunell
- Universidad: Politécnica de catalunya
- Fecha de lectura de la tesis: 07/07/2006
Dirección y tribunal
- Director de la tesis
- Robert Lukas Mario Nieuwenhuis
- Tribunal
- Presidente del tribunal: jordi Cortadella fortuny
- sava Krstic (vocal)
- e. Bryant randal (vocal)
- byron Cook (vocal)