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.

PDF

In Logic Programming and Nonmonotonic Reasoning, 149--161, 2007.

@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} }