[Zurück]


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.