Go to page

Bibliographic Metadata

Complexity Results and Algorithms for Extension Enforcement in Abstract Argumentation
AuthorWallner, Johannes P. ; Niskanen, Andreas ; Järvisalo, Matti In der Gemeinsamen Normdatei der DNB nachschlagen
Published in
Journal of Artificial Intelligence Research, 2017, Vol. 60, page 1-40
PublishedAI Access Foundation, 2017
Published version
The final publication is available at https://doi.org/10.1613/jair.5415.
Document typeJournal Article
Project-/ReportnumberAustrian Science Fund (FWF): P30168-N31
URNurn:nbn:at:at-ubtuw:3-4526 Persistent Identifier (URN)
 The work is publicly available
Complexity Results and Algorithms for Extension Enforcement in Abstract Argumentation [1.16 mb]
Abstract (English)

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.

The PDF-Document has been downloaded 5 times.