4 ms·
I'm working in first-order logic theorem proving (which obviously has far greater applications than propositional SAT: from mathematical proof checking, to soft
by andrepd 7y ago
I'm working in first-order logic theorem proving (which obviously has far greater applications than propositional SAT: from mathematical proof checking, to software and hardware verification, e.g. compiler optimisation checking, to integration in higher-order solvers, etc.). Our algorithm is based on the idea of abstracting the first-order problem to a propositional one, which is then passed to a SAT solver! If it is inconsistent, so is the first order problem and we're done. If not, the SAT problem is satisfiable and we can use the solution to guide a "refinement" of the propositional abstraction, which is again passed to the SAT solver, and so on. If no "refinement" can be made, the first-order problem is satisfiable.
We do reasonably well on the annual CASC competition of theorem provers (we're iprover), even winning a division where this approach is particularly strong!
[1]: http://www.tptp.org/CASC/27/ http://www.tptp.org/CASC/27/
- est31 7y agoGreat talk by Kathleen Fisher on this topic. Also mentions SAT solvers. https://youtu.be/TH0tDGk19_c https://youtu.be/TH0tDGk19_c
- Footpost 7y agoOur algorithm ... Unless I completely misunderstand what you write, the approach you describe is the standard way of setting up SMT-solvers by interaction between a SAT solver with a theory solver. I think it is called lazy SMT or DPLL(T) in [1] where this approach seems to have been described first. [2] is also an interesting description of the phenomenon. [1] H. Ganzinger, G. Hagen, R. Nieuwenhuis, A. Oliveras, C. Tinelli, DPLL(T): Fast Decision Procedures. https://www.cs.upc.edu/~oliveras/espai/papers/dpllt.pdf https://www.cs.upc.edu/~oliveras/espai/papers/dpllt.pdf [1] R. Nieuwenhuis, A. Oliveras, C. Tinelli, Abstract DPLL and Abstract DPLL Modulo Theories. http://www.cs.upc.edu/~roberto/papers/lpar04.pdf http://www.cs.upc.edu/~roberto/papers/lpar04.pdf
- andrepd 7y agoI read both those papers ;) I guess that you can think of our algorithm as lazy SAT modulo quantified first order logic, with the crucial difference that first order logic is undecidable. But anyway in this case the "decision procedure for T" would just be checking whether any two complementary literals which are true in the model are unifiable, which is decidable. Paper: http://www.cs.man.ac.uk/~korovink/my_pub/inst_gen_modular.pdf http://www.cs.man.ac.uk/~korovink/my_pub/inst_gen_modular.pd...
- c-cube 7y agoIt's not the same approach as CDCL(T) (the stuff in z3, cvc4, and other classic SMT solvers). Basically CDCL(T) uses the theory part (the "T") as a callback in the inner loop of the SAT solver (to validate partial models). iProver and similar refinement provers tend to have their own outer loops ("refinement loops" in other communities) that makes a succession of calls to the SAT solver, to completion, and use the model or unsat core to refine their own abstraction for the next iteration of the outer loop.