Instantiations and Computational Aspects of Non-Flat Assumption-based Argumentation

Instantiations and Computational Aspects of Non-Flat Assumption-based Argumentation

Tuomo Lehtonen, Anna Rapberger, Francesca Toni, Markus Ulbricht, Johannes P. Wallner

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence
Main Track. Pages 3457-3465. https://doi.org/10.24963/ijcai.2024/383

Most existing computational tools for assumption-based argumentation (ABA) focus on so-called flat frameworks, disregarding the more general case. In this paper, we study an instantiation-based approach for reasoning in possibly non-flat ABA. We make use of a semantics-preserving translation between ABA and bipolar argumentation frameworks (BAFs). By utilizing compilability theory, we establish that the constructed BAFs will in general be of exponential size. To keep the number of arguments and computational cost low, we present three ways of identifying redundant arguments. Moreover, we identify fragments of ABA which admit a poly-sized instantiation. We propose two algorithmic approaches for reasoning in non-flat ABA; the first utilizes the BAF instantiation while the second works directly without constructing arguments. An empirical evaluation shows that the former outperforms the latter on many instances, reflecting the lower complexity of BAF reasoning. This result is in contrast to flat ABA, where direct approaches dominate instantiation-based solvers.
Keywords:
Knowledge Representation and Reasoning: KRR: Argumentation
Knowledge Representation and Reasoning: KRR: Computational complexity of reasoning