Computational Properties of Resolution-based Grounded Semantics

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.

Pietro Baroni, Paul E. Dunne, Massimiliano Giacomin