UTCS Artificial Intelligence
courses
talks/events
demos
people
projects
publications
software/data
labs
areas
admin
Head-Elementary-Set-Free Logic Programs (2007)
Martin Gebser,
Joohyung Lee
, and
Yuliya Lierler
The recently proposed notion of an elementary set (or elementary loop) yielded a refinement of the theorem on loop formulas, which tells us that stable models can be characterized by loop formulas of elementary sets. Based on the notion of an elementary set, we propose the notion of an head-elementary-set-free (HEF) program, a more general class of disjunctive programs than head-cycle-free (HCF) programs by Ben-Eliyahu and Dechter, that can be still turned into nondisjunctive programs in polynomial time and space by "shifting" the head atoms into the body. We also show several other properties of HEF programs that generalize earlier results on HCF programs. We provide an algorithm for finding an elementary set for an HEF program, which has a potential for improving the stable model computation for disjunctive programs.
View:
PDF
Citation:
In
Logic Programming and Nonmonotonic Reasoning
, pp. 149--161 2007.
Bibtex:
@inproceedings{gebser:lpnmr07, title={Head-Elementary-Set-Free Logic Programs}, author={Martin Gebser and Joohyung Lee and Yuliya Lierler}, booktitle={Logic Programming and Nonmonotonic Reasoning}, pages={149--161}, url="http://www.cs.utexas.edu/users/ai-lab?gebser:lpnmr07", year={2007} }
People
Joohyung Lee
Ph.D. Alumni
joolee [at] asu edu
Yuliya Lierler
Ph.D. Alumni
ylierler [at] unomaha edu
Areas of Interest
Logic