An Efficient Algorithm for Semi-stable Extensions

Federico Cerutti; Massimiliano Giacomin; Mauro Vallati; Tobia Zanetti

doi:10.1007/978-3-030-77091-4_8

An Efficient Algorithm for Semi-stable Extensions

Federico Cerutti, Massimiliano Giacomin, Mauro Vallati, Tobia Zanetti

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

In this paper we introduce AASExts, an algorithm for computing semi–stable extensions. We improve techniques developed for other semantics, notably preferred semantics, as well as leverage recent advances in All-SAT community. We prove our proposed algorithm is sound and complete, we describe the experiments to select the most appropriate encoding to adopt, and we show empirically that our implementation significantly outperforms even sophisticated ASP-based and SAT-based reduction approaches on existing benchmarks.

Original language	English
Title of host publication	AIxIA 2020 – Advances in Artificial Intelligence
Subtitle of host publication	XIXth International Conference of the Italian Association for Artificial Intelligence, Revised Selected Papers
Editors	Matteo Baldoni, Stefania Bandini
Place of Publication	Cham
Publisher	Springer Nature Switzerland AG
Pages	117-135
Number of pages	19
Volume	LNCS/LNAI 12414
Edition	1st
ISBN (Electronic)	9783030770914
ISBN (Print)	9783030770907
DOIs	https://doi.org/10.1007/978-3-030-77091-4_8
Publication status	Published - 22 May 2021
Event	19th International Conference of the Italian Association for Artiﬁcial Intelligence - Virtual, Online Duration: 24 Nov 2020 → 27 Nov 2020 Conference number: 19

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publisher	Springer Nature Switzerland AG
Volume	12414 LNAI/LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	19th International Conference of the Italian Association for Artiﬁcial Intelligence
Abbreviated title	AIxIA 2020
City	Virtual, Online
Period	24/11/20 → 27/11/20

Access to Document

10.1007/978-3-030-77091-4_8Licence: Unspecified

Cite this

Cerutti, F., Giacomin, M., Vallati, M., & Zanetti, T. (2021). An Efficient Algorithm for Semi-stable Extensions. In M. Baldoni, & S. Bandini (Eds.), AIxIA 2020 – Advances in Artificial Intelligence: XIXth International Conference of the Italian Association for Artificial Intelligence, Revised Selected Papers (1st ed., Vol. LNCS/LNAI 12414, pp. 117-135). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12414 LNAI/LNCS). Springer Nature Switzerland AG. https://doi.org/10.1007/978-3-030-77091-4_8

Cerutti, Federico ; Giacomin, Massimiliano ; Vallati, Mauro et al. / An Efficient Algorithm for Semi-stable Extensions. AIxIA 2020 – Advances in Artificial Intelligence: XIXth International Conference of the Italian Association for Artificial Intelligence, Revised Selected Papers. editor / Matteo Baldoni ; Stefania Bandini. Vol. LNCS/LNAI 12414 1st. ed. Cham : Springer Nature Switzerland AG, 2021. pp. 117-135 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{15543884327044809605acde0fec27cd,

title = "An Efficient Algorithm for Semi-stable Extensions",

abstract = "In this paper we introduce AASExts, an algorithm for computing semi–stable extensions. We improve techniques developed for other semantics, notably preferred semantics, as well as leverage recent advances in All-SAT community. We prove our proposed algorithm is sound and complete, we describe the experiments to select the most appropriate encoding to adopt, and we show empirically that our implementation significantly outperforms even sophisticated ASP-based and SAT-based reduction approaches on existing benchmarks.",

keywords = "Abstract argumentation, Algorithm, Semi-stable semantics",

author = "Federico Cerutti and Massimiliano Giacomin and Mauro Vallati and Tobia Zanetti",

note = "Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG. Copyright: Copyright 2021 Elsevier B.V., All rights reserved.; 19th International Conference of the Italian Association for Artiﬁcial Intelligence, AIxIA 2020 ; Conference date: 24-11-2020 Through 27-11-2020",

year = "2021",

month = may,

day = "22",

doi = "10.1007/978-3-030-77091-4_8",

language = "English",

isbn = "9783030770907",

volume = "LNCS/LNAI 12414",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Nature Switzerland AG",

pages = "117--135",

editor = "Matteo Baldoni and Stefania Bandini",

booktitle = "AIxIA 2020 – Advances in Artificial Intelligence",

address = "Switzerland",

edition = "1st",

}

