Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-08T14:28:56.690Z Has data issue: false hasContentIssue false
  • English
  • Français

Omission-Based Abstraction for Answer Set Programs

Published online by Cambridge University Press:  09 June 2020

ZEYNEP G. SARIBATUR Open the ORCID record for ZEYNEP G. SARIBATUR [Opens in a new window]  and
THOMAS EITER Open the ORCID record for THOMAS EITER [Opens in a new window]
ZEYNEP G. SARIBATUR
Affiliation:
Institute of Logic and Computation, TU Wien, Vienna, Austria (e-mails: [email protected], [email protected])
THOMAS EITER
Affiliation:
Institute of Logic and Computation, TU Wien, Vienna, Austria (e-mails: [email protected], [email protected])
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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.

Keywords

knowledge representation and nonmonotonic reasoninganswer set programmingabstractioninconsistency explanation
Type
Rapid Communication
Information
Theory and Practice of Logic Programming , Volume 21 , Issue 2 , March 2021 , pp. 145 - 195
Check for updates
Creative Commons
Creative Common License - CCCreative Common License - BY
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.
Copyright
© The Author(s), 2020. Published by Cambridge University Press

Footnotes

*

This article is a revised and extended version of the paper presented at the 16th International Conference on Principles of Knowledge Representation and Reasoning (KR 2018), October 30–November 2, 2018, Tempe, Arizona, USA. This work has been supported by the Austrian Science Fund (FWF) project W1255-N23. The authors thank the reviewers for their constructive comments to improve this paper, and the authors are in particular grateful for the suggested correction of an error in the original proof of Theorem 14. The authors acknowledge TU Wien University Library for financial support through its Open Access Funding Programme.

References

