AAAI Publications, Fourteenth International Conference on the Principles of Knowledge Representation and Reasoning

Font Size: 
Analyzing the Computational Complexity of Abstract Dialectical Frameworks via Approximation Fixpoint Theory
Hannes Strass, Johannes Peter Wallner

Last modified: 2014-05-04


Abstract dialectical frameworks (ADFs) have recently been proposed as a versatile generalization of Dung's abstract argumentation frameworks (AFs). In this paper, we present a comprehensive analysis of the computational complexity of ADFs. Our results show that while ADFs are one level up in the polynomial hierarchy compared to AFs, there is a useful subclass of ADFs which is as complex as AFs while arguably offering more modeling capacities. As a technical vehicle, we employ the approximation fixpoint theory of Denecker, Marek and TruszczyƄski, thus showing that it is also a useful tool for complexity analysis of operator-based semantics.


Abstract argumentation; complexity analysis; approximation fixpoint theory

Full Text: PDF