Deciding Acceptance in Incomplete Argumentation Frameworks

Authors

  • Andreas Niskanen University of Helsinki
  • Daniel Neugebauer Heinrich-Heine-Universität Düsseldorf
  • Matti Järvisalo University of Helsinki
  • Jörg Rothe Heinrich-Heine-Universität Düsseldorf

DOI:

https://doi.org/10.1609/aaai.v34i03.5686

Abstract

Expressing incomplete knowledge in abstract argumentation frameworks (AFs) through incomplete AFs has recently received noticeable attention. However, algorithmic aspects of deciding acceptance in incomplete AFs are still under-developed. We address this current shortcoming by developing algorithms for NP-hard and coNP-hard variants of acceptance problems over incomplete AFs via harnessing Boolean satisfiability (SAT) solvers. Focusing on nonempty conflict-free or admissible sets and on stable extensions, we also provide new complexity results for a refined variant of skeptical acceptance in incomplete AFs, ranging from polynomial-time computability to hardness for the second level of the polynomial hierarchy. Furthermore, central to the proposed SAT-based counterexample-guided abstraction refinement approach for the second-level problem variants, we establish conditions for redundant atomic changes to incomplete AFs from the perspective of preserving extensions. We show empirically that the resulting SAT-based approach for incomplete AFs scales at least as well as existing SAT-based approaches to deciding acceptance in AFs.

Downloads

Published

2020-04-03

How to Cite

Niskanen, A., Neugebauer, D., Järvisalo, M., & Rothe, J. (2020). Deciding Acceptance in Incomplete Argumentation Frameworks. Proceedings of the AAAI Conference on Artificial Intelligence, 34(03), 2942-2949. https://doi.org/10.1609/aaai.v34i03.5686

Issue

Section

AAAI Technical Track: Knowledge Representation and Reasoning