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:qucosa:12226
Date22 January 2014
CreatorsStraß, Hannes, Wallner, Johannes Peter
ContributorsUniversität Leipzig, Technische Universität Wien
Source SetsHochschulschriftenserver (HSSS) der SLUB Dresden
LanguageEnglish
Detected LanguageEnglish
Typeinfo:eu-repo/semantics/submittedVersion, doc-type:workingPaper, info:eu-repo/semantics/workingPaper, doc-type:Text
Rightsinfo:eu-repo/semantics/openAccess
Relationurn:nbn:de:bsz:15-qucosa-154857, qucosa:11933

Page generated in 0.002 seconds