ASSAT: Computing Answer Sets of a Logic Program by SAT Solvers

Fangzhen Lin and Yuting Zhao, Hong Kong University of Science and Technology

We propose a new translation from normal logic programs with constraints under the answer set semantics to propositional logic. Given a logic program, we show that by adding, for each loop in the program, a corresponding loop formula to the program’s completion, we obtain a one-to-one correspondence between the answer sets of the program and the models of the resulting propositional theory. Compared with the translation by Ben-Eliyahu and Dechter, ours has the advantage that it does not use any extra variables, and is considerably simpler, thus easier to understand. However, in the worst case, it requires computing exponential number of loop formulas. To address this problem, we propose an approach that adds loop formulas a few at a time, selectively. Based on these results, we implemented a system called ASSAT(X), depending on the SAT solver X used, and tested it on a variety of benchmarks including the graph coloring, the blocks world planning, and Hamiltonian Circuit domains. The results are compared with those by smodels and dlv, and it shows a clear edge of ASSAT(X) over them in these domains.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.