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