研究无限但有限攻击的论证框架，发现其计算复杂度可大幅降低。
Complexity in finitary argumentation (extended version)
- 限定每个论点仅被有限个其他论点攻击，简化推理结构。
- 在可接受性语义下，发现组合约束使复杂度显著下降。
- 适合需要表达力又兼顾计算效率的推理场景研究者。
抽象论证框架（AFs）为分析冲突信息的多种推理形式提供了形式化设定。尽管一般无限AFs具有强大表达能力，适合建模多种推理场景，但其求解的计算不可行性限制了实际应用，甚至影响理论研究。本文研究无限但有限攻击的论证框架——即每个论点仅被有限数量的其他论点攻击——的计算复杂性。结果揭示了一个出人意料的现象：有限攻击的假设并不自动带来复杂度下降。然而，在基于可接受性的语义下，我们发现一个关键的组合约束，能导致复杂度急剧降低。结论表明，对于许多推理任务，有限攻击的无限框架在表达力与计算可行性之间实现了良好平衡，是实用且富有潜力的推理建模工具。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。