arXiv cs.AI· Jinfan Xu, Jieting Luo·· 9 天前AI 评分12
有限论证框架中 grounded 与 preferred 语义的复杂度映射
Complexity of Grounded Semantics and Preferred Semantics in Finitary Argumentation Frameworks
AI 导读
该论文给出了可计算有限论证框架（AF）中 grounded 与 preferred 语义在轻信接受、怀疑接受、扩展存在性、唯一性和非空存在性等标准判定问题上的复杂度映射。
正文 · AI 翻译
摘要：Dung 提出的抽象论辩框架（AFs）为人工智能中的非单调推理提供了形式化基础。虽然一般无限 AFs 的判定问题通常位于解析谱系的高层（$\Sigma_1^1$ 或 $\Pi_1^1$），但将框架限制为可计算有穷的，可将部分复杂度降低到算术谱系。在本文中，我们给出了可计算有穷 AFs 中 grounded 和 preferred 语义在标准判定问题上的复杂度映射：轻信接受（$\Cred$）、怀疑接受（$\Skep$）、扩展存在性（$\Ex$）、唯一性（$\Uni$）和非空存在性（$\NE$）。对于 grounded 语义，轻信接受和怀疑接受已知是 $\Sigma_1^0$-完全的。我们证明非空存在性也是 $\Sigma_1^0$-完全的，而存在性和唯一性是平凡的。这些分类是在有效可计算有穷表示的范围内理解的。对于 preferred 语义，使用可计算有穷分支的计算树，$\Cred_{\pref}$ 被证明属于 $\Pi_1^0$-c，$\NE_{\pref}$ 是 $\Sigma_2^0$-c。然而，这不足以归约全称量化和全局唯一性，使得 $\Skep_{\pref}$ 处于 $\Pi_1^1$，$\UniPref$ 处于 $\Sigma_2^1$-c。我们的结果展示了有穷性成功将推理降低到算术谱系的精确边界，以及二阶量化将问题推回解析谱系的位置。
| 评论： | 15 页 |
| 主题： | 人工智能（cs.AI）；计算机科学中的逻辑（cs.LO） |
| 引用为： | arXiv:2610.12008 [cs.AI] |
| （或 arXiv:2610.12008v1 [cs.AI] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2610.12008 arXiv 颁发的 DOI 通过 DataCite（待注册） |
提交历史
来自：Jinfan Xu [查看电子邮件]
[v1]
2026年10月8日星期四 14:10:16 UTC（33 KB）
来源：arXiv cs.AI · arxiv.org