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

被引：0
|
作者：
Strass, Hannes [1 ]
Wallner, Johannes Peter [2 ]
机构：
[1] Univ Leipzig, Comp Sci Inst, Leipzig, Germany
[2] Vienna Univ Technol, Inst Informat Syst, Vienna, Austria
来源：
FOURTEENTH INTERNATIONAL CONFERENCE ON THE PRINCIPLES OF KNOWLEDGE REPRESENTATION AND REASONING | 2014年
关键词：
ARGUMENTATION; DEFAULT; CARNEADES;
D O I：
暂无
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
The 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 Truszczynski, thus showing that it is also a useful tool for complexity analysis of operator-based semantics.
引用
收藏
页码：101 / 110
页数：10
相关论文
共 16 条
  • [1] Analyzing the computational complexity of abstract dialectical frameworks via approximation fixpoint theory
    Strass, Hannes
    Wallner, Johannes Peter
    ARTIFICIAL INTELLIGENCE, 2015, 226 : 34 - 74
  • [2] Weighted Abstract Dialectical Frameworks through the Lens of Approximation Fixpoint Theory
    Bogaerts, Bart
    THIRTY-THIRD AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE / THIRTY-FIRST INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE CONFERENCE / NINTH AAAI SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE, 2019, : 2686 - 2693
  • [3] On the Computational Complexity of Naive-based Semantics for Abstract Dialectical Frameworks
    Gaggl, Sarah Alice
    Rudolph, Sebastian
    Strass, Hannes
    PROCEEDINGS OF THE TWENTY-FOURTH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE (IJCAI), 2015, : 2985 - 2991
  • [4] HEX Semantics via Approximation Fixpoint Theory
    Antic, Christian
    Eiter, Thomas
    Fink, Michael
    LOGIC PROGRAMMING AND NONMONOTONIC REASONING (LPNMR 2013), 2013, 8148 : 102 - 115
  • [5] On the decomposition of abstract dialectical frameworks and the complexity of naive-based semantics
    Gaggl S.A.
    Rudolph S.
    Strass H.
    Journal of Artificial Intelligence Research, 2021, 70 : 1 - 64
  • [6] On the Decomposition of Abstract Dialectical Frameworks and the Complexity of Naive-based Semantics
    Gaggl, Sarah Alice
    Rudolph, Sebastian
    Strass, Hannes
    JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, 2021, 70 : 1 - 64
  • [7] Analyzing Semantics of Aggregate Answer Set Programming Using Approximation Fixpoint Theory
    Vanbesien, Linde
    Bruynooghe, Maurice
    Denecker, Marc
    THEORY AND PRACTICE OF LOGIC PROGRAMMING, 2022, 22 (04) : 523 - 537
  • [8] The Computational Complexity of Ideal Semantics I: Abstract Argumentation Frameworks
    Dunne, Paul E.
    COMPUTATIONAL MODELS OF ARGUMENT, PROCEEDINGS OF COMMA 2008, 2008, 172 : 147 - 158
  • [9] Novel Algorithms for Abstract Dialectical Frameworks based on Complexity Analysis of Subclasses and SAT Solving
    Linsbichler, Thomas
    Maratea, Marco
    Niskanen, Andreas
    Wallner, Johannes P.
    Woltran, Stefan
    PROCEEDINGS OF THE TWENTY-SEVENTH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, 2018, : 1905 - 1911
  • [10] Advanced algorithms for abstract dialectical frameworks based on complexity analysis of subclasses and SAT solving
    Linsbichler, Thomas
    Maratea, Marco
    Niskanen, Andreas
    Wallner, Johannes P.
    Woltran, Stefan
    ARTIFICIAL INTELLIGENCE, 2022, 307
12