Advanced Algorithms for Abstract Dialectical Frameworks based on Complexity Analysis of Subclasses and SAT Solving

Thomas Linsbichler, Marco Maratea, Andreas Niskanen, Johannes P. Wallner, Stefan Woltran

Forskningsoutput: TidskriftsbidragArtikelVetenskapligPeer review

Sammanfattning

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. (c) 2022 The Author(s). Published by Elsevier B.V.
Originalspråkengelska
Artikelnummer103697
TidskriftArtificial Intelligence
Volym307
Antal sidor40
ISSN0004-3702
DOI
StatusPublicerad - juni 2022
MoE-publikationstypA1 Tidskriftsartikel-refererad

Vetenskapsgrenar

  • 113 Data- och informationsvetenskap

Citera det här