Go to page
 

Bibliographic Metadata

Title
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
Edition
Published version
Annotation
The final publication is available at https://doi.org/10.1613/jair.5415.
LanguageEnglish
Document typeJournal Article
Project-/ReportnumberAustrian Science Fund (FWF): P30168-N31
ISSN1076-9757
URNurn:nbn:at:at-ubtuw:3-4526 Persistent Identifier (URN)
DOI10.1613/jair.5415 
Restriction-Information
 The work is publicly available
Files
Complexity Results and Algorithms for Extension Enforcement in Abstract Argumentation [1.16 mb]
Links
Reference
Classification
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.

Stats
The PDF-Document has been downloaded 5 times.