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 HCF program, an HEF program can be turned into an equivalent nondisjunctive program in polynomial time by shifting head atoms into the body.show moreshow less

Download full text files

  • SHA-1: 2af083dcdd9038e3daa82fa00ce951841d83a61d

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics
Metadaten
Author:Martin GebserORCiD, Joohyung Lee, Yuliya Lierler
URN:urn:nbn:de:kobv:517-opus4-413091
DOI:https://doi.org/10.25932/publishup-41309
ISSN:1866-8372
Parent Title (English):Postprints der Universität Potsdam : Mathematisch-Naturwissenschaftliche Reihe
Series (Serial Number):Postprints der Universität Potsdam : Mathematisch-Naturwissenschaftliche Reihe (566)
Document Type:Postprint
Language:English
Date of first Publication:2019/02/01
Year of Completion:2011
Publishing Institution:Universität Potsdam
Release Date:2019/02/01
Tag:loop formulas; stable model semantics; unfounded sets
Issue:566
Pagenumber:36
Source:Theory and Practice of Logic Programming 11 (2011) 6, pp. 953–988 DOI 10.1017/S1471068411000019
Organizational units:Mathematisch-Naturwissenschaftliche Fakultät
Dewey Decimal Classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
Peer Review:Referiert
Publication Way:Open Access
Grantor:Cambridge University Press (CUP)
Licence (German):License LogoKeine Nutzungslizenz vergeben - es gilt das deutsche Urheberrecht
Notes extern:Bibliographieeintrag der Originalveröffentlichung/Quelle