Complexity in finitary argumentation (extended version)
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
SCC-recursiveness in infinite argumentation (extended version)
Argumentation frameworks (AFs) are a foundational tool in artificial intelligence for modeling structured reasoning and conflict. SCC-recursiveness is a well-known design principle in which the evaluation of arguments is…
Possible Controllability of Control Argumentation Frameworks -- Extended Version
The recent Control Argumentation Framework (CAF) is a generalization of Dung's Argumentation Framework which handles argumentation dynamics under uncertainty; especially it can be used to model the behavior of an agent w…
Stable Models for Infinitary Formulas with Extensional Atoms
The definition of stable models for propositional formulas with infinite conjunctions and disjunctions can be used to describe the semantics of answer set programming languages. In this note, we enhance that definition b…
Admissibility in Strength-based Argumentation: Complexity and Algorithms (Extended Version with Proofs)
Recently, Strength-based Argumentation Frameworks (StrAFs) have been proposed to model situations where some quantitative strength is associated with arguments. In this setting, the notion of accrual corresponds to sets …
LEMMAAutomata for Infinite Argumentation Structures
The theory of abstract argumentation frameworks (afs) has, in the main, focused on finite structures, though there are many significant contexts where argumentation can be regarded as a process involving infinite objects…
Abstract Argumentation