Argumentation Extensions Enumeration as a Constraint Satisfaction Problem

A Performance Overview

Mauro Vallati, Federico Cerutti, Massimiliano Giacomin

Research output: Contribution to journalConference article

1 Citation (Scopus)

Abstract

Enumerating semantics extensions in abstract argumentation is generally an intractable problem. For preferred semantics four implementations have been recently proposed, CONArg2, AspartixM, PrefSAT and NAD-Alg, with significant runtime variations. This work is a first empirical evaluation of the performance of these implementations with the hypothesis that NAD-Alg, as representative of a family of ad-hoc approaches, will overcome in sequence PrefSAT-a SAT-based approach-, CONArg2-a CSP-based approach-, and the ASP-based approach AspartixM. The results shows that this is not always the case, as PrefSAT has been often the best approach both in terms of numbers of enumeration problems solved, and CPU-time. Moreover, we identify situations where AspartixM has been proved to be significantly faster than CONArg2.

Original languageEnglish
Number of pages13
JournalCEUR Workshop Proceedings
Volume1212
Publication statusPublished - 18 Aug 2014
EventInternational Workshop on Defeasible and Ampliative Reasoning - Prague, Czech Republic
Duration: 19 Aug 201419 Aug 2014
http://www.wikicfp.com/cfp/servlet/event.showcfp?eventid=36617&copyownerid=19937 (Link to Workshop Information)

Fingerprint

Constraint satisfaction problems
Semantics
Program processors

Cite this

@article{4a29090491604aed98f1ec53e52b1281,
title = "Argumentation Extensions Enumeration as a Constraint Satisfaction Problem: A Performance Overview",
abstract = "Enumerating semantics extensions in abstract argumentation is generally an intractable problem. For preferred semantics four implementations have been recently proposed, CONArg2, AspartixM, PrefSAT and NAD-Alg, with significant runtime variations. This work is a first empirical evaluation of the performance of these implementations with the hypothesis that NAD-Alg, as representative of a family of ad-hoc approaches, will overcome in sequence PrefSAT-a SAT-based approach-, CONArg2-a CSP-based approach-, and the ASP-based approach AspartixM. The results shows that this is not always the case, as PrefSAT has been often the best approach both in terms of numbers of enumeration problems solved, and CPU-time. Moreover, we identify situations where AspartixM has been proved to be significantly faster than CONArg2.",
keywords = "Argumentation, Empirical evaluation, Preferred semantics",
author = "Mauro Vallati and Federico Cerutti and Massimiliano Giacomin",
year = "2014",
month = "8",
day = "18",
language = "English",
volume = "1212",
journal = "CEUR Workshop Proceedings",
issn = "1613-0073",
publisher = "CEUR Workshop Proceedings",

}

Argumentation Extensions Enumeration as a Constraint Satisfaction Problem : A Performance Overview. / Vallati, Mauro; Cerutti, Federico; Giacomin, Massimiliano.

In: CEUR Workshop Proceedings, Vol. 1212, 18.08.2014.

Research output: Contribution to journalConference article

TY - JOUR

T1 - Argumentation Extensions Enumeration as a Constraint Satisfaction Problem

T2 - A Performance Overview

AU - Vallati, Mauro

AU - Cerutti, Federico

AU - Giacomin, Massimiliano

PY - 2014/8/18

Y1 - 2014/8/18

N2 - Enumerating semantics extensions in abstract argumentation is generally an intractable problem. For preferred semantics four implementations have been recently proposed, CONArg2, AspartixM, PrefSAT and NAD-Alg, with significant runtime variations. This work is a first empirical evaluation of the performance of these implementations with the hypothesis that NAD-Alg, as representative of a family of ad-hoc approaches, will overcome in sequence PrefSAT-a SAT-based approach-, CONArg2-a CSP-based approach-, and the ASP-based approach AspartixM. The results shows that this is not always the case, as PrefSAT has been often the best approach both in terms of numbers of enumeration problems solved, and CPU-time. Moreover, we identify situations where AspartixM has been proved to be significantly faster than CONArg2.

AB - Enumerating semantics extensions in abstract argumentation is generally an intractable problem. For preferred semantics four implementations have been recently proposed, CONArg2, AspartixM, PrefSAT and NAD-Alg, with significant runtime variations. This work is a first empirical evaluation of the performance of these implementations with the hypothesis that NAD-Alg, as representative of a family of ad-hoc approaches, will overcome in sequence PrefSAT-a SAT-based approach-, CONArg2-a CSP-based approach-, and the ASP-based approach AspartixM. The results shows that this is not always the case, as PrefSAT has been often the best approach both in terms of numbers of enumeration problems solved, and CPU-time. Moreover, we identify situations where AspartixM has been proved to be significantly faster than CONArg2.

KW - Argumentation

KW - Empirical evaluation

KW - Preferred semantics

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

M3 - Conference article

VL - 1212

JO - CEUR Workshop Proceedings

JF - CEUR Workshop Proceedings

SN - 1613-0073

ER -