On the Complexity of the Grounded Semantics for Infinite Argumentation Frameworks
This addresses foundational issues in formal argumentation for AI and logic, revealing inherent computational barriers in infinite settings.
The paper tackles the problem of computing the grounded extension in infinite argumentation frameworks, showing that it requires transfinite iterations and is maximally complex, unlike the polynomial-time computable finite case.
Argumentation frameworks, consisting of arguments and an attack relation representing conflicts, are fundamental for formally studying reasoning under conflicting information. We use methods from mathematical logic, specifically computability and set theory, to analyze the grounded extension, a widely-used model of maximally skeptical reasoning, defined as the least fixed-point of a natural defense operator. Without additional constraints, finding this fixed-point requires transfinite iterations. We identify the exact ordinal number corresponding to the length of this iterative process and determine the complexity of deciding grounded acceptance, showing it to be maximally complex. This shows a marked distinction from the finite case where the grounded extension is polynomial-time computable, thus simpler than other reasoning problems explored in formal argumentation.