<div class="csl-bib-body">
<div class="csl-entry">Wallner, J., Niskanen, A., & Järvisalo, M. (2017). Complexity Results and Algorithms for Extension Enforcement in Abstract Argumentation. <i>Journal of Artificial Intelligence Research</i>, <i>60</i>, 1–40. https://doi.org/10.1613/jair.5415</div>
</div>
-
dc.identifier.issn
1076-9757
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/64
-
dc.description
The final publication is available at <a href="https://doi.org/10.1613/jair.5415" target="_blank">https://doi.org/10.1613/jair.5415</a>.
-
dc.description
The final publication is available via <a href="https://doi.org/10.1613/jair.5415" target="_blank">https://doi.org/10.1613/jair.5415</a>.
-
dc.description.abstract
Argumentation is an active area of modern artificial intelligence (AI) research, with connections to a range of fields, from computational complexity theory and knowledge representation and reasoning to philosophy and social sciences, as well as application-oriented work in domains such as legal reasoning, multi-agent systems, and decision support. Argumentation frameworks (AFs) of abstract argumentation have become the graph-based formal model of choice for many approaches to argumentation in AI, with semantics defining sets of jointly acceptable arguments, i.e., extensions. Understanding the dynamics of AFs has been recently recognized as an important topic in the study of argumentation in AI. In this work, we focus on the so-called extension enforcement problem in abstract argumentation as a recently proposed form of argumentation dynamics. We provide a nearly complete computational complexity map of argument-fixed extension enforcement under various major AF semantics, with results ranging from polynomial-time algorithms to completeness for the second level of the polynomial hierarchy. Complementing the complexity results, we propose algorithms for NP-hard extension enforcement based on constraint optimization under the maximum satisfiability (MaxSAT) paradigm. Going beyond NP, we propose novel MaxSAT-based counterexample-guided abstraction refinement procedures for the second-level complete problems and present empirical results on a prototype system constituting the first approach to extension enforcement in its generality.
en
dc.description.sponsorship
Austrian Science Funds (FWF)
-
dc.language
English
-
dc.language.iso
en
-
dc.publisher
AI ACCESS FOUNDATION
-
dc.relation.ispartof
Journal of Artificial Intelligence Research
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.title
Complexity Results and Algorithms for Extension Enforcement in Abstract Argumentation
en
dc.type
Article
en
dc.type
Artikel
de
dc.rights.license
Urheberrechtsschutz
de
dc.rights.license
In Copyright
en
dc.contributor.affiliation
University of Helsinki, Finland
-
dc.contributor.affiliation
University of Helsinki, Finland
-
dc.description.startpage
1
-
dc.description.endpage
40
-
dc.relation.grantno
P30168-N31
-
dc.rights.holder
2017 AI Access Foundation
-
dc.type.category
Original Research Article
-
tuw.container.volume
60
-
tuw.journal.peerreviewed
true
-
tuw.peerreviewed
true
-
tuw.version
vor
-
dcterms.isPartOf.title
Journal of Artificial Intelligence Research
-
tuw.publication.orgunit
E192 - Institut für Logic and Computation
-
tuw.publisher.doi
10.1613/jair.5415
-
dc.identifier.eissn
1943-5037
-
dc.identifier.libraryid
AC15244167
-
dc.description.numberOfPages
40
-
dc.identifier.urn
urn:nbn:at:at-ubtuw:3-4526
-
tuw.author.orcid
0000-0002-3051-1966
-
tuw.author.orcid
0000-0003-2572-063X
-
dc.rights.identifier
Urheberrechtsschutz
de
dc.rights.identifier
In Copyright
en
item.openaccessfulltext
Open Access
-
item.openairecristype
http://purl.org/coar/resource_type/c_2df8fbb1
-
item.grantfulltext
open
-
item.languageiso639-1
en
-
item.openairetype
research article
-
item.fulltext
with Fulltext
-
item.cerifentitytype
Publications
-
crisitem.author.dept
E192-02 - Forschungsbereich Databases and Artificial Intelligence