Talks and Poster Presentations (with Proceedings-Entry):
W. Dvorak, M. Ulbricht, S. Woltran:
"Weak Admissibility is PSPACE-complete";
Talk: NMR 2020 - 18th INTERNATIONAL WORKSHOP ON NON-MONOTONIC REASONING,
Rhodes, Greece;
2020-09-12
- 2020-09-18; in: "18th INTERNATIONAL WORKSHOP ON NON-MONOTONIC REASONING",
(2020),
100
- 109.
English abstract:
We study the complexity of decision problems for weak ad-missibility, a recently introduced concept in abstract argu-mentation to deal with arguments of self-defeating nature.Our results reveal that semantics based on weak admissibilityare of much higher complexity (under typical assumptions)compared to all argumentation semantics which have beenanalysed in terms of complexity so far. In fact, we showPSPACE-completeness of all standard decision problems forw-admissible and w-preferred semantics (with the exceptionof skeptical w-admissible acceptance which is trivial). As astrategy for implementation we also provide a polynomial-time reduction to DATALOG with stratified negation.
Created from the Publication Database of the Vienna University of Technology.