提出可计算的非有限信念收缩方法，突破传统限制
Effective AGM Belief Contraction: A Journey beyond the Finitary Realm (Technical Report)
- 用线性时序逻辑与巴奇自动机构造可计算信念收缩函数
- 证明非有限逻辑中存在无穷多个不可计算的收缩函数
- 为时序逻辑信念更新提供新范式，适合逻辑与AI研究者
尽管已有大量工作尝试将AGM信念变化范式拓展至非有限逻辑，但其计算性问题几乎未被触及。本文研究非有限逻辑上AGM收缩的可计算性，揭示一个令人惊讶的负面结果：此类逻辑中存在无穷多个不可计算的AGM收缩函数。更严重的是，当前控制可计算性的主流策略——通过限制认知状态空间——在所有非有限情形下均失效。基于此颠覆性发现，本文提出新方法以在非有限领域控制可计算性。以线性时序逻辑（LTL）为例，识别出一类无限的、完全理性的可计算AGM收缩函数。通过巴奇自动机构建这些函数，并用于表示和推理LTL信念。
原文摘要 · Abstract (English)
Despite significant efforts towards extending the AGM paradigm of belief change beyond finitary logics, the computational aspects of AGM have remained almost untouched. We investigate the computability of AGM contraction on non-finitary logics, and show an intriguing negative result: there are infinitely many uncomputable AGM contraction functions in such logics. Drastically, we also show that the current de facto standard strategies to control computability, which rely on restricting the space of epistemic states, fail: uncomputability remains in all non-finitary cases. Motivated by this disruptive result, we propose new approaches to controlling computability beyond the finitary realm. Using Linear Temporal Logic (LTL) as a case study, we identify an infinite class of fully-rational AGM contraction functions that are computable by design. We use Büchi automata to construct such functions, and to represent and reason about LTL beliefs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。