Complexity in finitary argumentation (extended version)
This addresses the problem of computational intractability in infinite argumentation frameworks for researchers in formal reasoning, offering a balance between expressiveness and tractability, though it is incremental in focusing on finitary constraints.
The paper investigates the computational complexity of infinite but finitary argumentation frameworks, where each argument has finitely many attackers, finding that while finitary does not always reduce complexity, admissibility-based semantics show a dramatic decrease in complexity, making these frameworks both expressive and computationally tractable for many reasoning scenarios.
Abstract argumentation frameworks (AFs) provide a formal setting to analyze many forms of reasoning with conflicting information. While the expressiveness of general infinite AFs make them a tempting tool for modeling many kinds of reasoning scenarios, the computational intractability of solving infinite AFs limit their use, even in many theoretical applications. We investigate the complexity of computational problems related to infinite but finitary argumentations frameworks, that is, infinite AFs where each argument is attacked by only finitely many others. Our results reveal a surprising scenario. On one hand, we see that the assumption of being finitary does not automatically guarantee a drop in complexity. However, for the admissibility-based semantics, we find a remarkable combinatorial constraint which entails a dramatic decrease in complexity. We conclude that for many forms of reasoning, the finitary infinite AFs provide a natural setting for reasoning which balances well the competing goals of being expressive enough to be applied to many reasoning settings while being computationally tractable enough for the analysis within the framework to be useful.