Return to search

Analyzing the Computational Complexity of Abstract Dialectical Frameworks via Approximation Fixpoint Theory

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.

Identiferoai:union.ndltd.org:DRESDEN/oai:qucosa.de:bsz:15-qucosa-129614
Date22 January 2014
CreatorsStraß, Hannes, Wallner, Johannes Peter
ContributorsUniversität Leipzig, Fakultät für Mathematik und Informatik, Technische Universität Wien, Fakultät für Informatik, Universität Leipzig, Fakultät für Mathematik und Informatik
PublisherUniversitätsbibliothek Leipzig
Source SetsHochschulschriftenserver (HSSS) der SLUB Dresden
LanguageEnglish
Detected LanguageEnglish
Typedoc-type:workingPaper
Formatapplication/pdf
Relationdcterms:isPartOf:Technical report / Faculty of Mathematics and Computer Science; Institute of Computer Science ; 2013,2

Page generated in 0.002 seconds