Incomplete Argumentation Frameworks: Properties and Complexity


  • Gianvincenzo Alfano University of Calabria, Italy
  • Sergio Greco University of Calabria, Italy
  • Francesco Parisi University of Calabria, Italy
  • Irina Trubitsyna University of Calabria, Italy



Knowledge Representation And Reasoning (KRR)


Dung’s Argumentation Framework (AF) has been extended in several directions, including the possibility of representing unquantified uncertainty about the existence of arguments and attacks. The framework resulting from such an extension is called incomplete AF (iAF). In this paper, we first introduce three new satisfaction problems named totality, determinism and functionality, and investigate their computational complexity for both AF and iAF under several semantics. We also investigate the complexity of credulous and skeptical acceptance in iAF under semi-stable semantics—a problem left open in the literature. We then show that any iAF can be rewritten into an equivalent one where either only (unattacked) arguments or only attacks are uncertain. Finally, we relate iAF to probabilistic argumentation framework, where uncertainty is quantified.




How to Cite

Alfano, G., Greco, S., Parisi, F., & Trubitsyna, I. (2022). Incomplete Argumentation Frameworks: Properties and Complexity. Proceedings of the AAAI Conference on Artificial Intelligence, 36(5), 5451-5460.



AAAI Technical Track on Knowledge Representation and Reasoning