An SCC Recursive Meta-Algorithm for Computing Preferred Labellings in Abstract Argumentation

Federico Cerutti, Massimiliano Giacomin, Mauro Vallati, Marina Zanella

Research output: Chapter in Book/Report/Conference proceedingConference contribution

25 Citations (Scopus)

Abstract

This paper presents a meta-algorithm for the computation of preferred labellings, based on the general recursive schema for argumentation semantics called SCC-Recursiveness. The idea is to recursively decompose a framework so as to compute semantics labellings on restricted sub-frameworks, in order to reduce the computational effort. The meta-algorithm can be instantiated with a specific "base algorithm", applied to the base case of the recursion, which can be obtained by generalizing existing algorithms in order to compute labellings in restricted sub-frameworks. We devise for this purpose a generalization of a SAT-based algorithm, and provide an empirical investigation to show the significant improvement of performances obtained by exploiting the SCCrecursive schema.

Original languageEnglish
Title of host publication14th International Conference on the Principles of Knowledge Representation and Reasoning, KR 2014
PublisherAAAI press
Pages42-51
Number of pages10
ISBN (Electronic)9781577356578
Publication statusPublished - 4 May 2014
Event14th International Conference on the Principles of Knowledge Representation and Reasoning - Vienna, Austria
Duration: 20 Jul 201424 Jul 2014
Conference number: 14
http://www.dbai.tuwien.ac.at/kr2014/ (Link to Conference Website)

Conference

Conference14th International Conference on the Principles of Knowledge Representation and Reasoning
Abbreviated titleKR 2014
CountryAustria
CityVienna
Period20/07/1424/07/14
Internet address

Fingerprint

Argumentation
Computing
Schema
Semantics
Recursion
Decompose
Framework

Cite this

Cerutti, F., Giacomin, M., Vallati, M., & Zanella, M. (2014). An SCC Recursive Meta-Algorithm for Computing Preferred Labellings in Abstract Argumentation. In 14th International Conference on the Principles of Knowledge Representation and Reasoning, KR 2014 (pp. 42-51). AAAI press.
Cerutti, Federico ; Giacomin, Massimiliano ; Vallati, Mauro ; Zanella, Marina. / An SCC Recursive Meta-Algorithm for Computing Preferred Labellings in Abstract Argumentation. 14th International Conference on the Principles of Knowledge Representation and Reasoning, KR 2014. AAAI press, 2014. pp. 42-51
@inproceedings{acd0d27321194af38cef6a6efc387640,
title = "An SCC Recursive Meta-Algorithm for Computing Preferred Labellings in Abstract Argumentation",
abstract = "This paper presents a meta-algorithm for the computation of preferred labellings, based on the general recursive schema for argumentation semantics called SCC-Recursiveness. The idea is to recursively decompose a framework so as to compute semantics labellings on restricted sub-frameworks, in order to reduce the computational effort. The meta-algorithm can be instantiated with a specific {"}base algorithm{"}, applied to the base case of the recursion, which can be obtained by generalizing existing algorithms in order to compute labellings in restricted sub-frameworks. We devise for this purpose a generalization of a SAT-based algorithm, and provide an empirical investigation to show the significant improvement of performances obtained by exploiting the SCCrecursive schema.",
author = "Federico Cerutti and Massimiliano Giacomin and Mauro Vallati and Marina Zanella",
year = "2014",
month = "5",
day = "4",
language = "English",
pages = "42--51",
booktitle = "14th International Conference on the Principles of Knowledge Representation and Reasoning, KR 2014",
publisher = "AAAI press",

}

Cerutti, F, Giacomin, M, Vallati, M & Zanella, M 2014, An SCC Recursive Meta-Algorithm for Computing Preferred Labellings in Abstract Argumentation. in 14th International Conference on the Principles of Knowledge Representation and Reasoning, KR 2014. AAAI press, pp. 42-51, 14th International Conference on the Principles of Knowledge Representation and Reasoning, Vienna, Austria, 20/07/14.

An SCC Recursive Meta-Algorithm for Computing Preferred Labellings in Abstract Argumentation. / Cerutti, Federico; Giacomin, Massimiliano; Vallati, Mauro; Zanella, Marina.

14th International Conference on the Principles of Knowledge Representation and Reasoning, KR 2014. AAAI press, 2014. p. 42-51.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - An SCC Recursive Meta-Algorithm for Computing Preferred Labellings in Abstract Argumentation

AU - Cerutti, Federico

AU - Giacomin, Massimiliano

AU - Vallati, Mauro

AU - Zanella, Marina

PY - 2014/5/4

Y1 - 2014/5/4

N2 - This paper presents a meta-algorithm for the computation of preferred labellings, based on the general recursive schema for argumentation semantics called SCC-Recursiveness. The idea is to recursively decompose a framework so as to compute semantics labellings on restricted sub-frameworks, in order to reduce the computational effort. The meta-algorithm can be instantiated with a specific "base algorithm", applied to the base case of the recursion, which can be obtained by generalizing existing algorithms in order to compute labellings in restricted sub-frameworks. We devise for this purpose a generalization of a SAT-based algorithm, and provide an empirical investigation to show the significant improvement of performances obtained by exploiting the SCCrecursive schema.

AB - This paper presents a meta-algorithm for the computation of preferred labellings, based on the general recursive schema for argumentation semantics called SCC-Recursiveness. The idea is to recursively decompose a framework so as to compute semantics labellings on restricted sub-frameworks, in order to reduce the computational effort. The meta-algorithm can be instantiated with a specific "base algorithm", applied to the base case of the recursion, which can be obtained by generalizing existing algorithms in order to compute labellings in restricted sub-frameworks. We devise for this purpose a generalization of a SAT-based algorithm, and provide an empirical investigation to show the significant improvement of performances obtained by exploiting the SCCrecursive schema.

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

M3 - Conference contribution

SP - 42

EP - 51

BT - 14th International Conference on the Principles of Knowledge Representation and Reasoning, KR 2014

PB - AAAI press

ER -

Cerutti F, Giacomin M, Vallati M, Zanella M. An SCC Recursive Meta-Algorithm for Computing Preferred Labellings in Abstract Argumentation. In 14th International Conference on the Principles of Knowledge Representation and Reasoning, KR 2014. AAAI press. 2014. p. 42-51