Publications in Scientific Journals:
W. Dvorak, S. Woltran:
"Complexity of semi-stable and stage semantics in argumentation frameworks";
Information Processing Letters,
Inf. Process. Lett. 110
(2010),
11;
425
- 430.
English abstract:
In this work, we answer two questions about the complexity of
semi-stable semantics for abstract argumentation frameworks: we show
PiP2-completeness for the problem of deciding whether an argument is
skeptically accepted, and respectively, SigmaP2-completeness for the
problem of deciding whether an argument is credulously accepted under
the semi-stable semantics. Furthermore, we extend these complexity
bounds to the according decision problems for stage semantics and
discuss two approaches towards tractability.
German abstract:
In this work, we answer two questions about the complexity of
semi-stable semantics for abstract argumentation frameworks: we show
PiP2-completeness for the problem of deciding whether an argument is
skeptically accepted, and respectively, SigmaP2-completeness for the
problem of deciding whether an argument is credulously accepted under
the semi-stable semantics. Furthermore, we extend these complexity
bounds to the according decision problems for stage semantics and
discuss two approaches towards tractability.
Keywords:
Computational complexity; Abstract argumentation
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1016/j.ipl.2010.04.005
Related Projects:
Project Head Stefan Woltran:
Neue Methoden für Analyse, Vergleich und Lösung von Argumentationsproblemen
Created from the Publication Database of the Vienna University of Technology.