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

doi:10.1016/j.artint.2022.103697

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

Tietojenkäsittelytieteen osasto

Tutkimustuotos: Artikkelijulkaisu › Artikkeli › Tieteellinen › vertaisarvioitu

Abstrakti

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.

Alkuperäiskieli	englanti
Artikkeli	103697
Lehti	Artificial Intelligence
Vuosikerta	307
Sivumäärä	40
ISSN	0004-3702
DOI - pysyväislinkit	https://doi.org/10.1016/j.artint.2022.103697
Tila	Julkaistu - kesäk. 2022
OKM-julkaisutyyppi	A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä, vertaisarvioitu

Tieteenalat

113 Tietojenkäsittely- ja informaatiotieteet

Pääsy asiakirjaan

10.1016/j.artint.2022.103697Lisenssi: CC BY

1-s2.0-S0004370222000376-mainLopullinen julkaistu versio, 1,08 MBLisenssi: CC BY

1 Päättynyt

Symbolic Techniques for Formally Verified and Explainable AI
Järvisalo, M. (Principal Investigator)
01/01/2020 → 31/12/2022
Projekti: Tutkimusprojekti

Siteeraa tätä

@article{2b9a179910294586952376c6d6e4344a,

title = "Advanced Algorithms for Abstract Dialectical Frameworks based on Complexity Analysis of Subclasses and SAT Solving",

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. (c) 2022 The Author(s). Published by Elsevier B.V.",

keywords = "113 Computer and information sciences, Abstract dialectical frameworks, SAT-based procedures, Complexity analysis, ARGUMENTATION",

author = "Thomas Linsbichler and Marco Maratea and Andreas Niskanen and Wallner, {Johannes P.} and Stefan Woltran",

year = "2022",

month = jun,

doi = "10.1016/j.artint.2022.103697",

language = "English",

volume = "307",

journal = "Artificial Intelligence",

issn = "0004-3702",

publisher = "Elsevier B.V.",

}

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 P.

AU - Woltran, Stefan

PY - 2022/6

Y1 - 2022/6

N2 - 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.

AB - 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.

KW - 113 Computer and information sciences

KW - Abstract dialectical frameworks

KW - SAT-based procedures

KW - Complexity analysis

KW - ARGUMENTATION

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 -

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

Abstrakti

Tieteenalat

Pääsy asiakirjaan

Projektit

Symbolic Techniques for Formally Verified and Explainable AI

Siteeraa tätä