- AutorIn
- Dr. rer. nat. Hannes Straß
- Dipl.-Ing. Johannes Peter Wallner
- Titel
- Analyzing the Computational Complexity of Abstract Dialectical Frameworks via Approximation Fixpoint Theory
- Zitierfähige Url:
- https://nbn-resolving.org/urn:nbn:de:bsz:15-qucosa-129614
- Schriftenreihe
- Technical report / Leipzig University, Faculty of Mathematics and Computer Science; Institute of Computer Science
- Bandnummer
- 2013,2
- Erstveröffentlichung
- 2013
- ISSN
- 1430-3701
- Abstract (EN)
- 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.
- Freie Schlagwörter (DE)
- Wissensrepräsentation, Argumentation, Komplexitätsanalyse
- Freie Schlagwörter (EN)
- Knowledge representation, Abstract argumentation, Approximation fixpoint theory, Complexity analysis, Abstract dialectical frameworks
- Herausgeber (Institution)
- Universität Leipzig
- Technische Universität Wien
- Version / Begutachtungsstatus
- eingereichte Version / Preprint
- URN Qucosa
- urn:nbn:de:bsz:15-qucosa-129614
- Veröffentlichungsdatum Qucosa
- 22.01.2014
- Dokumenttyp
- Forschungsbericht
- Sprache des Dokumentes
- Englisch