Complexity of Verification in Incomplete Argumentation Frameworks

Authors

  • Dorothea Baumeister Heinrich-Heine-Universität Düsseldorf
  • Daniel Neugebauer Heinrich-Heine-Universität Düsseldorf
  • Jörg Rothe Heinrich-Heine-Universität Düsseldorf
  • Hilmar Schadrack Heinrich-Heine-Universität Düsseldorf

Keywords:

abstract argumentation, argumentation framework, incomplete knowledge, verification, computational complexity

Abstract

Abstract argumentation frameworks are a well-established formalism to model nonmonotonic reasoning processes. However, the standard model cannot express incomplete or conflicting knowledge about the state of a given argumentation. Previously, argumentation frameworks were extended to allow uncertainty regarding the set of attacks or the set of arguments. We combine both models into a model of general incompleteness, complement previous results on the complexity of the verification problem in incomplete argumentation frameworks, and provide a full complexity map covering all three models and all classical semantics. Our main result shows that the complexity of verifying the preferred semantics rises from coNP- to Sigma^p_2-completeness when allowing uncertainty about either attacks or arguments, or both.

Downloads

Published

2018-04-25

How to Cite

Baumeister, D., Neugebauer, D., Rothe, J., & Schadrack, H. (2018). Complexity of Verification in Incomplete Argumentation Frameworks. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/11562

Issue

Section

AAAI Technical Track: Knowledge Representation and Reasoning