{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T16:51:13Z","timestamp":1762102273596,"version":"3.37.3"},"reference-count":53,"publisher":"Cambridge University Press (CUP)","issue":"3-4","license":[{"start":{"date-parts":[[2018,8,10]],"date-time":"2018-08-10T00:00:00Z","timestamp":1533859200000},"content-version":"unspecified","delay-in-days":40,"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":[[2018,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Answer Set Programming (ASP) is a logic-based knowledge representation framework, supporting\u2014among other reasoning modes\u2014the central task of query answering. In the propositional case, query answering amounts to computing cautious consequences of the input program among the atoms in a given set of candidates, where a cautious consequence is an atom belonging to all stable models. Currently, the most efficient algorithms either iteratively verify the existence of a stable model of the input program extended with the complement of one candidate, where the candidate is heuristically selected, or introduce a clause enforcing the falsity of at least one candidate, so that the solver is free to choose which candidate to falsify at any time during the computation of a stable model. This paper introduces new algorithms for the computation of cautious consequences, with the aim of driving the solver to search for stable models discarding more candidates. Specifically, one of such algorithms enforces minimality on the set of true candidates, where different notions of minimality can be used, and another takes advantage of unsatisfiable cores computation. The algorithms are implemented in<jats:sc>wasp<\/jats:sc>, and experiments on benchmarks from the latest ASP competitions show that the new algorithms perform better than the state of the art.<\/jats:p>","DOI":"10.1017\/s1471068418000145","type":"journal-article","created":{"date-parts":[[2018,8,10]],"date-time":"2018-08-10T09:44:17Z","timestamp":1533894257000},"page":"319-336","source":"Crossref","is-referenced-by-count":6,"title":["Cautious reasoning in ASP via minimal models and unsatisfiable cores"],"prefix":"10.1017","volume":"18","author":[{"given":"MARIO","family":"ALVIANO","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5617-5286","authenticated-orcid":false,"given":"CARMINE","family":"DODARO","sequence":"additional","affiliation":[]},{"given":"MATTI","family":"J\u00c4RVISALO","sequence":"additional","affiliation":[]},{"given":"MARCO","family":"MARATEA","sequence":"additional","affiliation":[]},{"given":"ALESSANDRO","family":"PREVITI","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2018,8,10]]},"reference":[{"key":"S1471068418000145_ref14","first-page":"282","volume-title":"Datalog Reloaded","author":"Alviano","year":"2010"},{"key":"S1471068418000145_ref2","first-page":"2:1","volume-title":"Technical Communications of the International Conference on Logic Programming","author":"Alviano","year":"2017"},{"key":"S1471068418000145_ref41","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2016.01.002"},{"key":"S1471068418000145_ref40","doi-asserted-by":"crossref","first-page":"161","DOI":"10.3233\/AIC-140640","article-title":"Algorithms for computing backbones of propositional formulae","volume":"28","author":"Janota","year":"2015","journal-title":"AI Communications"},{"key":"S1471068418000145_ref46","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068411000640"},{"key":"S1471068418000145_ref24","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068412000105"},{"key":"S1471068418000145_ref29","doi-asserted-by":"publisher","DOI":"10.1145\/261124.261126"},{"volume-title":"Knowledge Representation, Reasoning and Declarative Problem Solving","year":"2010","author":"Baral","key":"S1471068418000145_ref17"},{"key":"S1471068418000145_ref33","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2012.04.001"},{"key":"S1471068418000145_ref42","doi-asserted-by":"publisher","DOI":"10.1609\/aimag.v37i3.2672"},{"key":"S1471068418000145_ref22","doi-asserted-by":"publisher","DOI":"10.1023\/A:1006291616338"},{"key":"S1471068418000145_ref15","first-page":"1034","volume-title":"AAAI Conference on Artificial Intelligence","author":"Amendola","year":"2017"},{"key":"S1471068418000145_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2012.04.008"},{"key":"S1471068418000145_ref18","first-page":"385","volume-title":"AAAI Conference on Artificial Intelligence","author":"Brewka","year":"2007"},{"key":"S1471068418000145_ref51","doi-asserted-by":"crossref","unstructured":"Previti A. and J\u00e4rvisalo M. 2018. A preference-based approach to backbone computation with application to argumentation. In ACM\/SIGAPP Symposium on Applied Computing. ACM. To appear.","DOI":"10.1145\/3167132.3167230"},{"key":"S1471068418000145_ref28","doi-asserted-by":"publisher","DOI":"10.1007\/11546207_2"},{"key":"S1471068418000145_ref4","doi-asserted-by":"publisher","DOI":"10.1017\/S147106841600020X"},{"key":"S1471068418000145_ref53","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1109\/HLDVT.2011.6113981","volume-title":"IEEE International High Level Design Validation and Test Workshop","author":"Zhu","year":"2011"},{"key":"S1471068418000145_ref23","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2015.09.008"},{"key":"S1471068418000145_ref39","doi-asserted-by":"publisher","DOI":"10.1609\/aimag.v37i3.2671"},{"key":"S1471068418000145_ref13","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068410000244"},{"key":"S1471068418000145_ref49","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-61208-4_18"},{"key":"S1471068418000145_ref5","doi-asserted-by":"crossref","unstructured":"Alviano M. and Dodaro C. 2017. Unsatisfiable core shrinking for anytime answer set optimization. In International Joint Conference on Artificial Intelligence. ijcai.org, 4781\u20134785.","DOI":"10.24963\/ijcai.2017\/666"},{"key":"S1471068418000145_ref19","doi-asserted-by":"publisher","DOI":"10.1145\/2043174.2043195"},{"key":"S1471068418000145_ref38","first-page":"184","volume-title":"International Conference on Automated Deduction","author":"Hasegawa","year":"2000"},{"key":"S1471068418000145_ref20","unstructured":"Brewka G. , Roelofsen F. , and Serafini L. 2007. Contextual default reasoning. In International Joint Conference on Artificial Intelligence. 268\u2013273."},{"key":"S1471068418000145_ref26","first-page":"99","volume-title":"Italian Conference on Computational Logic","author":"Dodaro","year":"2011"},{"key":"S1471068418000145_ref27","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068416000284"},{"key":"S1471068418000145_ref16","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068403001832"},{"key":"S1471068418000145_ref1","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068417000278"},{"key":"S1471068418000145_ref50","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018930122475"},{"key":"S1471068418000145_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-23264-5_5"},{"key":"S1471068418000145_ref43","unstructured":"Koshimura M. , Nabeshima H. , Fujita H. , and Hasegawa R. 2009. Minimal model generation with respect to an atom set. In International Workshop on First-Order Theorem Proving. CEUR Workshop Proceedings, vol. 556. CEUR-WS.org."},{"key":"S1471068418000145_ref25","doi-asserted-by":"publisher","DOI":"10.1007\/s10601-010-9095-y"},{"key":"S1471068418000145_ref30","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2008.04.002"},{"key":"S1471068418000145_ref31","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-20895-9_39"},{"key":"S1471068418000145_ref52","doi-asserted-by":"publisher","DOI":"10.1109\/12.769433"},{"key":"S1471068418000145_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-61660-5_19"},{"key":"S1471068418000145_ref8","article-title":"Optimum stable model search: algorithms and implementation","author":"Alviano","year":"2015","journal-title":"Journal of Logic and Computation"},{"key":"S1471068418000145_ref45","doi-asserted-by":"publisher","DOI":"10.1609\/aimag.v37i3.2670"},{"key":"S1471068418000145_ref34","doi-asserted-by":"publisher","DOI":"10.1613\/jair.5373"},{"key":"S1471068418000145_ref36","doi-asserted-by":"publisher","DOI":"10.1007\/BF03037169"},{"key":"S1471068418000145_ref48","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-60085-2_17"},{"key":"S1471068418000145_ref37","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-009-9113-1"},{"key":"S1471068418000145_ref44","doi-asserted-by":"publisher","DOI":"10.1145\/1149114.1149117"},{"key":"S1471068418000145_ref21","unstructured":"Brochenin R. and Maratea M. 2015. Abstract answer set solvers for cautious reasoning. In Technical Communications of the International Conference on Logic Programming. CEUR Workshop Proceedings, vol. 1433. CEUR-WS.org."},{"key":"S1471068418000145_ref10","first-page":"2677","volume-title":"International Joint Conference on Artificial Intelligence","author":"Alviano","year":"2015"},{"key":"S1471068418000145_ref11","doi-asserted-by":"crossref","first-page":"125","DOI":"10.3233\/AIC-2011-0492","article-title":"Dynamic magic sets and super-coherent answer set programs","volume":"24","author":"Alviano","year":"2011","journal-title":"AI Communications"},{"key":"S1471068418000145_ref9","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068414000325"},{"key":"S1471068418000145_ref47","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068415000320"},{"volume-title":"AAAI Conference on Artificial Intelligence","year":"2013","author":"Gebser","key":"S1471068418000145_ref32"},{"key":"S1471068418000145_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40564-8_6"},{"key":"S1471068418000145_ref35","first-page":"1070","volume-title":"International Conference and Symposium on Logic Programming","author":"Gelfond","year":"1988"}],"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\/S1471068418000145","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,7]],"date-time":"2020-11-07T15:08:48Z","timestamp":1604761728000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068418000145\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7]]},"references-count":53,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["S1471068418000145"],"URL":"https:\/\/doi.org\/10.1017\/s1471068418000145","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"type":"print","value":"1471-0684"},{"type":"electronic","value":"1475-3081"}],"subject":[],"published":{"date-parts":[[2018,7]]}}}