Wang, Y., Eiter, T., Yuanlin Zhang, & Lin, F. (2022, November 29). Witnesses for Answer Sets of Logic Programs [Conference Presentation]. TAASP - Workshop on Trends and Applications of Answer Set Programming, Wien, Austria. http://hdl.handle.net/20.500.12708/154231
E192-03 - Forschungsbereich Knowledge Based Systems
-
Date (published):
29-Nov-2022
-
Event name:
TAASP - Workshop on Trends and Applications of Answer Set Programming
en
Event date:
28-Nov-2022 - 29-Nov-2022
-
Event place:
Wien, Austria
-
Keywords:
logic programming; answer set programming
en
Additional information:
In this paper, we propose a notion of reduct for logic pro-
grams and show that each atom in an answer set has a resolution proof
from the reduct with respect to the answer set. Such a resolution proof
provides an explanation of “why a set of atoms is an answer set”. We
then further consider (minimal) sets of rules that will be sufficient to
provide resolution proofs for sets of atoms. Such sets of rules will be
called witnesses and are in the focus of this paper. We study complexity
issues of computing various witnesses and provide algorithms for com-
puting them. In particular, we show that the problem is intractable in
general. Experiments on many well-known ASP and SAT benchmarks
show that computing a minimal witness for an atom of an answer set is
often feasible. In most cases, a resolution proof for an atom is easy to
construct from its witness.
-
Research Areas:
Logic and Computation: 80% Mathematical and Algorithmic Foundations: 20%
