Computational Properties of Resolution-based Grounded Semantics

P. Baroni, P. E. Dunne, M. Giacomin

Proc. of IJCAI 09, 21st International Joint Conference on Artificial Intelligence, Pasadena, CA, 2009, 683-689

 

Abstract

In the context of Dung’s theory of abstract argumentation frameworks, the recently introduced resolution-based grounded semantics features the unique property of fully complying with a set of general requirements, only partially satisfied by previous literature proposals. This paper contributes to the investigation of resolution-based grounded semantics by analyzing its computational properties with reference to a standard set of decision problems for abstract argumentation semantics: (a) checking the property of being an extension for a set of arguments; (b) checking agreement with traditional grounded semantics; (c) checking the existence of a non-empty extension; (d) checking credulous acceptance of an argument; (e) checking skeptical acceptance of an argument. It is shown that problems (a)-(c) admit polynomial time decision processes, while (d) is NP–complete and (e) coNP–complete.

Publisher's on-line resources

Return to publication list