On elementary loops of logic programs
- Using the notion of an elementary loop, Gebser and Schaub (2005. Proceedings of the Eighth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'05), 53-65) refined the theorem on loop formulas attributable to Lin and Zhao (2004) by considering loop formulas of elementary loops only. In this paper, we reformulate the definition 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 also show that the corresponding problem is coNP-complete for a disjunctive program. Based on the notion of an elementary loop, we present the class of Head-Elementary-loop-Free (HEF) programs, which strictly generalizesUsing the notion of an elementary loop, Gebser and Schaub (2005. Proceedings of the Eighth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'05), 53-65) refined the theorem on loop formulas attributable to Lin and Zhao (2004) by considering loop formulas of elementary loops only. In this paper, we reformulate the definition 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 also show that the corresponding problem is coNP-complete for a disjunctive program. Based on the notion of an elementary loop, we present the class of Head-Elementary-loop-Free (HEF) programs, which strictly generalizes the class of Head-Cycle-Free (HCF) programs attributable to Ben-Eliyahu and Dechter (1994. Annals of Mathematics and Artificial Intelligence 12, 53-87). Like an Ha: program, an HEF program can be turned into an equivalent nondisjunctive program in polynomial time by shifting head atoms into the body.…
| Author details: | Martin GebserORCiD, Joohyung Lee, Yuliya Lierler |
|---|---|
| DOI: | https://doi.org/10.1017/S1471068411000019 |
| ISSN: | 1471-0684 |
| Title of parent work (English): | Theory and practice of logic programming |
| Publisher: | Cambridge Univ. Press |
| Place of publishing: | New York |
| Publication type: | Article |
| Language: | English |
| Year of first publication: | 2011 |
| Publication year: | 2011 |
| Release date: | 2017/03/26 |
| Tag: | loop formulas; stable model semantics; unfounded sets |
| Volume: | 11 |
| Issue: | 2 |
| Number of pages: | 36 |
| First page: | 953 |
| Last Page: | 988 |
| Funding institution: | German Research Foundation [SCHA 550/8-1]; National Science Foundation [IIS-0916116, IIS-0712113]; Office of the Director of National Intelligence (ODNI); Intelligence Advanced Research Projects Activity (IARPA), through US army; Computing Innovation Fellowship |
| Organizational units: | Mathematisch-Naturwissenschaftliche Fakultät / Institut für Informatik und Computational Science |
| Peer review: | Referiert |
| Institution name at the time of the publication: | Mathematisch-Naturwissenschaftliche Fakultät / Institut für Informatik |
| External remark: | Zweitveröffentlichung in der Schriftenreihe Postprints der Universität Potsdam : Mathematisch-Naturwissenschaftliche Reihe ; 566 |
