paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Inducing syntactic cut-elimination for indexed nested sequents

诱导索引嵌套矢列式的句法切消
LMCS vol.Volume 14, Issue 42018匹配度 1/10 · 该论文属于纯证明论/逻辑领域,研究索引嵌套矢列式的句法切消,与用户关注的程序分析、LLM/Agent、浮点程序分析或贝叶斯程序分析均无直接关联。虽然涉及形式化验证的理论基础,但未触及用户研究画像的核心问题。引用 2 inbox
Revantha Ramanayake
crossref: 2026-09-10

AI 速览

一句话:通过标签矢列与索引嵌套矢列式的对应,诱导句法切消并构造新的无切演算。

证明论研究常需具有子公式性质的演算。为覆盖模态逻辑 K 经 Geach 公理扩张的系统,嵌套矢列式被推广为索引嵌套矢列式,但此前的完全性与切消证明是语义的且复杂。本文证明:标签矢列式中“几乎树形”的推导恰好对应索引嵌套矢列式推导。借助该对应,作者将标签矢列演算已有的优雅证明特化,诱导出索引嵌套矢列演算的句法切消,从而避免为每种形式化独立证明。该方法还能产生新的无切演算,并首次给出中间逻辑的索引嵌套矢列演算。

问题
如何为索引嵌套矢列演算提供句法的完全性与切消证明;此前方法依赖语义且繁琐,且各形式化需独立证明。
方法
建立“几乎树形”标签矢列推导与索引嵌套矢列推导的精确对应,并通过特化标签矢列演算的已有证明变换来诱导切消。
评估
以证明论对应与构造性证明展示句法切消,并据此给出中间逻辑的首个索引嵌套矢列演算;属于理论验证而非实验评估。
原文摘要(Abstract)

The key to the proof-theoretic study of a logic is a proof calculus with a subformula property. Many different proof formalisms have been introduced (e.g. sequent, nested sequent, labelled sequent formalisms) in order to provide such calculi for the many logics of interest. The nested sequent formalism was recently generalised to indexed nested sequents in order to yield proof calculi with the subformula property for extensions of the modal logic K by (Lemmon-Scott) Geach axioms. The proofs of completeness and cut-elimination therein were semantic and intricate. Here we show that derivations in the labelled sequent formalism whose sequents are `almost treelike' correspond exactly to indexed nested sequents. This correspondence is exploited to induce syntactic proofs for indexed nested sequent calculi making use of the elegant proofs that exist for the labelled sequent calculi. A larger goal of this work is to demonstrate how specialising existing proof-theoretic transformations alleviate the need for independent proofs in each formalism. Such coercion can also be used to induce new cutfree calculi. We employ this to present the first indexed nested sequent calculi for intermediate logics. Comment: This is an extended version of the conference paper [20]

链接与引用

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

BibTeX
@article{paperbot353,
  title = {Inducing syntactic cut-elimination for indexed nested sequents},
  author = {Revantha Ramanayake},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 14, Issue 4},
  year = {2018},
  doi = {10.23638/lmcs-14(4:18)2018}
}