Quantitative Reasoning and Structural Complexity for Claim-Centric Argumentation

Quantitative Reasoning and Structural Complexity for Claim-Centric Argumentation

Johannes K. Fichte, Markus Hecher, Yasir Mahmood, Arne Meier

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence
Main Track. Pages 3212-3220. https://doi.org/10.24963/ijcai.2023/358

Argumentation is a well-established formalism for nonmonotonic reasoning and a vibrant area of research in AI. Claim-augmented argumentation frameworks (CAFs) have been introduced to deploy a conclusion-oriented perspective. CAFs expand argumentation frameworks by an additional step which involves retaining claims for an accepted set of arguments. We introduce a novel concept of a justification status for claims, a quantitative measure of extensions supporting a particular claim. The well-studied problems of credulous and skeptical reasoning can then be seen as simply the two endpoints of the spectrum when considered as a justification level of a claim. Furthermore, we explore the parameterized complexity of various reasoning problems for CAFs, including the quantitative reasoning for claim assertions. We begin by presenting a suitable graph representation that includes arguments and their associated claims. Our analysis includes the parameter treewidth, and we present decomposition-guided reductions between reasoning problems in CAF and the validity problem for QBF.
Keywords:
Knowledge Representation and Reasoning: KRR: Argumentation
Knowledge Representation and Reasoning: KRR: Computational complexity of reasoning