[Back]

W. Dvorak, M. Ulbricht, S. Woltran:
"Recursion in Abstract Argumentation is Hard - On the Complexity of Semantics Based on Weak Admissibility";
Talk: 35th AAAI 2021, virtual event; 2021-02-02 - 2021-02-09; in: "Thirty-Fifth {AAAI} Conference on Artificial Intelligence, {AAAI} 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, {IAAI} 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, {EAAI} 2021", (2021), 6288 - 6295.

We study the computational complexity of abstract argumentation semantics based on weak admissibility, a recently introduced concept to deal with arguments of self-defeating nature. Our results reveal that semantics based on weak admissibility are of much higher complexity (under typical assumptions) compared to all argumentation semantics which have been analysed in terms of complexity so far. In fact, we show PSPACE-completeness of all non-trivial standard decision problems for weak-admissible based semantics. We then investigate potential tractable fragments and show that restricting the frameworks under consideration to certain graph-classes significantly reduces the complexity. As a strategy for implementation we also provide a polynomial-time reduction to DATALOG with stratified negation.

Argumentation

Project Head Stefan Woltran:
START