paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Cut-free completeness for modal mu-calculus

模态 μ-演算的无割完备性
LICS 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2017匹配度 1/10 · 论文是模态μ演算的无割完备性证明,属于纯逻辑与证明论工作,与用户关注的LLM/Agent、静态分析、浮点程序分析、贝叶斯程序分析等方向均无直接关联;虽属形式化验证基础,但不涉及Agent、静态分析工具或工程落地。引用 83 inbox
Bahareh Afshari, Graham E. Leigh
crossref: 2026-09-12dblp: 2026-09-12

AI 速览

一句话:为模态 μ-演算给出两个有限无割矢列演算,并由此构造性地证明 Kozen 公理系统的完备性。

本文研究模态 μ-演算的证明论,目标是给出无割且有限的矢列演算,并重新建立 Kozen 公理系统的完备性。作者提出两个演算:其一将 Kozen 公理系统中的 cut 替换为对最大不动点归纳规则的强化;其二采用 Stirling 带名字的表列证明系统风格,推导带标注的矢列,并推广 ν-再生规则以允许释放开放假设。完备性与可靠性通过一系列证明系统之间的嵌入来证明:从 Stirling 的表列证明出发,逐步嵌入到 Kozen 的原始公理系统。作为推论,得到 Kozen 公理化完备性的新构造性证明,避免通常经由自动机与博弈的绕道。

问题
如何为模态 μ-演算提供无割、有限的矢列演算,并直接证明 Kozen 公理系统的完备性,而不依赖自动机与博弈。
方法
构造两个无割矢列演算,并通过从 Stirling 表列证明到 Kozen 公理系统的一系列嵌入证明其可靠性与完备性。
评估
评估方式为证明论论证:以嵌入关系建立两个演算的可靠性与完备性,并作为推论得到 Kozen 公理化完备性的构造性证明,避免自动机与博弈路线。
原文摘要(Abstract)

We present two finitary cut-free sequent calculi for the modal μ-calculus. One is a variant of Kozen's axiomatisation in which cut is replaced by a strengthening of the induction rule for greatest fixed point. The second calculus derives annotated sequents in the style of Stirling's `tableau proof system with names' (2014) and features a generalisation of the ν-regeneration rule that allows discharging open assumptions. Soundness and completeness for the two calculi is proved by establishing a sequence of embeddings between proof systems, starting at Stirling's tableau-proofs and ending at the original axiomatisation of the μ-calculus due to Kozen. As a corollary we obtain a new, constructive, proof of completeness for Kozen's axiomatisation which avoids the usual detour through automata and games.

链接与引用

DOI 原文 · DBLP

BibTeX
@inproceedings{AfshariL17,
  title = {Cut-free completeness for modal mu-calculus},
  author = {Bahareh Afshari and Graham E. Leigh},
  booktitle = {LICS},
  year = {2017},
  doi = {10.1109/lics.2017.8005088}
}