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.
Argumentation extensions enumeration as a constraint satisfaction problem: A performance overview
Cerutti, Federico;GIACOMIN, Massimiliano
2014-01-01
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.