{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,21]],"date-time":"2025-12-21T10:03:17Z","timestamp":1766311397386},"reference-count":41,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2011,5,24]],"date-time":"2011-05-24T00:00:00Z","timestamp":1306195200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2011,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Using the notion of an elementary loop, Gebser and Schaub (2005. <jats:italic>Proceedings of the Eighth International Conference on Logic Programming and Nonmonotonic Reasoning<\/jats:italic> (<jats:italic>LPNMR'05<\/jats:italic>), 53\u201365) 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 <jats:monospace>coNP<\/jats:monospace>-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. <jats:italic>Annals of Mathematics and Artificial Intelligence 12<\/jats:italic>, 53\u201387). 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.<\/jats:p>","DOI":"10.1017\/s1471068411000019","type":"journal-article","created":{"date-parts":[[2011,5,24]],"date-time":"2011-05-24T04:57:50Z","timestamp":1306213070000},"page":"953-988","source":"Crossref","is-referenced-by-count":7,"title":["On elementary loops of logic programs"],"prefix":"10.1017","volume":"11","author":[{"given":"MARTIN","family":"GEBSER","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JOOHYUNG","family":"LEE","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"YULIYA","family":"LIERLER","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2011,5,24]]},"reference":[{"key":"S1471068411000019_ref39","doi-asserted-by":"publisher","DOI":"10.1145\/298514.298572"},{"key":"S1471068411000019_ref7","first-page":"224","volume-title":"Proceedings of the Nineteenth International Conference on Logic Programming (ICLP'03)","author":"Eiter","year":"2003"},{"key":"S1471068411000019_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/11546207_5"},{"key":"S1471068411000019_ref21","doi-asserted-by":"publisher","DOI":"10.3166\/jancl.16.35-86"},{"key":"S1471068411000019_ref4","first-page":"298","volume-title":"Proceedings of the Tenth International Conference on Principles of Knowledge Representation and Reasoning (KR'06)","author":"Chen","year":"2006"},{"key":"S1471068411000019_ref32","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2630"},{"key":"S1471068411000019_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72200-7_14"},{"key":"S1471068411000019_ref33","doi-asserted-by":"publisher","DOI":"10.1007\/11546207_44"},{"key":"S1471068411000019_ref11","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068409990196"},{"key":"S1471068411000019_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-3384-5_11"},{"key":"S1471068411000019_ref12","first-page":"372","volume-title":"Proceedings of the Twentieth International Joint Conference on Artificial Intelligence (IJCAI'07)","author":"Ferraris","year":"2007"},{"key":"S1471068411000019_ref35","doi-asserted-by":"publisher","DOI":"10.1145\/1131313.1131316"},{"key":"S1471068411000019_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(03)00078-X"},{"key":"S1471068411000019_ref25","first-page":"141","volume-title":"Proceedings of the Seventh International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'04)","author":"Lee","year":"2004"},{"key":"S1471068411000019_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2010.04.011"},{"key":"S1471068411000019_ref22","doi-asserted-by":"publisher","DOI":"10.1145\/1119439.1119440"},{"key":"S1471068411000019_ref40","first-page":"584","volume-title":"Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence (AAAI'08)","author":"You","year":"2008"},{"key":"S1471068411000019_ref31","doi-asserted-by":"publisher","DOI":"10.1145\/1149114.1149117"},{"key":"S1471068411000019_ref20","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-1066(97)10001-2"},{"key":"S1471068411000019_ref14","volume-title":"Proceedings of the Twenty-first AAAI Conference on Artificial Intelligence (AAAI'06)","author":"Gebser","year":"2006"},{"key":"S1471068411000019_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-934613-40-8.50006-3"},{"key":"S1471068411000019_ref36","first-page":"853","volume-title":"Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI'03)","author":"Lin","year":"2003"},{"key":"S1471068411000019_ref41","first-page":"859","volume-title":"Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI'03)","author":"You","year":"2003"},{"key":"S1471068411000019_ref18","first-page":"230","volume-title":"Proceedings of the Second International Conference on Principles of Knowledge Representation and Reasoning (KR'91)","author":"Gelfond","year":"1991"},{"key":"S1471068411000019_ref10","first-page":"51","article-title":"Consistency of Clark's completion and existence of stable models","volume":"1","author":"Fages","year":"1994","journal-title":"Journal of Methods of Logic in Computer Science"},{"key":"S1471068411000019_ref6","first-page":"422","volume-title":"Proceedings of the Eleventh International Conference on Principles of Knowledge Representation and Reasoning (KR'08)","author":"Drescher","year":"2008"},{"key":"S1471068411000019_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(94)90025-6"},{"key":"S1471068411000019_ref27","doi-asserted-by":"crossref","unstructured":"Lee J. and Lifschitz V. 2003. Loop formulas for disjunctive logic programs. In Proceedings of Nineteenth International Conference on Logic Programming (ICLP'03). 451\u2013465.","DOI":"10.1007\/978-3-540-24599-5_31"},{"key":"S1471068411000019_ref9","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068403001765"},{"key":"S1471068411000019_ref23","doi-asserted-by":"crossref","first-page":"813","DOI":"10.1613\/jair.2810","article-title":"Modularity aspects of disjunctive stable models","volume":"35","author":"Janhunen","year":"2009","journal-title":"Journal of Artificial Intelligence Research"},{"key":"S1471068411000019_ref37","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2004.04.004"},{"key":"S1471068411000019_ref28","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2005.09.003"},{"key":"S1471068411000019_ref38","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1613\/jair.2009","article-title":"Properties and applications of programs with monotone and convex constraints","volume":"27","author":"Liu","year":"2006","journal-title":"Journal of Artificial Intelligence Research"},{"key":"S1471068411000019_ref34","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018978005636"},{"key":"S1471068411000019_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01536399"},{"key":"S1471068411000019_ref29","first-page":"444","volume-title":"Proceedings of the Eleventh International Conference on Knowledge Representation and Reasoning (KR'08)","author":"Lee","year":"2008"},{"key":"S1471068411000019_ref19","first-page":"61","volume-title":"Proceedings of the Nineteenth AAAI Conference on Artificial Intelligence (AAAI)","author":"Giunchiglia","year":"2004"},{"key":"S1471068411000019_ref30","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04238-6_17"},{"key":"S1471068411000019_ref26","first-page":"503","volume-title":"Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence (IJCAI'05)","author":"Lee","year":"2005"},{"key":"S1471068411000019_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/BF01530761"},{"key":"S1471068411000019_ref17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77684-0_5"}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1471068411000019","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,26]],"date-time":"2019-04-26T23:31:46Z","timestamp":1556321506000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068411000019\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,5,24]]},"references-count":41,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2011,11]]}},"alternative-id":["S1471068411000019"],"URL":"https:\/\/doi.org\/10.1017\/s1471068411000019","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,5,24]]}}}