UTCS Artificial Intelligence
courses
talks/events
demos
people
projects
publications
software/data
labs
areas
admin
SAT-Based Answer Set Programming (2004)
Enrico Giunchiglia,
Yuliya Lierler
, Marco Maratea
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 answer set programming that (i) deals with any (non disjunctive) logic programs, (ii) works on a SAT formula without additional variables, and (iii) is guaranteed to work in polynomial space. Further, our procedure can be extended to compute all the answer sets still working in polynomial space. The experimental results of a prototypical implementation show that the approach can pay off sometimes by orders of magnitude.
View:
PS
Citation:
In
Proceedings of National Conference on Artificial Intelligence (AAAI)
, pp. 61-66 2004.
Bibtex:
@inproceedings{giu04a, title={SAT-Based Answer Set Programming}, author={Enrico Giunchiglia and Yuliya Lierler and Marco Maratea}, booktitle={Proceedings of National Conference on Artificial Intelligence (AAAI)}, pages={61-66}, url="http://www.cs.utexas.edu/users/ai-lab/?giu04a", year={2004} }
People
Yuliya Lierler
Ph.D. Alumni
ylierler [at] unomaha edu
Areas of Interest
Answer Set Programming
Labs
Texas Action Group