KR2024Proceedings of the 21st International Conference on Principles of Knowledge Representation and ReasoningProceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning

Hanoi, Vietnam. November 2-8, 2024.

Edited by

ISSN: 2334-1033
ISBN: 978-1-956792-05-8

Sponsored by
Published by

Copyright © 2024 International Joint Conferences on Artificial Intelligence Organization

Complexity Results and Algorithms for Preferential Argumentative Reasoning in ASPIC+

  1. Tuomo Lehtonen(Department of Computer Science, Aalto University, Finland)
  2. Daphne Odekerken(Department of Information and Computing Sciences, Utrecht University, The Netherlands, National Police Lab AI, Netherlands Police, The Netherlands)
  3. Johannes P. Wallner(Institute of Software Technology, TU Graz, Austria)
  4. Matti Järvisalo(Department of Computer Science, University of Helsinki, Finland)

Keywords

  1. Argumentation-General
  2. Computational aspects of knowledge representation-General
  3. Modeling and reasoning about preferences-General
  4. Logic programming, answer set programming-General

Abstract

We provide complexity results and algorithms for reasoning in the central structured argumentation formalism of ASPIC+. Considering ASPIC+ accommodated with preferences under the last-link principle, the results are made possible by rephrasing several argumentation semantics---admissible, complete, stable, preferred and grounded---in terms of defeasible elements of an ASPIC+ theory for both democratic and elitist last-link lifting. Via the rephrasing, we establish that acceptance is polynomial-time computable under grounded semantics, and complete for either NP, coNP, or Pi_P^2, depending on the reasoning mode and semantics. We also detail answer set programming encodings for deciding acceptance for the NP/coNP-complete reasoning tasks, and empirically show that it scales significantly better than first translating ASPIC+ reasoning tasks to abstract argumentation. Finally, we show that, in contrast to the last-link principle, it is NP-hard to compute the grounded extension under the weakest-link principle.