The Complexity of Repairing, Adjusting, and Aggregating of
Extensions in Abstract Argumentation

D 2014

The Complexity of Repairing, Adjusting, and Aggregating of Extensions in Abstract Argumentation

ORDYNIAK, Sebastian, Stefan SZEIDER a Kim EUN JUNG

Základní údaje

Originální název

The Complexity of Repairing, Adjusting, and Aggregating of Extensions in Abstract Argumentation

Autoři

ORDYNIAK, Sebastian (276 Německo, garant, domácí), Stefan SZEIDER (40 Rakousko) a Kim EUN JUNG (410 Korejská republika)

Vydání

Lecture Notes in Computer Science, Lecture Notes in Computer Science, od s. 158-175, 18 s. 2014

Nakladatel

Springer

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10000 1. Natural Sciences

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

tištěná verze "print"

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/14:00075259

Organizační jednotka

Fakulta informatiky

ISBN

978-3-642-54372-2

ISSN

DOI

http://dx.doi.org/10.1007/978-3-642-54373-9_11

Klíčová slova anglicky

abstract argumentation;dynamic argumentation;parameterized complexity

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 25. 4. 2014 14:08, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

We study the computational complexity of problems that arise in abstract argumentation in the context of dynamic argumentation, minimal change, and aggregation. In particular, we consider the following problems where always an argumentation framework F and a small positive integer k are given. The Repair problem asks whether a given set of arguments can be modified into an extension by at most k elementary changes (i.e., the extension is of distance k from the given set). The Adjust problem asks whether a given extension can be modified by at most k elementary changes into an extension that contains a specified argument. The Center problem asks whether, given two extensions of distance k, whether there is a ``center'' extension that is a distance at most (k-1) from both given extensions. We study these problems in the framework of parameterized complexity, and take the distance k as the parameter. Our results covers several different semantics, including admissible, complete, preferred, semi-stable and stable semantics.

Návaznosti

EE2.3.30.0009, projekt VaV

Název: Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci

Citovat

ORDYNIAK, Sebastian, Stefan SZEIDER a Kim EUN JUNG. The Complexity of Repairing, Adjusting, and Aggregating of Extensions in Abstract Argumentation. In Elizabeth Black, Sanjay Modgil, Nir Oren. Lecture Notes in Computer Science. Lecture Notes in Computer Science: Springer, 2014, s. 158-175. ISBN 978-3-642-54372-2. Dostupné z: https://dx.doi.org/10.1007/978-3-642-54373-9_11.

@inproceedings{1173824,
   author = {Ordyniak, Sebastian and Szeider, Stefan and Eun Jung, Kim},
   address = {Lecture Notes in Computer Science},
   booktitle = {Lecture Notes in Computer Science},
   doi = {http://dx.doi.org/10.1007/978-3-642-54373-9_11},
   editor = {Elizabeth Black, Sanjay Modgil, Nir Oren},
   keywords = {abstract argumentation;dynamic argumentation;parameterized complexity},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Lecture Notes in Computer Science},
   isbn = {978-3-642-54372-2},
   pages = {158-175},
   publisher = {Springer},
   title = {The Complexity of Repairing, Adjusting, and Aggregating of Extensions in Abstract Argumentation},
   year = {2014}
}

TY  - JOUR
ID  - 1173824
AU  - Ordyniak, Sebastian - Szeider, Stefan - Eun Jung, Kim
PY  - 2014
TI  - The Complexity of Repairing, Adjusting, and Aggregating of Extensions in Abstract Argumentation
PB  - Springer
CY  - Lecture Notes in Computer Science
SN  - 9783642543722
KW  - abstract argumentation;dynamic argumentation;parameterized complexity
N2  - We study the computational complexity of problems that arise in abstract argumentation in the context of dynamic argumentation, minimal change, and aggregation. In particular, we consider the following problems where always an argumentation framework F and a small positive integer k are given. The Repair problem asks whether a given set of arguments can be modified into an extension by at most k elementary changes (i.e., the extension is of distance k from the given set). The Adjust problem asks whether a given extension can be modified by at most k elementary changes into an extension that contains a specified argument. The Center problem asks whether, given two extensions of distance k, whether there is a ``center'' extension that is a distance at most (k-1) from both given extensions. We study these problems in the framework of parameterized complexity, and take the distance k as the parameter. Our results covers several different semantics, including admissible, complete, preferred, semi-stable and stable semantics.
ER  -

ORDYNIAK, Sebastian, Stefan SZEIDER a Kim EUN JUNG. The Complexity of Repairing, Adjusting, and Aggregating of Extensions in Abstract Argumentation. In Elizabeth Black, Sanjay Modgil, Nir Oren. \textit{Lecture Notes in Computer Science}. Lecture Notes in Computer Science: Springer, 2014, s.~158-175. ISBN~978-3-642-54372-2. Dostupné z: https://dx.doi.org/10.1007/978-3-642-54373-9\_{}11.

Podrobný výpis o publikaci