Zeitschriftenartikel:
W. Dvorak, S. Woltran:
"Complexity of semi-stable and stage semantics in argumentation frameworks";
Information Processing Letters,
Inf. Process. Lett. 110
(2010),
11;
S. 425
- 430.
Kurzfassung deutsch:
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.
Kurzfassung englisch:
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.
Schlagworte:
Computational complexity; Abstract argumentation
"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.1016/j.ipl.2010.04.005
Zugeordnete Projekte:
Projektleitung Stefan Woltran:
Neue Methoden für Analyse, Vergleich und Lösung von Argumentationsproblemen
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.