| Identifikační kód | RIV/00216224:14330/12:00063350 |
|---|
| Název v anglickém jazyce | Augmenting tractable fragments of abstract argumentation |
|---|
| Druh | J - Článek v odborném periodiku |
|---|
| Jazyk | eng - angličtina |
|---|
| Obor - skupina | I - Informatika |
|---|
| Obor | IN - Informatika |
|---|
| Rok uplatnění | 2012 |
|---|
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
|---|
| Počet výskytů výsledku | 1 |
|---|
| Počet tvůrců celkem | 3 |
|---|
| Počet domácích tvůrců | 1 |
|---|
| Výčet všech uvedených jednotlivých tvůrců | Wolfgang Dvorak (státní příslušnost: AT - Rakouská republika)
Sebastian Ordyniak (státní příslušnost: DE - Spolková republika Německo, domácí tvůrce: A)
Stefan Szeider (státní příslušnost: AT - Rakouská republika) |
|---|
| Popis výsledku v anglickém jazyce | We present a new approach to the efficient solution of important computational problems that arise in the context of abstract argumentation. Our approach makes known algorithms defined for restricted fragments generally applicable, at a computational cost that scales with the distance from the fragment. Thus, in a certain sense, we gradually augment tractable fragments. Surprisingly, it turns out that some tractable fragments admit such an augmentation and that others do not. More specifically, we showthat the problems of Credulous and Skeptical Acceptance are fixed-parameter tractable when parameterized by the distance from the fragment of acyclic argumentation frameworks-for most semantics. Other tractable fragments such as the fragments of symmetrical and bipartite frameworks seem to prohibit an augmentation: the acceptance problems are already intractable for frameworks at distance 1 from the fragments. For our study we use a broad setting and consider several different semantics. |
|---|
| Klíčová slova oddělená středníkem | Abstract argumentation; Backdoors; Computational complexity; Parameterized complexity; Fixed-parameter tractability |
|---|
| Stránka www, na které se nachází výsledek | - |
|---|
| DOI výsledku | 10.1016/j.artint.2012.03.002 |
|---|