Omission-based Abstraction for Answer Set Programs

Abstraction is a well-known approach to reduce program complexity by over-approximating the problem with a deliberate loss of information. It has not been considered so far in the context of Answer Set Programming, a convenient tool for problem solving. In this paper, we introduce a method to automatically abstract ground ASP programs that preserves their structure by reducing the vocabulary. Such an abstraction makes it possible to generate partial answer set candidates, which can help with the approximation of reasoning. Faithful (non-spurious) abstractions may be used to represent the projection of answer sets and to guide solvers in answer set construction. In order to deal with the unavoidably introduced spurious answer sets, we employ an ASP debugging approach to help with the refinement of the abstraction. We investigate the usage of such an abstraction to obtain explanations of unsatisfiable programs as a show case.

Authors

• Zeynep G. Saribatur TU Wien
• Thomas Eiter

Keywords

No keywords are indexed for this paper.