{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T16:53:58Z","timestamp":1773939238149,"version":"3.50.1"},"reference-count":65,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2020,6,9]],"date-time":"2020-06-09T00:00:00Z","timestamp":1591660800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2021,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Abstraction is a well-known approach to simplify a complex problem by over-approximating it with a deliberate loss of information. It was not considered so far in Answer Set Programming (ASP), a convenient tool for problem solving. We introduce a method to automatically abstract ASP programs that preserves their structure by reducing the vocabulary while ensuring an over-approximation (i.e., each original answer set maps to some abstract answer set). This allows for generating partial answer set candidates that can help with approximation of reasoning. Computing the abstract answer sets is intuitively easier due to a smaller search space, at the cost of encountering spurious answer sets. Faithful (non-spurious) abstractions may be used to represent projected answer sets and to guide solvers in answer set construction. For dealing with spurious answer sets, we employ an ASP debugging approach to help with abstraction refinement, which determines atoms as badly omitted and adds them back in the abstraction. As a show case, we apply abstraction to explain unsatisfiability of ASP programs in terms of blocker sets, which are the sets of atoms such that abstraction to them preserves unsatisfiability. Their usefulness is demonstrated by experimental results.<\/jats:p>","DOI":"10.1017\/s1471068420000095","type":"journal-article","created":{"date-parts":[[2020,6,9]],"date-time":"2020-06-09T14:57:38Z","timestamp":1591714658000},"page":"145-195","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":8,"title":["Omission-Based Abstraction for Answer Set Programs"],"prefix":"10.1017","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8690-5043","authenticated-orcid":false,"given":"ZEYNEP G.","family":"SARIBATUR","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6003-6345","authenticated-orcid":false,"given":"THOMAS","family":"EITER","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2020,6,9]]},"reference":[{"key":"S1471068420000095_ref49","first-page":"1","article-title":"Algorithms for computing minimal unsatisfiable subsets of constraints","volume":"1","author":"Liffiton","year":"2008","journal-title":"Journal of Automated Reasoning 40"},{"key":"S1471068420000095_ref5","unstructured":"Arenas, M. , Bertossi, L. E. and Chomicki, J. 1999. Consistent query answers in inconsistent databases. In Proceedings of the 18th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 68\u201379."},{"key":"S1471068420000095_ref11","first-page":"116","volume-title":"Arithmetic, Proof Theory and Computational Complexity","author":"Buss","year":"1993"},{"key":"S1471068420000095_ref23","unstructured":"Eiter, T. and Fink, M. 2003. Uniform equivalence of logic programs under the stable model semantics. In International Conference on Logic Programming. Springer, 224\u2013238."},{"key":"S1471068420000095_ref16","doi-asserted-by":"publisher","DOI":"10.1145\/186025.186051"},{"key":"S1471068420000095_ref31","doi-asserted-by":"publisher","DOI":"10.3233\/AIC-2011-0491"},{"key":"S1471068420000095_ref8","unstructured":"Brain, M. , Gebser, M. , P\u00fchrer, J. , Schaub, T. , Tompits, H. and Woltran, S. 2007. Debugging ASP programs by means of ASP. In Proceedings of the 9th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR). Springer, 31\u201343."},{"key":"S1471068420000095_ref45","doi-asserted-by":"crossref","unstructured":"Kouvaros, P. and Lomuscio, A. 2015. A counter abstraction technique for the verification of robot swarms. In Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI).","DOI":"10.1609\/aaai.v29i1.9442"},{"key":"S1471068420000095_ref7","unstructured":"Banihashemi, B. , De Giacomo, G. and Lesp\u00e9rance, Y. 2017. Abstraction in situation calculus action theories. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), 1048\u20131055."},{"key":"S1471068420000095_ref4","unstructured":"Andres, B. , Kaufmann, B. , Matheis, O. and Schaub, T. 2012. Unsatisfiability-based optimization in clasp. In Technical Communications of the 28th International Conference on Logic Programming, ICLP, vol. 17. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 211\u2013221."},{"key":"S1471068420000095_ref63","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068403001819"},{"key":"S1471068420000095_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-1066(96)00115-X"},{"key":"S1471068420000095_ref22","unstructured":"Edelkamp, S. 2001. Planning with pattern databases. In Proceedings of the 6th European Conference on Planning (ECP), 13\u201324."},{"key":"S1471068420000095_ref36","doi-asserted-by":"publisher","DOI":"10.1007\/BF03037169"},{"key":"S1471068420000095_ref1","unstructured":"Alviano, M. , Calimeri, F. , Charwat, G. , Dao-Tran, M. , Dodaro, C. , Ianni, G. , Krennwallner, T. , Kronegger, M. , Oetsch, J. , Pfandler, A. , P\u00fchrer, J. , Redl, C. , Ricca, F. , Schneider, P. , Schwengerer, M. , Spendier, L. K. , Wallner, J. P. and Xiao, G. 2013. The fourth answer set programming competition: Preliminary report. In Proceedings of the 12th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR). Springer, 42\u201353."},{"key":"S1471068420000095_ref64","doi-asserted-by":"publisher","DOI":"10.1145\/116825.116838"},{"key":"S1471068420000095_ref32","unstructured":"Gebser, M. , Maratea, M. and Ricca, F. 2015. The design of the sixth answer set programming competition. In International Conference on Logic Programming and Nonmonotonic Reasoning. Springer, 531\u2013544."},{"key":"S1471068420000095_ref26","unstructured":"Eiter, T. , Leone, N. , Mateis, C. , Pfeifer, G. and Scarcello, F. 1998. The KR system dlv: Progress report, comparisons and benchmarks. In Proceedings of the 6th International Conference on Principles of Knowledge Representation and Reasoning (KR 1998), 406\u2013417."},{"key":"S1471068420000095_ref61","unstructured":"Saribatur, Z. G. , Sch\u00fcller, P. and Eiter, T. 2019. Abstraction for non-ground answer set programs. In Proceedings of the 16th European Conference on Logics in Artificial Intelligence (JELIA). Lecture Notes in Computer Science. Springer, 576\u2013592."},{"key":"S1471068420000095_ref65","doi-asserted-by":"publisher","DOI":"10.1038\/30918"},{"key":"S1471068420000095_ref35","doi-asserted-by":"crossref","unstructured":"Gei\u00dfer, F. , Keller, T. and Mattm\u00fcller, R. 2016. Abstractions for planning with state-dependent action costs. In Proceedings of the 26th International Conference on Automated Planning and Scheduling (ICAPS). 140\u2013148.","DOI":"10.1609\/icaps.v26i1.13742"},{"key":"S1471068420000095_ref30","unstructured":"Gebser, M. , Kaminski, R. , Kaufmann, B. , Ostrowski, M. , Schaub, T. and Thiele, S. 2008. Engineering an incremental ASP solver. In Proceedings of the 24th International Conference on Logic Programming (ICLP), 190\u2013205."},{"key":"S1471068420000095_ref12","unstructured":"Calimeri, F. , Faber, W. , Gebser, M. , Ianni, G. , Kaminski, R. , Krennwallner, T. , Leone, N. , Maratea, M. , Ricca, F. and Schaub, T. 2020. ASP-core-2 input language format. Theory and Practice of Logic Programming 20, 2, 294\u2013309."},{"key":"S1471068420000095_ref19","doi-asserted-by":"publisher","DOI":"10.1613\/jair.5530"},{"key":"S1471068420000095_ref24","unstructured":"Eiter, T. , Fink, M. , Tompits, H. and Woltran, S. 2004. Simplifying logic programs under uniform and strong equivalence. In Proceedings of the 7th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2004), Lifschitz, V. and Niemel\u00e4, I. , Eds. Springer, 87\u201399."},{"key":"S1471068420000095_ref58","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(87)90062-2"},{"key":"S1471068420000095_ref28","unstructured":"Faber, W. , Leone, N. and Pfeifer, G. 2004. Recursive aggregates in disjunctive logic programs: Semantics and complexity. In Proceedings of the 9th European Conference on Logics in Artificial Intelligence (JELIA). Lecture Notes in Computer Science, vol. 3229. Springer, 200\u2013212."},{"key":"S1471068420000095_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(92)90030-7"},{"key":"S1471068420000095_ref55","unstructured":"Osorio, M. , Navarro, J. A. and Arrazola, J. 2002. Equivalence in answer set programming. In Logic Based Program Synthesis and Transformation, A. Pettorossi, Ed. Springer, Berlin , Heidelberg, 57\u201375."},{"key":"S1471068420000095_ref21","unstructured":"Dodaro, C. , Gasteiger, P. , Musitsch, B. , Ricca, F. and Shchekotykhin, K. 2015. Interactive debugging of non-ground ASP programs. In Proceedings of the 13th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR). Springer, 279\u2013293."},{"key":"S1471068420000095_ref50","doi-asserted-by":"publisher","DOI":"10.1145\/383779.383783"},{"key":"S1471068420000095_ref47","unstructured":"Leite, J. 2017. A bird\u2019s-eye view of forgetting in answer-set programming. In Proceedings of the 14th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR), Balduccini, M. and Janhunen, T. , Eds. Lecture Notes in Computer Science, vol. 10377. Springer, 10\u201322."},{"key":"S1471068420000095_ref10","doi-asserted-by":"publisher","DOI":"10.1145\/2043174.2043195"},{"key":"S1471068420000095_ref25","first-page":"9","article-title":"A brief survey on forgetting from a knowledge representation and reasoning perspective","volume":"1","author":"Eiter","year":"2018","journal-title":"KI \u2013 K\u00fcnstliche Intelligenz 33"},{"key":"S1471068420000095_ref34","unstructured":"Gebser, M. , P\u00fchrer, J. , Schaub, T. and Tompits, H. 2008. A meta-programming technique for debugging answer-set programs. In Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI), vol. 8, 448\u2013453."},{"key":"S1471068420000095_ref51","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018978005636"},{"key":"S1471068420000095_ref15","doi-asserted-by":"publisher","DOI":"10.1145\/876638.876643"},{"key":"S1471068420000095_ref27","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2008.05.002"},{"key":"S1471068420000095_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-3384-5_11"},{"key":"S1471068420000095_ref44","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(94)90069-8"},{"key":"S1471068420000095_ref40","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068417000382"},{"key":"S1471068420000095_ref18","doi-asserted-by":"publisher","DOI":"10.1111\/0824-7935.00065"},{"key":"S1471068420000095_ref39","unstructured":"Gon\u00e7alves, R. , Knorr, M. and Leite, J. 2016. The ultimate guide to forgetting in answer set programming. In Proceedings of the 15th International Conference on Principles of Knowledge Representation and Reasoning (KR). AAAI Press, 135\u2013144."},{"key":"S1471068420000095_ref59","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(74)90026-5"},{"key":"S1471068420000095_ref52","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2004.04.004"},{"key":"S1471068420000095_ref56","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27775-0_15"},{"key":"S1471068420000095_ref57","first-page":"1","article-title":"Justifications for logic programs under answer set semantics","volume":"1","author":"Pontelli","year":"2009","journal-title":"Theory and Practice of Logic Programming 9"},{"key":"S1471068420000095_ref48","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2630"},{"key":"S1471068420000095_ref20","unstructured":"Delgrande, J. P. and Wang, K. 2015. A syntax-independent approach to forgetting in disjunctive logic programs. In Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI), 1482\u20131488."},{"key":"S1471068420000095_ref3","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068418000145"},{"key":"S1471068420000095_ref38","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(92)90021-O"},{"key":"S1471068420000095_ref43","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2016.01.002"},{"key":"S1471068420000095_ref60","unstructured":"Sagiv, Y. 1987. Optimizing datalog programs. In Proceedings of the 6th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS). ACM, New York, NY, USA, 349\u2013362."},{"key":"S1471068420000095_ref37","unstructured":"Giunchiglia, E. , Lierler, Y. and Maratea, M. 2004. SAT-based answer set programming. In Proceedings of the 19th National Conference on Artificial Intelligence (AAAI), 61\u201366."},{"key":"S1471068420000095_ref2","doi-asserted-by":"publisher","DOI":"10.1017\/S147106841600020X"},{"key":"S1471068420000095_ref41","first-page":"16","article-title":"Merge-and-shrink abstraction: A method for generating lower bounds in factored state spaces","volume":"3","author":"Helmert","year":"2014","journal-title":"Journal of the ACM 61"},{"key":"S1471068420000095_ref46","unstructured":"Lee, J. 2005. A model-theoretic counterpart of loop formulas. In Proceedings of the 19th International Joint conference on Artificial intelligence (IJCAI), vol. 5, 503\u2013508."},{"key":"S1471068420000095_ref29","unstructured":"Gaggl, S. A. , Linsbichler, T. , Maratea, M. and Woltran, S. 2016. Introducing the second international competition on computational models of argumentation. In Proceedings of the International Workshop on Systems and Algorithms for Formal Argumentation (SAFA), 4\u20139."},{"key":"S1471068420000095_ref13","unstructured":"Cerutti, F. , Giacomin, M. and Vallati, M. 2016. Generating structured argumentation frameworks: AFBenchGen2. In Proceedings of the 6th International Conference on Computational Models of Argument (COMMA 2016), Baroni, P. , Gordon, T. F. , Scheffler, T. and Stede, M. , Eds. Frontiers in Artificial Intelligence and Applications, vol. 287. IOS Press, 467\u2013468."},{"key":"S1471068420000095_ref33","unstructured":"Gebser, M. , Maratea, M. and Ricca, F. 2017. The design of the seventh answer set programming competition. In International Conference on Logic Programming and Nonmonotonic Reasoning. Springer, 3\u20139."},{"key":"S1471068420000095_ref62","unstructured":"Syrj\u00e4nen, T. 2006. Debugging inconsistent answer set programs. In Proceedings of the 11th International Workshop on Non-Monotonic Reasoning (NMR), vol. 6, 77\u201383."},{"key":"S1471068420000095_ref6","unstructured":"Balduccini, M. and Gelfond, M. 2003. Logic programs with consistency-restoring rules. In Proceedings of the International Symposium on Logical Formalization of Commonsense Reasoning, AAAI 2003 Spring Symposium Series, McCarthy, J. and Williams, M.-A. , Eds. AAAI Press, 9\u201318."},{"key":"S1471068420000095_ref42","first-page":"1","article-title":"Unfolding partiality and disjunctions in stable model semantics","volume":"1","author":"Janhunen","year":"2006","journal-title":"ACM Transactions on Computational Logic 7"},{"key":"S1471068420000095_ref53","unstructured":"Lynce, I. and Silva, J. P. M. 2004. On computing minimum unsatisfiable cores. In Proceedings of the 7th International Conference on Theory and Applications of Satisfiability Testing (SAT), 305\u2013310. 1986. Equivalences of logic programs. In Third International Conference on Logic Programming, E. Shapiro, Ed. Springer, Berlin , Heidelberg, 410\u2013424."},{"key":"S1471068420000095_ref54","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068410000256"}],"updated-by":[{"DOI":"10.1017\/s1471068420000125","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2020,6,9]],"date-time":"2020-06-09T00:00:00Z","timestamp":1591660800000}}],"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\/S1471068420000095","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,27]],"date-time":"2022-10-27T11:11:30Z","timestamp":1666869090000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068420000095\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,9]]},"references-count":65,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,3]]}},"alternative-id":["S1471068420000095"],"URL":"https:\/\/doi.org\/10.1017\/s1471068420000095","relation":{"correction":[{"id-type":"doi","id":"10.1017\/S1471068420000125","asserted-by":"object"}]},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,9]]},"assertion":[{"value":"\u00a9 The Author(s), 2020. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}