Title: Complexity Results and Algorithms for Extension Enforcement in Abstract Argumentation
Language: English
Authors: Wallner, Johannes 
Niskanen, Andreas 
Järvisalo, Matti 
Category: Original Research Article
Issue Date: 2017
Journal: Journal of Artificial Intelligence Research 
ISSN: 1076-9757
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.
DOI: 10.1613/jair.5415
Library ID: AC15244167
URN: urn:nbn:at:at-ubtuw:3-4526
Organisation: E192 - Institut für Logic and Computation 
Publication Type: Article
Appears in Collections:Article

Files in this item:

Page view(s)

checked on Jul 24, 2021


checked on Jul 24, 2021

Google ScholarTM


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.