Revisiting the Notion of Extension over Incomplete Abstract Argumentation Frameworks

Revisiting the Notion of Extension over Incomplete Abstract Argumentation Frameworks

Bettina Fazzinga, Sergio Flesca, Filippo Furfaro

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
Main track. Pages 1712-1718. https://doi.org/10.24963/ijcai.2020/237

We revisit the notion of i-extension, i.e., the adaption of the fundamental notion of extension to the case of incomplete Abstract Argumentation Frameworks. We show that the definition of i-extension raises some concerns in the "possible" variant, e.g., it allows even conflicting arguments to be collectively considered as members of an (i-)extension. Thus, we introduce the alternative notion of i*-extension overcoming the highlighted problems, and provide a thorough complexity characterization of the corresponding verification problem. Interestingly, we show that the revisitation not only has beneficial effects for the semantics, but also for the complexity: under various semantics, the verification problem under the possible perspective moves from NP-complete to P.
Keywords:
Knowledge Representation and Reasoning: Computational Complexity of Reasoning
Knowledge Representation and Reasoning: Computational Models of Argument