Recursion in Abstract Argumentation is Hard --- On the Complexity of Semantics Based on Weak Admissibility

Authors

  • Wolfgang Dvořák TU Wien
  • Markus Ulbricht University of Leipzig
  • Stefan Woltran TU Wien

Keywords:

Argumentation

Abstract

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.

Downloads

Published

2021-05-18

How to Cite

Dvořák, W., Ulbricht, M., & Woltran, S. (2021). Recursion in Abstract Argumentation is Hard --- On the Complexity of Semantics Based on Weak Admissibility. Proceedings of the AAAI Conference on Artificial Intelligence, 35(7), 6288-6295. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/16781

Issue

Section

AAAI Technical Track on Knowledge Representation and Reasoning