KR2023Proceedings of the 20th International Conference on Principles of Knowledge Representation and ReasoningProceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning

Rhodes, Greece. September 2-8, 2023.

Edited by

ISSN: 2334-1033
ISBN: 978-1-956792-02-7

Sponsored by
Published by

Copyright © 2023 International Joint Conferences on Artificial Intelligence Organization

Argumentation Frameworks Induced by Assumption-based Argumentation: Relating Size and Complexity

  1. Tuomo Lehtonen(University of Helsinki)
  2. Anna Rapberger(TU Wien)
  3. Markus Ulbricht(University of Leipzig)
  4. Johannes P. Wallner(TU Graz)


  1. Argumentation
  2. Computational aspects of knowledge representation


A key ingredient of computational argumentation in AI is the generation of arguments in favor of or against claims under scrutiny. In this paper we look at the complexity of argument construction and reasoning in the prominent structured formalism of assumption-based argumentation (ABA). We point out that reasoning in ABA by means of constructing an abstract argumentation framework (AF) gives rise to two main sources of complexity: (i) constructing the AF and (ii) reasoning within the constructed graph. Since both steps are intractable in general, it is no surprise that the best performing state-of-the-art ABA reasoners skip the instantiation procedure entirely and perform tasks directly on the input knowledge base. Driven by this observation, we identify and study atomic and symmetric ABA, two ABA fragments that preserve the expressive power of general ABA, and that can be utilized to have milder complexity in the first or second step. We show that using atomic ABA allows for an instantiation procedure for general ABA leading to polynomially-bounded AFs and that symmetric ABA can be used to create AFs that have mild complexity to reason on. By an experimental evaluation, we show that using the former approach with modern AF solvers can be competitive with state-of-the-art ABA solvers, improving on previous AF instantiation approaches that are hindered by intractable argument construction.