TY - JOUR
T1 - Advanced Algorithms for Abstract Dialectical Frameworks based on Complexity Analysis of Subclasses and SAT Solving
AU - Linsbichler, Thomas
AU - Maratea, Marco
AU - Niskanen, Andreas
AU - Wallner, Johannes Peter
AU - Woltran, Stefan
PY - 2022/6
Y1 - 2022/6
N2 - Abstract dialectical frameworks (ADFs) constitute one of the most powerful formalisms in abstract argumentation. Their high computational complexity poses, however, certain challenges when designing efficient systems. In this paper, we tackle this issue by (i) analyzing the complexity of ADFs under structural restrictions, (ii) presenting novel algorithms which make use of these insights, and (iii) implementing these algorithms via (multiple) calls to SAT solvers. An empirical evaluation of the resulting implementation on ADF benchmarks generated from ICCMA competitions shows that our solver is able to outperform state-of-the-art ADF systems.
AB - Abstract dialectical frameworks (ADFs) constitute one of the most powerful formalisms in abstract argumentation. Their high computational complexity poses, however, certain challenges when designing efficient systems. In this paper, we tackle this issue by (i) analyzing the complexity of ADFs under structural restrictions, (ii) presenting novel algorithms which make use of these insights, and (iii) implementing these algorithms via (multiple) calls to SAT solvers. An empirical evaluation of the resulting implementation on ADF benchmarks generated from ICCMA competitions shows that our solver is able to outperform state-of-the-art ADF systems.
KW - Abstract dialectical frameworks
KW - Complexity analysis
KW - SAT-based procedures
UR - http://www.scopus.com/inward/record.url?scp=85126943738&partnerID=8YFLogxK
U2 - 10.1016/j.artint.2022.103697
DO - 10.1016/j.artint.2022.103697
M3 - Article
SN - 0004-3702
VL - 307
JO - Artificial Intelligence
JF - Artificial Intelligence
M1 - 103697
ER -