Alviano, M., Calimeri, F., Charwat, G., Dao-Tran, M., Dodaro, C., Ianni, G., Krennwallner, T., Kronegger, M., Oetsch, J., Pfandler, A., Pührer, 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–53.Google Scholar
Alviano, M. and Dodaro, C. 2016. Anytime answer set optimization via unsatisfiable core shrinking. Theory and Practice of Logic Programming 16, 5–6, 533–551.CrossRefGoogle Scholar
Alviano, M., Dodaro, C., Järvisalo, M., Maratea, M. and Previti, A. 2018. Cautious reasoning in ASP via minimal models and unsatisfiable cores. Theory and Practice of Logic Programming 18, 3–4, 319–336.CrossRefGoogle Scholar
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–221.Google Scholar
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–79.Google Scholar
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–18.Google Scholar
Banihashemi, B., De Giacomo, G. and Lespérance, Y. 2017. Abstraction in situation calculus action theories. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), 1048–1055.Google Scholar
Brain, M., Gebser, M., Pührer, 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–43.Google Scholar
Brass, S. and Dix, J. 1997. Characterizations of the disjunctive stable semantics by partial evaluation. The Journal of Logic Programming 32, 3, 207–228.CrossRefGoogle Scholar
Brewka, G., Eiter, T. and Truszczyski, M. 2011. Answer set programming at a glance. Communications of the ACM 54, 12, 92–103.CrossRefGoogle Scholar
Buss, S., Krajček, J. and Takeuti, G. 1993. On provably total functions in bounded arithmetic theories. In Arithmetic, Proof Theory and Computational Complexity, Clote, P. and Krajček, J., Eds. Oxford University Press, 116–161.Google Scholar
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–309.Google Scholar
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–468.Google Scholar
Clark, K. L. 1978. Negation as failure. In Logic and Data Bases, Gallaire, H. and Minker, J., Eds. Springer, 293–322.CrossRefGoogle Scholar
Clarke, E., Grumberg, O., Jha, S., Lu, Y. and Veith, H. 2003. Counterexample-guided abstraction refinement for symbolic model checking. Journal of the ACM 50, 5, 752–794.CrossRefGoogle Scholar
Clarke, E. M., Grumberg, O. and Long, D. E. 1994. Model checking and abstraction. ACM Transactions on Programming Languages and Systems (TOPLAS) 16, 5, 1512–1542.CrossRefGoogle Scholar
Cousot, P. and Cousot, R. 1992. Abstract interpretation and application to logic programs. The Journal of Logic Programming 13, 2, 103–179.CrossRefGoogle Scholar
Culberson, J. C. and Schaeffer, J. 1998. Pattern databases. Computational Intelligence 14, 3, 318–334.CrossRefGoogle Scholar
Delgrande, J. P. 2017. A knowledge level account of forgetting. Journal of Artificial Intelligence Research 60, 1165–1213.CrossRefGoogle Scholar
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–1488.Google Scholar
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–293.Google Scholar
Edelkamp, S. 2001. Planning with pattern databases. In Proceedings of the 6th European Conference on Planning (ECP), 13–24.Google Scholar
Eiter, T. and Fink, M. 2003. Uniform equivalence of logic programs under the stable model semantics. In International Conference on Logic Programming. Springer, 224–238.Google Scholar
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ä, I., Eds. Springer, 87–99.Google Scholar
Eiter, T. and Kern-Isberner, G. 2018. A brief survey on forgetting from a knowledge representation and reasoning perspective. KI – Künstliche Intelligenz 33, 1, 9–33.Google Scholar
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–417.Google Scholar
Eiter, T. and Wang, K. 2008. Semantic forgetting in answer set programming. Artificial Intelligence 172, 14, 1644–1672.CrossRefGoogle Scholar
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–212.Google Scholar
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–9.Google Scholar
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–205.Google Scholar
Gebser, M., Kaufmann, B., Kaminski, R., Ostrowski, M., Schaub, T. and Schneider, M. 2011. Potassco: The Potsdam answer set solving collection. AI Communications 24, 2, 107–124.CrossRefGoogle Scholar
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–544.Google Scholar
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–9.Google Scholar
Gebser, M., Pührer, 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–453.Google Scholar
Geißer, F., Keller, T. and Mattmüller, R. 2016. Abstractions for planning with state-dependent action costs. In Proceedings of the 26th International Conference on Automated Planning and Scheduling (ICAPS). 140–148.Google Scholar
Gelfond, M. and Lifschitz, V. 1991. Classical negation in logic programs and disjunctive databases. New Generation Computing 9, 3, 365–385.CrossRefGoogle Scholar
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–66.Google Scholar
Giunchiglia, F. and Walsh, T. 1992. A theory of abstraction. Artificial Intelligence 57, 2–3, 323–389.CrossRefGoogle Scholar
Gonçalves, 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–144.Google Scholar
Gonçalves, R., Knorr, M., Leite, J. and Woltran, S. 2017. When you must forget: Beyond strong persistence when forgetting in answer set programming. Theory and Practice of Logic Programming 17, 5–6, 837–854.CrossRefGoogle Scholar
Helmert, M., Haslum, P., Hoffmann, J. and Nissim, R. 2014. Merge-and-shrink abstraction: A method for generating lower bounds in factored state spaces. Journal of the ACM 61, 3, 16.Google Scholar
Janhunen, T., Niemelä, I., Seipel, D., Simons, P. and You, J.-H. 2006. Unfolding partiality and disjunctions in stable model semantics. ACM Transactions on Computational Logic 7, 1, 1–37.Google Scholar
Janota, M. and Marques-Silva, J. 2016. On the query complexity of selecting minimal sets for monotone predicates. Artificial Intelligence 233, 73–83.CrossRefGoogle Scholar
Knoblock, C. A. 1994. Automatically generating abstractions for planning. Artificial Intelligence 68, 2, 243–302.CrossRefGoogle Scholar
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).Google Scholar
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–508.Google Scholar
Leite, J. 2017. A bird’s-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–22.Google Scholar
Leone, N., Rullo, P. and Scarcello, F. 1997. Disjunctive stable models: Unfounded sets, fixpoint semantics, and computation. Information and Computation 135, 2, 69–112.CrossRefGoogle Scholar
Liffiton, M. H. and Sakallah, K. A. 2008. Algorithms for computing minimal unsatisfiable subsets of constraints. Journal of Automated Reasoning 40, 1, 1–33.Google Scholar
Lifschitz, V., Pearce, D. and Valverde, A. 2001. Strongly equivalent logic programs. ACM Transactions on Computational Logic 2, 4 (October), 526–541.CrossRefGoogle Scholar
Lifschitz, V., Tang, L. R. and Turner, H. 1999. Nested expressions in logic programs. Annals of Mathematics and Artificial Intelligence 25, 3–4, 369–389.CrossRefGoogle Scholar
Lin, F. and Zhao, Y. 2004. ASSAT: Computing answer sets of a logic program by SAT solvers. Artificial Intelligence 157, 1–2, 115–137.CrossRefGoogle Scholar
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–310. 1986. Equivalences of logic programs. In Third International Conference on Logic Programming, E. Shapiro, Ed. Springer, Berlin, Heidelberg, 410–424.Google Scholar
Oetsch, J., Pührer, J. and Tompits, H. 2010. Catching the ouroboros: On debugging non-ground answer-set programs. Theory and Practice of Logic Programming 10, 4–6, 513–529.CrossRefGoogle Scholar
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–75.Google Scholar
Pearce, D. 2004. Simplifying logic programs under answer set semantics. In Logic Programming, Demoen, B. and Lifschitz, V., Eds. Springer, 210–224.CrossRefGoogle Scholar
Pontelli, E., Son, T. C. and Elkhatib, O. 2009. Justifications for logic programs under answer set semantics. Theory and Practice of Logic Programming 9, 1, 1–56.Google Scholar
Reiter, R. 1987. A theory of diagnosis from first principles. Artificial Intelligence 32, 1, 57–95.CrossRefGoogle Scholar
Sacerdoti, E. D. 1974. Planning in a hierarchy of abstraction spaces. Artificial Intelligence 5, 2, 115–135.CrossRefGoogle Scholar
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–362.Google Scholar
Saribatur, Z. G., Schüller, 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–592.Google Scholar
Syrjänen, T. 2006. Debugging inconsistent answer set programs. In Proceedings of the 11th International Workshop on Non-Monotonic Reasoning (NMR), vol. 6, 77–83.Google Scholar
Turner, H. 2003. Strong equivalence made easy: nested expressions and weight constraints. Theory and Practice of Logic Programming 3, 4–5, 609–622.CrossRefGoogle Scholar
Van Gelder, A., Ross, K. A. and Schlipf, J. S. 1991. The well-founded semantics for general logic programs. Journal of the ACM 38, 3, 619–649.CrossRefGoogle Scholar
Watts, D. J. and Strogatz, S. H. 1998. Collective dynamics of “small-world” networks. Nature 393, 440–442.CrossRefGoogle ScholarPubMed
Supplementary material: PDF

Saribatur and Eiter supplementary material

Saribatur and Eiter supplementary material

Download Saribatur and Eiter supplementary material(PDF)
PDF 120.7 KB