{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T00:07:30Z","timestamp":1715645250961},"reference-count":31,"publisher":"Cambridge University Press (CUP)","issue":"4-5","license":[{"start":{"date-parts":[[2013,9,25]],"date-time":"2013-09-25T00:00:00Z","timestamp":1380067200000},"content-version":"unspecified","delay-in-days":86,"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":[[2013,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider disjunctive logic programs without function symbols but with existential quantification in rule heads, under the semantics of general stable models. There are at least two interesting prospects in these programs. The first is that a program can be made more succinct by using existential variables, and the second is on the potential in representing defeasible ontological knowledge by these logic programs. This paper studies some of the properties of these programs. First, we show a simple yet intuitive definition of stable models for these programs that does not resort to second-order logic. Second, the stable models of these programs can be characterized by an extension of progression for disjunctive programs, which provides a native characterization of justification for stable models. We then study the decidability issue. While the stable model existence problem for safe disjunctive programs is decidable, with existential quantification allowed in rule heads the problem becomes undecidable. We identify an interesting decidable fragment by exploring a new notion of stratification over existential quantification.<\/jats:p>","DOI":"10.1017\/s1471068413000355","type":"journal-article","created":{"date-parts":[[2013,9,25]],"date-time":"2013-09-25T16:24:58Z","timestamp":1380126298000},"page":"563-578","source":"Crossref","is-referenced-by-count":1,"title":["Disjunctive logic programs with existential quantification in rule heads"],"prefix":"10.1017","volume":"13","author":[{"given":"JIA-HUAI","family":"YOU","sequence":"first","affiliation":[]},{"given":"HENG","family":"ZHANG","sequence":"additional","affiliation":[]},{"given":"YAN","family":"ZHANG","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2013,9,25]]},"reference":[{"key":"S1471068413000355_ref6","doi-asserted-by":"publisher","DOI":"10.1109\/69.599933"},{"key":"S1471068413000355_ref31","unstructured":"Zhou Y. and Zhang Y. 2011. Progression semantics for disjunctive logic programs. In Proc. AAAI-11, 286\u2013291."},{"key":"S1471068413000355_ref27","doi-asserted-by":"publisher","DOI":"10.1145\/1217856.1217859"},{"key":"S1471068413000355_ref25","doi-asserted-by":"publisher","DOI":"10.1145\/1754399.1754403"},{"key":"S1471068413000355_ref23","doi-asserted-by":"publisher","DOI":"10.1145\/1149114.1149117"},{"key":"S1471068413000355_ref22","unstructured":"Leone N. , Manna M. , Terracina G. and Veltri P. 2012. Efficiently computable datalog; programs. In KR."},{"key":"S1471068413000355_ref17","unstructured":"Gottlob G. , Hernich A. , Kupke C. and Lukasiewicz T. 2012. Equality-friendly well-founded semantics and applications to description logics. In Proc. AAAI-12."},{"key":"S1471068413000355_ref16","unstructured":"Gelfond M. and Lifschitz V. 1988. The stable model semantics for logic programming. In Proc. ICLP'88, 1070\u20131080."},{"key":"S1471068413000355_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2010.04.011"},{"key":"S1471068413000355_ref15","unstructured":"Ferraris P. , Lee J. , Lifschitz V. and Palla R. 2009. Symmetric splitting in the general theory of stable models. In IJCAI-09, 797\u2013803."},{"key":"S1471068413000355_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.10.033"},{"key":"S1471068413000355_ref12","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":"S1471068413000355_ref2","unstructured":"Bartholomew M. and Lee J. 2010. A decidable class of groundable formulas in the general theory of stable models. In Proc. KR-2010."},{"key":"S1471068413000355_ref1","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068412000257"},{"key":"S1471068413000355_ref3","first-page":"1","article-title":"The undecidability of the domino problem.","volume":"66","author":"Berger","year":"1966","journal-title":"Memoirs of the American Mathematical Society"},{"key":"S1471068413000355_ref21","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1613\/jair.3489","article-title":"Reformulating the situation calculus and the event calculus in the general theory of stable models and in answer set programming.","volume":"43","author":"Lee","year":"2012","journal-title":"Journal of Artificial Intelligence Research (JAIR)"},{"key":"S1471068413000355_ref8","unstructured":"Cal\u00ec A. , Gottlob G. and Lukasiewicz T. 2009. A general datalog-based framework for tractable query answering over ontologies. In Proc. PODS, 77\u201386."},{"key":"S1471068413000355_ref10","unstructured":"Casini G. and Straccia U. 2011. Defeasible inheritance-based description logics. In Proc. IJCAI-11, 813\u2013818."},{"key":"S1471068413000355_ref7","unstructured":"Cal\u00ec A. , Gottlob G. and Kifer M. 2008. Taming the infinite chase: Query answering under expressive relational constraints. In KR, 70\u201380."},{"key":"S1471068413000355_ref20","first-page":"125","article-title":"First-order stable model semantics and first-order loop formulas.","volume":"42","author":"Lee","year":"2011","journal-title":"Journal of Artificial Intelligence Research (JAIR)"},{"key":"S1471068413000355_ref28","unstructured":"You J.-H. , Shen Y.-D. and Wang K. 2012. Well-supported semantics for logic programs with generalized rules. In Correct Reasoning: Essays on Logic-Based AI in Honor of Vladimir Lifschitz, LNCS 7265, 576\u2013591."},{"key":"S1471068413000355_ref19","unstructured":"Lee J. , Lifschitz V. and Palla R. 2008. Safe formulas in the general theory of stable models (preliminary report). In Proc. ICLP, 672\u2013676."},{"key":"S1471068413000355_ref4","first-page":"719","article-title":"Defeasible inclusions in low-complexity DLs.","volume":"42","author":"Bonatti","year":"2011","journal-title":"Journal of Artificial Intelligence Research"},{"key":"S1471068413000355_ref26","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018930122475"},{"key":"S1471068413000355_ref30","unstructured":"Zhang H. , Zhang Y. , Ying M. and Zhou Y. 2011. Translating first-order theories into logic programs. In Proc. IJCAI-11, 1126\u20131131."},{"key":"S1471068413000355_ref29","doi-asserted-by":"crossref","unstructured":"Zhang H. and Ying M. 2010. Decidable fragments of first-order language under stable model semantics and circumscription. In Proc. AAAI-10.","DOI":"10.1609\/aaai.v24i1.7590"},{"key":"S1471068413000355_ref18","doi-asserted-by":"publisher","DOI":"10.1007\/BF00971620"},{"key":"S1471068413000355_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2012.08.002"},{"key":"S1471068413000355_ref5","unstructured":"Cabalar P. , Pearce D. and Valverde A. 2009. A revised concept of safety for general answer set programs. In Proc. LPNMR, 58\u201370."},{"key":"S1471068413000355_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2010.04.001"},{"key":"S1471068413000355_ref11","doi-asserted-by":"publisher","DOI":"10.1145\/261124.261126"}],"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\/S1471068413000355","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,13]],"date-time":"2024-05-13T09:29:11Z","timestamp":1715592551000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068413000355\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,7]]},"references-count":31,"journal-issue":{"issue":"4-5","published-print":{"date-parts":[[2013,7]]}},"alternative-id":["S1471068413000355"],"URL":"https:\/\/doi.org\/10.1017\/s1471068413000355","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,7]]}}}