Argumentation frameworks induced by assumption-based argumentation: Relating size and complexity
T. Lehtonen, A. Rapberger, M. Ulbricht, and J. Wallner. Proceedings of the Twentieth International Conference on Principles of Knowledge Representation and Reasoning, page 440--450. California, International Joint Conferences on Artificial Intelligence Organization, (September 2023)
Abstract
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.
%0 Conference Paper
%1 Lehtonen2023-eq
%A Lehtonen, Tuomo
%A Rapberger, Anna
%A Ulbricht, Markus
%A Wallner, Johannes P
%B Proceedings of the Twentieth International Conference on Principles of Knowledge Representation and Reasoning
%C California
%D 2023
%I International Joint Conferences on Artificial Intelligence Organization
%K topic_knowledge topic_lifescience
%P 440--450
%T Argumentation frameworks induced by assumption-based argumentation: Relating size and complexity
%X 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.
@inproceedings{Lehtonen2023-eq,
abstract = {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.},
added-at = {2024-09-10T10:41:24.000+0200},
address = {California},
author = {Lehtonen, Tuomo and Rapberger, Anna and Ulbricht, Markus and Wallner, Johannes P},
biburl = {https://puma.scadsai.uni-leipzig.de/bibtex/24b41bb0dbb83fe10245c843e46b64746/scadsfct},
booktitle = {Proceedings of the Twentieth International Conference on Principles of Knowledge Representation and Reasoning},
conference = {20th International Conference on Principles of Knowledge Representation and Reasoning \{KR-2023\}},
interhash = {a8b4748fbb042fd6a40a8af35d96a1b7},
intrahash = {4b41bb0dbb83fe10245c843e46b64746},
keywords = {topic_knowledge topic_lifescience},
location = {Rhodes, Greece},
month = sep,
pages = {440--450},
publisher = {International Joint Conferences on Artificial Intelligence Organization},
timestamp = {2024-11-22T15:46:07.000+0100},
title = {Argumentation frameworks induced by assumption-based argumentation: Relating size and complexity},
year = 2023
}
