Robbins, E., Howe, J. M. & King, A. (2013). Theory propagation and rational-trees. Proceedings of the 15th Symposium on Principles and Practice of Declarative Programming, PPDP 2013, pp. 193-204.
Download (222kB) | Preview
SAT Modulo Theories (SMT) is the problem of determining the satisfiability of a formula in which constraints, drawn from a given constraint theory T, are composed with logical connectives. The DPLL(T) approach to SMT has risen to prominence as a technique for solving these quantifier-free problems. The key idea in DPLL(T) is to closely couple unit propagation in the propositional part of the problem with theory propagation in the constraint component. In this paper it is demonstrated how reification provides a natural way for orchestrating this in the setting of logic programming. This allows an elegant implementation of DPLL(T) solvers in Prolog. The work is motivated by a problem in reverse engineering, that of type recovery from binaries. The solution to this problem requires an SMT solver where the theory is that of rational-tree constraints, a theory not supported in off-the-shelf SMT solvers, but realised as unification in many Prolog systems. The solver is benchmarked against a number of type recovery problems, and compared against a lazy-basic SMT solver built on PicoSAT.
|Additional Information:||© ACM 2013. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in Proceedings of the 15th Symposium on Principles and Practice of Declarative Programming, http://dx.doi.org/10.1145/2505879.2505901.|
|Uncontrolled Keywords:||SAT solving, reverse engineering|
|Subjects:||Q Science > QA Mathematics > QA75 Electronic computers. Computer science|
|Divisions:||School of Informatics > Department of Computing|
Actions (login required)
Downloads per month over past year