Physical Sciences and Mathematics Commons^™

Sat-Based Answer Set Programming, Enrico Giunchiglia, Yuliya Lierler, Marco Maratea

Computer Science Faculty Proceedings & Presentations

The relation between answer set programming (ASP) and propositional satisfiability (SAT) is at the center of many research papers, partly because of the tremendous performance boost of SAT solvers during last years. Various translations from ASP to SAT are known but the resulting SAT formula either includes many new variables or may have an unpractical size. There are also well known results showing a one-to-one correspondence between the answer sets of a logic program and the models of its completion. Unfortunately, these results only work for specific classes of problems. In this paper we present a SAT-based decision procedure for …