paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Interpolation for the two-way modal μ-calculus

双向模态 μ-演算的插值性质
LICS 2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2025匹配度 2/10 · 该论文属于纯逻辑与证明论,研究双向模态 μ-演算的矢列系统、Craig 插值和 Beth 可定义性,与用户关注的静态分析、LLM/Agent、浮点程序分析及贝叶斯程序分析没有直接交叉。虽与形式化验证的理论基础相邻,但既未涉及程序分析落地,也未使用或改进 LLM/Agent。引用 0 inbox
Johannes Kloibhofer, Yde Venema
crossref: 2026-09-12

AI 速览

一句话:为双向模态 μ-演算引入非良基与循环矢列证明系统,证明其可靠完备,并推出 Craig 插值与 Beth 可定义性。

双向模态 μ-演算是在标准单向 μ-演算上加入反向模态的扩展。论文为该逻辑提出两种新的矢列式证明演算:允许无限分支的非良基系统,以及带标注的有限循环版本;二者均包含分析性切规则,并借助迹原子在证明论中应用 Vardi 的双向自动机。作者证明两个系统的可靠性与完备性,随后利用循环演算证明该逻辑关于命题和模态均具有局部 Craig 插值性质。证明方法是将 Maehara 方法适配到循环证明系统,并由此推出 Beth 可定义性。

问题
如何为双向模态 μ-演算建立合适的证明论,并刻画其插值与可定义性等性质。
方法
引入非良基和有限循环矢列演算,使用迹原子连接 Vardi 双向自动机,并改造 Maehara 方法以处理循环证明。
评估
通过证明两个系统的可靠性与完备性,并推导出局部 Craig 插值性质和 Beth 可定义性来评估。
原文摘要(Abstract)

The two-way modal μ-calculus is the extension of the (standard) one-way μ-calculus with converse (backward-looking) modalities. For this logic we introduce two new sequent-style proof calculi: a non-wellfounded system admitting infinite branches and a finitary, cyclic version of this that employs annotations.As is common in sequent systems for two-way modal logics, our calculi feature an analytic cut rule. What distinguishes our approach is the use of so-called trace atoms, which serve to apply Vardi’s two-way automata in a proof-theoretic setting.We prove soundness and completeness for both systems and subsequently use the cyclic calculus to show that the two-way μ-calculus has the (local) Craig interpolation property, with respect to both propositions and modalities. Our proof uses a version of Maehara’s method adapted to cyclic proof systems. As a corollary we prove that the two-way μ-calculus also enjoys Beth’s definability property.

链接与引用

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

BibTeX
@inproceedings{paperbot8623,
  title = {Interpolation for the two-way modal μ-calculus},
  author = {Johannes Kloibhofer and Yde Venema},
  booktitle = {LICS},
  year = {2025},
  doi = {10.1109/lics65433.2025.00019}
}