UTCS Artificial Intelligence
courses
talks/events
demos
people
projects
publications
software/data
labs
areas
admin
On Elementary Loops of Logic Programs (2011)
Martin Gebser,
Joohyung Lee
,
Yuliya Lierler
Using the notion of an elementary loop, Gebser and Schaub refined the theorem on loop formulas by Lin and Zhao by considering loop formulas of elementary loops only. In this paper, we reformulate their notion of an elementary loop, extend it to disjunctive programs, and study several properties of elementary loops, including how maximal elementary loops are related to minimal unfounded sets. The results provide useful insights into the stable model semantics in terms of elementary loops. For a nondisjunctive program, using a graph-theoretic characterization of an elementary loop, we show that the problem of recognizing an elementary loop is tractable. On the other hand, we show that the corresponding problem is coNP-complete for a disjunctive program. Based on the concept of an elementary loop, we present the notion of a Head-Elementary-loop-Free (HEF) program, a strict generalization of a Head-Cycle-Free (HCF) program by Ben-Eliyahu and Dechter, that can be turned into an equivalent nondisjunctive program in polynomial time by shifting head atoms into the body, thereby keeping nice properties of HCF programs.
View:
PDF
Citation:
Theory and Practice of Logic Programming
(2011).
Bibtex:
@article{gebser:tplp2010, title={On Elementary Loops of Logic Programs}, author={Martin Gebser and Joohyung Lee and Yuliya Lierler}, journal={Theory and Practice of Logic Programming}, url="http://www.cs.utexas.edu/users/ai-lab?gebser:tplp2010", year={2011} }
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
Logic