paperbot · PL 论文追踪

全部论文 待读 收藏

P2 A Proof of Stavi's Theorem

Stavi 定理的一个证明
LMCS vol.Volume 14, Issue 12018匹配度 1/10 · 该论文是关于时序逻辑表达力与 FOMLO 等价性的纯逻辑证明,虽属于形式方法基础,但不涉及静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析,与用户当前研究画像的核心问题基本无关。引用 0 inbox
Alexander Rabinovich
crossref: 2026-09-10

AI 速览

一句话:简化证明 Stavi 定理:Until、Since 与 Stavi 模态的时序逻辑在所有线性序上表达力等价于 FOMLO。

Kamp 定理表明,带 Until 与 Since 的时序逻辑在 Dedekind 完备时间流上和一阶一元序逻辑(FOMLO)表达力等价,但在有理数等线性序上并不完备。Stavi 为此引入两个额外模态,并证明在 Until、Since 与 Stavi 模态共同存在时,该时序逻辑在所有线性序上都与 FOMLO 表达力等价。本文重新给出 Stavi 定理的一个简单证明,目标是以更简洁的方式论证这一表达等价性。论文属于理论逻辑研究,不涉及实现或实验评估,其贡献主要在于提供更清晰、易验证的证明。

问题
Kamp 定理中的 Until/Since 时序逻辑在 Dedekind 完备时间流上与 FOMLO 等价,但在有理数等线性序上表达力不完全;需要证明加入 Stavi 的两个模态后可在所有线性序上恢复与 FOMLO 的表达等价。
方法
论文给出 Stavi 定理的一个简单证明,通过重新组织逻辑表达力等价的论证来证明该定理。
评估
作为理论证明论文,评估体现为证明的正确性与简洁性,不涉及程序实现、基准测试或实验。
原文摘要(Abstract)

Kamp's theorem established the expressive equivalence of the temporal logic with Until and Since and the First-Order Monadic Logic of Order (FOMLO) over the Dedekind-complete time flows. However, this temporal logic is not expressively complete for FOMLO over the rationals. Stavi introduced two additional modalities and proved that the temporal logic with Until, Since and Stavi's modalities is expressively equivalent to FOMLO over all linear orders. We present a simple proof of Stavi's theorem.Comment: arXiv admin note: text overlap with arXiv:1401.2580

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@article{paperbot421,
  title = {A Proof of Stavi's Theorem},
  author = {Alexander Rabinovich},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 14, Issue 1},
  year = {2018},
  doi = {10.23638/lmcs-14(1:20)2018}
}