UTCS Artificial Intelligence
courses
talks/events
demos
people
projects
publications
software/data
labs
areas
admin
Elementary Sets for Logic Programs (2006)
Martin Gebser,
Joohyung Lee
, and
Yuliya Lierler
By introducing the concepts of a loop and a loop formula, Lin and Zhao showed that the answer sets of a nondisjunctive logic program are exactly the models of its Clark's completion that satisfy the loop formulas of all loops. Recently, Gebser and Schaub showed that the Lin-Zhao theorem remains correct even if we restrict loop formulas to a special class of loops called ``elementary loops.'' In this paper, we simplify and generalize the notion of an elementary loop, and clarify its role. We propose the notion of an elementary set, which is almost equivalent to the notion of an elementary loop for nondisjunctive programs, but is simpler, and, unlike elementary loops, can be extended to disjunctive programs without producing unintuitive results. We show that the maximal unfounded elementary sets for the ``relevant'' part of a program are exactly the minimal sets among the nonempty unfounded sets. We also present a graph-theoretic characterization of elementary sets for nondisjunctive programs. Unlike the case of nondisjunctive programs, we show that the problem of deciding an elementary set is coNP-complete for disjunctive programs.
View:
PDF
Citation:
In
Proceedings of National Conference on Artificial Intelligence (AAAI)
2006.
Bibtex:
@Inproceedings{gll06, title={Elementary Sets for Logic Programs}, author={Martin Gebser and Joohyung Lee and Yuliya Lierler}, booktitle={Proceedings of National Conference on Artificial Intelligence (AAAI)}, url="http://www.cs.utexas.edu/users/ai-lab/?gll06", year={2006} }
People
Joohyung Lee
Ph.D. Alumni
joolee [at] asu edu
Yuliya Lierler
Ph.D. Alumni
ylierler [at] unomaha edu
Areas of Interest
Answer Set Programming
Labs
Texas Action Group