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.
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa.de:bsz:15-qucosa-129614 |
| Date | 22 January 2014 |
| Creators | Straß, Hannes, Wallner, Johannes Peter |
| Contributors | Universitä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 |
| Publisher | Universitätsbibliothek Leipzig |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | English |
| Detected Language | English |
| Type | doc-type:workingPaper |
| Format | application/pdf |
| Relation | dcterms:isPartOf:Technical report / Faculty of Mathematics and Computer Science; Institute of Computer Science ; 2013,2 |
Page generated in 0.0022 seconds