paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Normalization for multimodal type theory

多模态类型论的规范化
LMCS vol.Volume 22, Issue 12026匹配度 1/10 · 该论文是纯类型论/形式语义方向,研究多模态类型论的规范化与类型检查算法,不涉及静态分析、ML/Agentic 程序、浮点程序分析、贝叶斯程序分析,也不涉及 LLM/Agent 与形式化验证的交叉。引用 1 inbox
Daniel Gratzer
crossref: 2026-09-10crossref: 2026-09-12

AI 速览

一句话:证明了多模态类型论 MTT 的规范化,并将类型检查与转换判定归约为底层模态相等性,从而给出统一算法。

本文研究多模态依赖类型论 MTT 的元理论。MTT 可统一刻画守卫递归、内部参数性等多种模态类型论,但其类型检查与转换判定缺乏通用算法。作者证明 MTT 的规范化,并说明判定 MTT 中的类型检查与转换可归约为判定底层模态情形中模态的相等性,从而为文献中所有 MTT 实例立即导出类型检查算法。证明推广了合成 Tait 可计算性这一抽象胶合方法以处理模态,且该推广基于 MTT 自身,因此同时构成 MTT 的重要案例研究。

问题
MTT 能统一表达守卫递归、内部参数性等模态类型论,但其类型检查、转换判定与规范化尚无适用于所有实例的一般性证明与算法。
方法
作者推广合成 Tait 可计算性(synthetic Tait computability)这一抽象胶合方法以处理模态,并基于 MTT 自身构造规范化证明。
评估
通过数学证明表明类型检查与转换可归约为底层模态情形中的模态相等性,由此得到文献中所有 MTT 实例的类型检查算法,并作为 MTT 的重要案例研究。
原文摘要(Abstract)

We prove normalization for MTT, a general multimodal dependent type theory capable of expressing modal type theories for guarded recursion, internalized parametricity, and various other prototypical modal situations. We prove that deciding type checking and conversion in MTT can be reduced to deciding the equality of modalities in the underlying modal situation, immediately yielding a type checking algorithm for all instantiations of MTT in the literature. This proof uses a generalization of synthetic Tait computability -- an abstract approach to gluing proofs -- to account for modalities. This extension is based on MTT itself, so that this proof also constitutes a significant case study of MTT.

链接与引用

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

BibTeX
@article{paperbot4010,
  title = {Normalization for multimodal type theory},
  author = {Daniel Gratzer},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 22, Issue 1},
  year = {2026},
  doi = {10.46298/lmcs-22(1:27)2026}
}