paperbot · PL 论文追踪

全部论文 待读 收藏

P2 A sequent calculus with dependent types for classical arithmetic

带依赖类型的经典算术相继式演算
LICS Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science2018匹配度 2/10 · 该论文属于纯证明论与类型论研究,讨论经典算术中带依赖类型的相继式演算与正规化,不涉及静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析,仅与形式化验证的理论基础有间接关联。引用 7 inbox
Étienne Miquey
crossref: 2026-09-12

AI 速览

一句话:提出带依赖类型的经典算术相继式演算,以攻克 dPAω 中依赖类型、控制算子、余归纳与惰性共享共存下的正规化难题。

本文研究带依赖类型的经典算术演算,源于 Herbelin 的 dPAω:该演算把可数全称量化的证明编码为分量流,从而由构造性证明导出可数与依赖选择公理,但其正规化与可靠性仅是猜想。主要困难是依赖类型(选择的构造性部分)、控制算子(经典逻辑)、余归纳对象(以流编码 N→A 函数)和带共享的惰性求值同时出现。论文提出一个带依赖类型的相继式演算,试图在同一证明论框架中统一处理这些特征,为 dPAω 的正规化提供基础。摘要未给出实验评估,工作属证明论与类型论元理论研究。

问题
dPAω 的正规化与可靠性仅有猜想;同时存在依赖类型、控制算子、余归纳对象和带共享惰性求值,导致证明困难。
方法
据标题与摘要,论文构造一个带依赖类型的相继式演算,用证明论方式统一刻画经典算术中的这些特性。
评估
摘要未给出评估方式或实验结果;从内容看工作属于证明论与类型论的元理论研究。
原文摘要(Abstract)

In a recent paper [11], Herbelin developed dPAω, a calculus in which constructive proofs for the axioms of countable and dependent choices could be derived via the encoding of a proof of countable universal quantification as a stream of it components. However, the property of normalization (and therefore the one of soundness) was only conjectured. The difficulty for the proof of normalization is due to the simultaneous presence of dependent types (for the constructive part of the choice), of control operators (for classical logic), of coinductive objects (to encode functions of type N→A into streams (a0, a1, ...)) and of lazy evaluation with sharing (for these coinductive objects).

链接与引用

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

BibTeX
@inproceedings{paperbot4365,
  title = {A sequent calculus with dependent types for classical arithmetic},
  author = {Étienne Miquey},
  booktitle = {LICS},
  year = {2018},
  doi = {10.1145/3209108.3209199}
}