paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Cut-Restriction: From Cuts to Analytic Cuts

Cut-Restriction:从切割到解析切割
LICS 2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2023匹配度 1/10 · 该论文属于纯证明论与结构证明论,研究 sequent calculus 中的 cut-restriction 与 analytic cuts,与用户关注的静态分析、Agentic 程序、浮点程序分析、贝叶斯程序分析及 LLM 交叉均无直接关联。引用 3 inbox
Agata Ciabattoni, Timo Lang, Revantha Ramanayake
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:提出 Cut-Restriction,将任意切割限制为解析切割,在无法切消时恢复子公式性质并统一已有结果。

切消是证明论的基石,但多数非经典逻辑的相继式演算并不满足切消。实际应用真正依赖的往往是其推论——子公式性质。为此,作者引入 Cut-Restriction:当无法完全消去切割时,将任意切割限制为解析切割。该过程适用于所有满足语言无关且易于检查条件的相继式演算,其设计改编自经典切消算法。结果表明,该框架以统一方式涵盖已有解析切割结果,包含 Gentzen 的切消作为特例,并建立新的解析切割性质。

问题
多数非经典逻辑的相继式演算不满足切消,而许多证明论应用真正需要的是切消带来的子公式性质。
方法
引入 Cut-Restriction,通过改编经典切消算法,把任意切割限制为解析切割;适用条件语言无关且易于检查。
评估
以证明论方式论证并比较:该框架统一涵盖已有结果,包含 Gentzen 切消,并导出新的解析切割性质。
原文摘要(Abstract)

Cut-elimination is the bedrock of proof theory with a multitude of applications from computational interpretations to proof analysis. It is also the starting point for important meta-theoretical investigations into decidability, complexity, disjunction property, interpolation, and more. Unfortunately cut-elimination does not hold for the sequent calculi of most non-classical logics. It is well-known that the key to applications is the subformula property (a typical consequence of cut-elimination) rather than cut-elimination itself. With this in mind, we introduce cut-restriction, a procedure to restrict arbitrary cuts to analytic cuts (when elimination is not possible). The algorithm applies to all sequent calculi satisfying language-independent and simple-to-check conditions, and it is obtained by adapting age-old cut-elimination. Our work encompasses existing results in a uniform way, subsumes Gentzen’s cut-elimination, and establishes new analytic cut properties.

链接与引用

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

BibTeX
@inproceedings{abs-2304-13657,
  title = {Cut-Restriction: From Cuts to Analytic Cuts},
  author = {Agata Ciabattoni and Timo Lang and Revantha Ramanayake},
  booktitle = {LICS},
  year = {2023},
  doi = {10.1109/lics56636.2023.10175785}
}