Article contents
Omission-Based Abstraction for Answer Set Programs
Published online by Cambridge University Press: 09 June 2020
Abstract
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
- Type
- Rapid Communication
- Information
- Creative Commons
- 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
A correction has been issued for this article:
- 5
- Cited by
Linked content
Please note a has been issued for this article.