Publications in Scientific Journals:
H. Strass, J. P. Wallner:
"Analyzing the computational complexity of abstract dialectical frameworks via approximation fixpoint theory";
Artificial Intelligence,
226
(2015),
34
- 74.
English abstract:
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.
Keywords:
Abstract dialectical frameworks; Computational complexity; Approximation fixpoint theory
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1016/j.artint.2015.05.003
Created from the Publication Database of the Vienna University of Technology.