研究无限论证框架的最小固定点计算复杂度，发现其远超有限情形。
On the Complexity of the Grounded Semantics for Infinite Argumentation Frameworks
- 用递归迭代求最小固定点，需跨无穷序数步骤。
- 判定基底接受性是最大可能复杂度，不可简化。
- 适合逻辑与复杂性理论研究者阅读。
论证框架由论点及代表冲突的攻击关系构成，是形式化研究矛盾信息推理的基础。本文运用数学逻辑中的可计算性与集合论方法，分析广泛使用的最大怀疑性推理模型——基底扩展，该扩展定义为自然防御算子的最小固定点。在无额外约束下，求取此固定点需进行超限迭代。本文确定了该迭代过程对应的精确序数，并揭示判定基底接受性的复杂度为最大可能级别。这与有限情形形成鲜明对比：在有限情况下，基底扩展可在多项式时间内计算，比其他形式论证中的推理问题更简单。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。