paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Normalization for Cubical Type Theory

立方类型论的归一化
LICS 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2021匹配度 2/10 · 该论文属于立方类型论的元理论(归一化、判断相等可判定性),与用户关注的静态分析、LLM/Agent 改进程序分析、浮点程序分析或贝叶斯程序分析均无直接关系。它虽是形式化验证的理论基础工作,但未涉及 LLM/Agent 或工业工具落地,因此匹配度很低。引用 3 inbox
Jonathan Sterling, Carlo Angiuli
crossref: 2026-09-12

AI 速览

一句话:证明了(单值、笛卡尔)立方类型论的归一化,得到无归约的范式双射,并推出判断相等的可判定性与类型构造子单射性。

本文为(单值、笛卡尔)立方类型论证明归一化,解决了该理论句法元理论中最后一个主要未决问题。作者采用无归约(reduction-free)的归一化方法,不是通过逐步归约,而是建立上下文中项的可定义等价类与一类可处理的 β/η-范式语言之间的双射,从而给出范式的组合刻画。该结果直接蕴含判断相等的可判定性,并推出类型构造子的单射性。这为立方类型论作为同伦类型论计算模型的句法基础提供了关键保证,也补全了其元理论拼图。

问题
立方类型论的句法元理论缺少归一化证明,无法直接保证判断相等可判定以及类型构造子单射。
方法
给出无归约的归一化证明,构造上下文中项的等价类与 β/η-范式之间的双射。
评估
通过元理论证明完成,并以该归一化定理为推论得到判断相等可判定性与类型构造子单射性。
原文摘要(Abstract)

We prove normalization for (univalent, Cartesian) cubical type theory, closing the last major open problem in the syntactic metatheory of cubical type theory. Our normalization result is reduction-free, in the sense of yielding a bijection between equivalence classes of terms in context and a tractable language of β/η-normal forms. As corollaries we obtain both decidability of judgmental equality and the injectivity of type constructors.

链接与引用

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

BibTeX
@inproceedings{paperbot6223,
  title = {Normalization for Cubical Type Theory},
  author = {Jonathan Sterling and Carlo Angiuli},
  booktitle = {LICS},
  year = {2021},
  doi = {10.1109/lics52264.2021.9470719}
}