Cerutti, F, Giacomin, M, Vallati, M & Zanetti, T 2021, An Efficient Algorithm for Semi-stable Extensions. in M Baldoni & S Bandini (eds), AIxIA 2020 – Advances in Artificial Intelligence: XIXth International Conference of the Italian Association for Artificial Intelligence, Revised Selected Papers. 1st edn, vol. LNCS/LNAI 12414, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12414 LNAI/LNCS, Springer Nature Switzerland AG, Cham, pp. 117-135, 19th International Conference of the Italian Association for Artiﬁcial Intelligence, Virtual, Online, 24/11/20. https://doi.org/10.1007/978-3-030-77091-4_8

An Efficient Algorithm for Semi-stable Extensions. / Cerutti, Federico; Giacomin, Massimiliano; Vallati, Mauro et al.

AIxIA 2020 – Advances in Artificial Intelligence: XIXth International Conference of the Italian Association for Artificial Intelligence, Revised Selected Papers. ed. / Matteo Baldoni; Stefania Bandini. Vol. LNCS/LNAI 12414 1st. ed. Cham : Springer Nature Switzerland AG, 2021. p. 117-135 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12414 LNAI/LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - An Efficient Algorithm for Semi-stable Extensions

AU - Cerutti, Federico

AU - Giacomin, Massimiliano

AU - Vallati, Mauro

AU - Zanetti, Tobia

N1 - Conference code: 19

PY - 2021/5/22

Y1 - 2021/5/22

N2 - In this paper we introduce AASExts, an algorithm for computing semi–stable extensions. We improve techniques developed for other semantics, notably preferred semantics, as well as leverage recent advances in All-SAT community. We prove our proposed algorithm is sound and complete, we describe the experiments to select the most appropriate encoding to adopt, and we show empirically that our implementation significantly outperforms even sophisticated ASP-based and SAT-based reduction approaches on existing benchmarks.

AB - In this paper we introduce AASExts, an algorithm for computing semi–stable extensions. We improve techniques developed for other semantics, notably preferred semantics, as well as leverage recent advances in All-SAT community. We prove our proposed algorithm is sound and complete, we describe the experiments to select the most appropriate encoding to adopt, and we show empirically that our implementation significantly outperforms even sophisticated ASP-based and SAT-based reduction approaches on existing benchmarks.

KW - Abstract argumentation

KW - Algorithm

KW - Semi-stable semantics

UR - http://www.scopus.com/inward/record.url?scp=85111347687&partnerID=8YFLogxK

UR - https://link.springer.com/book/10.1007/978-3-030-77091-4

U2 - 10.1007/978-3-030-77091-4_8

DO - 10.1007/978-3-030-77091-4_8

M3 - Conference contribution

AN - SCOPUS:85111347687

SN - 9783030770907

VL - LNCS/LNAI 12414

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 117

EP - 135

BT - AIxIA 2020 – Advances in Artificial Intelligence

A2 - Baldoni, Matteo

A2 - Bandini, Stefania

PB - Springer Nature Switzerland AG

CY - Cham

T2 - 19th International Conference of the Italian Association for Artiﬁcial Intelligence

Y2 - 24 November 2020 through 27 November 2020

ER -

Cerutti F, Giacomin M, Vallati M, Zanetti T. An Efficient Algorithm for Semi-stable Extensions. In Baldoni M, Bandini S, editors, AIxIA 2020 – Advances in Artificial Intelligence: XIXth International Conference of the Italian Association for Artificial Intelligence, Revised Selected Papers. 1st ed. Vol. LNCS/LNAI 12414. Cham: Springer Nature Switzerland AG. 2021. p. 117-135. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). Epub 2021 May 22. doi: 10.1007/978-3-030-77091-4_8

An Efficient Algorithm for Semi-stable Extensions

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this