<div class="csl-bib-body">
<div class="csl-entry">Wang, Y., Eiter, T., Zhang, Y., & Lin, F. (2023). Witnesses for Answer Sets of Logic Programs. <i>ACM Transactions on Computational Logic</i>, Article 3568955. https://doi.org/10.1145/3568955</div>
</div>
-
dc.identifier.issn
1529-3785
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/144336
-
dc.description.abstract
In this paper, we consider Answer Set Programming (ASP). It is a declarative problem solving paradigm that can be used to encode a problem as a logic program whose answer sets correspond to the solutions of the problem. It has been widely applied in various domains in AI and beyond. Given that answer sets are supposed to yield solutions to the original problem, the question of “why a set of atoms is an answer set” becomes important for both semantics understanding and program debugging. It has been well investigated for normal logic programs. However, for the class of disjunctive logic programs, which is a substantial extension of that of normal logic programs, this question has not been addressed much. In this paper, we propose a notion of reduct for disjunctive logic programs and show how it can provide answers to the aforementioned question. First of all, we show that for each answer set, its reduct provides a resolution proof for each atom in it. 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 the focus of this paper. We study complexity issues of computing various witnesses and provide algorithms for computing them. In particular, we show that the problem is tractable for normal and headcycle-free disjunctive logic programs, but intractable for general disjunctive logic programs. We also conducted some experiments and found that for many well-known ASP and SAT benchmarks, computing a minimal witness for an atom of an answer set is often feasible.
en
dc.language.iso
en
-
dc.publisher
ASSOC COMPUTING MACHINERY
-
dc.relation.ispartof
ACM Transactions on Computational Logic
-
dc.subject
logic programming
en
dc.subject
answer set semantics
en
dc.subject
minimal models
en
dc.title
Witnesses for Answer Sets of Logic Programs
en
dc.type
Article
en
dc.type
Artikel
de
dc.contributor.affiliation
Texas Tech University
-
dc.type.category
Original Research Article
-
tuw.journal.peerreviewed
true
-
tuw.peerreviewed
true
-
wb.publication.intCoWork
International Co-publication
-
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
-
dcterms.isPartOf.title
ACM Transactions on Computational Logic
-
tuw.publication.orgunit
E192-03 - Forschungsbereich Knowledge Based Systems