Omission-Based Abstraction for Answer Set Programs
Theory and Practice of Logic Programming · 2021-03 · 21 (2) · 145-195
DOI: 10.1017/s1471068420000095 ↗Kurz gefasst
Fachartikel in der Zeitschrift Theory and Practice of Logic Programming, online erschienen am 09.06.2020. Verfasst von ZEYNEP G. SARIBATUR und 1 weiteren Autor:innen. Die Arbeit wurde bisher 10-mal zitiert (Crossref) und nennt 65 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
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.
Zitieren
APA
SARIBATUR, Z. G., & EITER, T. (2021). Omission-Based Abstraction for Answer Set Programs. Theory and Practice of Logic Programming, 21(2), 145-195. https://doi.org/10.1017/s1471068420000095
Vancouver
SARIBATUR ZG, EITER T. Omission-Based Abstraction for Answer Set Programs. Theory and Practice of Logic Programming. 2021;21(2):145-195. doi:10.1017/s1471068420000095
BibTeX
@article{SARIBATUR2021,
author = {SARIBATUR, ZEYNEP G. and EITER, THOMAS},
title = {Omission-Based Abstraction for Answer Set Programs},
journal = {Theory and Practice of Logic Programming},
year = {2021},
volume = {21},
number = {2},
pages = {145--195},
doi = {10.1017/s1471068420000095}
}
EUVIMED