{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T16:38:31Z","timestamp":1762101511643},"reference-count":41,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2014,1,10]],"date-time":"2014-01-10T00:00:00Z","timestamp":1389312000000},"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":[[2015,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Answer Set Programming (ASP) is a popular framework for modelling combinatorial problems. However, ASP cannot be used easily for reasoning about uncertain information. Possibilistic ASP (PASP) is an extension of ASP that combines possibilistic logic and ASP. In PASP a weight is associated with each rule, whereas this weight is interpreted as the certainty with which the conclusion can be established when the body is known to hold. As such, it allows us to model and reason about uncertain information in an intuitive way. In this paper we present new semantics for PASP in which rules are interpreted as constraints on possibility distributions. Special models of these constraints are then identified as possibilistic answer sets. In addition, since ASP is a special case of PASP in which all the rules are entirely certain, we obtain a new characterization of ASP in terms of constraints on possibility distributions. This allows us to uncover a new form of disjunction, called weak disjunction, that has not been previously considered in the literature. In addition to introducing and motivating the semantics of weak disjunction, we also pinpoint its computational complexity. In particular, while the complexity of most reasoning tasks coincides with standard disjunctive ASP, we find that brave reasoning for programs with weak disjunctions is easier.<\/jats:p>","DOI":"10.1017\/s147106841300063x","type":"journal-article","created":{"date-parts":[[2014,1,10]],"date-time":"2014-01-10T15:38:41Z","timestamp":1389368321000},"page":"79-116","source":"Crossref","is-referenced-by-count":8,"title":["Characterizing and extending answer set semantics using possibility theory"],"prefix":"10.1017","volume":"15","author":[{"given":"KIM","family":"BAUTERS","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"STEVEN","family":"SCHOCKAERT","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MARTINE","family":"DE COCK","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"DIRK","family":"VERMEIR","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,1,10]]},"reference":[{"key":"S147106841300063X_ref27","unstructured":"Lifschitz V. and Schwarz G. 1993. Extended logic programs as autoepistemic theories. In Proceedings of the 2nd International Workshop on Logic Programming and Nonmonotonic Reasoning, 101\u2013114."},{"key":"S147106841300063X_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(97)00012-X"},{"key":"S147106841300063X_ref1","doi-asserted-by":"crossref","unstructured":"Banerjee M. and Dubois D. 2009. A simple modal logic for reasoning about revealed beliefs. In Proceedings of the 10th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU'09), 805\u2013816.","DOI":"10.1007\/978-3-642-02906-6_69"},{"key":"S147106841300063X_ref35","volume-title":"Computational Complexity","author":"Papadimitriou","year":"1994"},{"key":"S147106841300063X_ref4","doi-asserted-by":"crossref","unstructured":"Bauters K. , Schockaert S. , De Cock M. and Vermeir D. 2011. Weak and strong disjunction in possibilistic ASP. In Proceedings of the 11th International Conference on Scalable Uncertainty Management (SUM).","DOI":"10.1007\/978-3-642-23963-2_37"},{"key":"S147106841300063X_ref2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511543357"},{"key":"S147106841300063X_ref8","unstructured":"Brewka G. 2002. Logic programming with ordered disjunction. In Proceedings of the 18th National Conference on Artificial Intelligence (AAAI), 100\u2013105."},{"key":"S147106841300063X_ref30","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(85)90042-6"},{"key":"S147106841300063X_ref12","doi-asserted-by":"crossref","unstructured":"Dam\u00e1sio C. V. and Pereira L. M. 2001. Monotonic and residuated logic programs. In Proceedings of the 6th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU '01), 748\u2013759.","DOI":"10.1007\/3-540-44652-4_66"},{"key":"S147106841300063X_ref37","doi-asserted-by":"publisher","DOI":"10.1007\/BF00881915"},{"key":"S147106841300063X_ref23","unstructured":"Gelfond M. and Lifzchitz V. 1988. The stable model semantics for logic programming. In Proceedings of the 5th International Conference on Logic Programming (ICLP), 1081\u20131086."},{"key":"S147106841300063X_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/S0888-613X(97)00019-4"},{"key":"S147106841300063X_ref31","unstructured":"Nguyen L. A. 2005. On the complexity of fragments of modal logics. In Proceedings of the 5th International Conference on Advances in Modal Logic (AiML'05), 249\u2013268."},{"key":"S147106841300063X_ref33","unstructured":"Nieves J. C. and Lindgren H. 2012. Possibilistic nested logic programs. In Technical Communications of the 28th International Conference on Logic Programming (ICLP'12), 267\u2013276."},{"key":"S147106841300063X_ref41","doi-asserted-by":"crossref","unstructured":"Zadeh L. 1992. Fuzzy logic and the calculus of fuzzy if-then rules. In Proceedings of the 22nd IEEE International Symposium on Multiple-Valued Logic (ISMVL), 480\u2013480.","DOI":"10.1109\/ISMVL.1992.186834"},{"key":"S147106841300063X_ref39","doi-asserted-by":"crossref","unstructured":"Vennekens J. , Verbaeten S. and Bruynooghe M. 2004. Logic programs with annotated disjunctions. In Proceedings of the 20th International Conference on Logic Programming (ICLP), Lecture Notes in Computer Science, Vol. 3132, 431\u2013445.","DOI":"10.1007\/978-3-540-27775-0_30"},{"key":"S147106841300063X_ref10","doi-asserted-by":"publisher","DOI":"10.1109\/69.877512"},{"key":"S147106841300063X_ref22","doi-asserted-by":"publisher","DOI":"10.1007\/BF03037169"},{"key":"S147106841300063X_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/S0888-613X(01)00061-5"},{"key":"S147106841300063X_ref6","unstructured":"Benferhat S. , Dubois D. and Prade H. 1992. Representing default rules in possibilistic logic. In Proceedings of the 3rd International Conference on Principles of Knowledge Representation and Reasoning (KR), 673\u2013684."},{"key":"S147106841300063X_ref40","unstructured":"Vlaeminck H. , Vennekens J. , Bruynooghe M. and Denecker M. 2012. Ordered epistemic logic: Semantics, complexity and applications. In Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning (KR'12)."},{"key":"S147106841300063X_ref9","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068402001394"},{"key":"S147106841300063X_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(91)90101-O"},{"key":"S147106841300063X_ref14","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1093\/oso\/9780198537472.003.0009","volume-title":"Handbook of Logic for Artificial Intelligence and Logic Programming","author":"Dubois","year":"1994"},{"key":"S147106841300063X_ref25","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511790423"},{"key":"S147106841300063X_ref32","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-006-9029-y"},{"key":"S147106841300063X_ref20","unstructured":"Gelfond M. 1987. On stratified autoepistemic theories. In Proceedings of the 6th National Conference on Artificial Intelligence (AAAI), 207\u2013211."},{"key":"S147106841300063X_ref11","doi-asserted-by":"publisher","DOI":"10.1137\/0217078"},{"key":"S147106841300063X_ref19","first-page":"115","volume-title":"LPNMR","author":"Faber","year":"2009"},{"key":"S147106841300063X_ref21","unstructured":"Gelfond M. 1991. Strong introspection. In Proceedings of the 9th National Conference on Artificial Intelligence (AAAI'91), 386\u2013391."},{"key":"S147106841300063X_ref34","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068411000408"},{"key":"S147106841300063X_ref3","unstructured":"Bauters K. , Schockaert S. , De Cock M. and Vermeir D. 2010. Possibilistic answer set programming revisited. In Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence (UAI)."},{"key":"S147106841300063X_ref13","unstructured":"Dubois D. , Lang J. and Prade H. 1991. Towards possibilistic logic programming. In Proceedings of the 8th International Conference on Logic Programming (ICLP), 581\u2013595."},{"key":"S147106841300063X_ref24","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511810275"},{"key":"S147106841300063X_ref36","unstructured":"Pearce D. 1997. A new logical characterization of stable models and answer sets. In Proceedings of the 2nd International Workshop on Non-Monotonic Extensions of Logic Programming (NMELP), Lecture Notes in Artificial Intelligence, Vol. 1216, 57\u201370."},{"key":"S147106841300063X_ref17","unstructured":"Dubois D. , Prade H. and Schockaert S. 2012. Stable models in generalized possibilistic logic. In Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning (KR'12), 519\u2013529."},{"key":"S147106841300063X_ref26","doi-asserted-by":"crossref","unstructured":"Lifschitz V. 2010. Thirteen definitions of a stable model. In Fields of Logic and Computation, Lecture Notes in Computer Science, Vol. 6300, 488\u2013503.","DOI":"10.1007\/978-3-642-15025-8_24"},{"key":"S147106841300063X_ref29","doi-asserted-by":"publisher","DOI":"10.1145\/116825.116836"},{"key":"S147106841300063X_ref28","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068405002619"},{"key":"S147106841300063X_ref38","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-20832-4_20"},{"key":"S147106841300063X_ref18","unstructured":"Eiter T. and Gottlob G. 1993. Complexity results for disjunctive logic programming and application to non-monotonic logics. In Proceedings of the 1993 International Logic Programming Symposium (ILPS), 266\u2013278."}],"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\/S147106841300063X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,23]],"date-time":"2024-05-23T00:11:13Z","timestamp":1716423073000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S147106841300063X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1,10]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["S147106841300063X"],"URL":"https:\/\/doi.org\/10.1017\/s147106841300063x","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1,10]]}}}