<div class="csl-bib-body">
<div class="csl-entry">Wang, Y., Eiter, T., Yuanlin Zhang, & Lin, F. (2022, November 29). <i>Witnesses for Answer Sets of Logic Programs</i> [Conference Presentation]. TAASP - Workshop on Trends and Applications of Answer Set Programming, Wien, Austria. http://hdl.handle.net/20.500.12708/154231</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/154231
-
dc.description
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.
-
dc.language.iso
en
-
dc.subject
logic programming
en
dc.subject
answer set programming
en
dc.title
Witnesses for Answer Sets of Logic Programs
en
dc.type
Presentation
en
dc.type
Vortrag
de
dc.contributor.affiliation
Texas Tech University
-
dc.type.category
Conference Presentation
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.id
C4
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.name
Mathematical and Algorithmic Foundations
-
tuw.researchTopic.value
80
-
tuw.researchTopic.value
20
-
tuw.publication.orgunit
E192-03 - Forschungsbereich Knowledge Based Systems
-
tuw.author.orcid
0000-0001-6003-6345
-
tuw.event.name
TAASP - Workshop on Trends and Applications of Answer Set Programming