paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Adding Negation to Lambda Mu

向 λμ-演算中添加否定
LMCS vol.Volume 19, Issue 22023匹配度 3/10 · 该论文属于纯类型论/形式语义研究,关注 λμ-演算中否定类型构造及合流、强规范化、主类型等元理论性质,与用户画像中的静态分析、LLM/Agent、浮点程序分析、贝叶斯程序分析等核心方向没有直接交集。虽然同属程序语言与形式验证的理论基础,但缺少 AI/LLM 交叉、工程落地或问题驱动 benchmark 等用户关注点。引用 3 inbox
Steffen van Bakel
crossref: 2026-09-10

AI 速览

一句话:在 Parigot 的 λμ-演算中引入否定类型构造及语法构造,并证明其归约合流、强规范化与主类型性质。

本文研究如何在 Parigot 的 λμ-演算中处理否定。作者提出扩展系统 L,将否定作为类型构造子,并加入否定的引入与消去语法构造;同时扩展归约系统,新增两条归约规则。文章首先证明该归约满足 subject reduction,并借助 Aczel 对 Tait 与 Martin-Löf 平行归约的推广证明其合流性。虽然该类型赋值在表示含蕴涵与否定的自然演绎证明方面存在局限,作者仍证明所有可在该自然演绎系统中证明的命题在 L 中都有见证。最后,利用 Girard 的可归约候选方法证明所有可类型化项都强规范化,并表明 L 的类型赋值具有主类型性质。

问题
如何将否定作为类型构造子加入 Parigot 的 λμ-演算,并建立其归约与类型赋值理论?
方法
扩展 λμ-演算,加入否定引入/消去构造和两条归约规则,使用平行归约与可归约候选证明元理论性质。
评估
通过证明 subject reduction、合流性、强规范化、自然演绎命题的见证存在以及主类型性质来评估该系统。
原文摘要(Abstract)

We present $\cal L$, an extension of Parigot's $\lambda\mu$-calculus by adding negation as a type constructor, together with syntactic constructs that represent negation introduction and elimination. We will define a notion of reduction that extends $\lambda\mu$'s reduction system with two new reduction rules, and show that the system satisfies subject reduction. Using Aczel's generalisation of Tait and Martin-L\"of's notion of parallel reduction, we show that this extended reduction is confluent. Although the notion of type assignment has its limitations with respect to representation of proofs in natural deduction with implication and negation, we will show that all propositions that can be shown in there have a witness in $\cal L$. Using Girard's approach of reducibility candidates, we show that all typeable terms are strongly normalisable, and conclude the paper by showing that type assignment for $\cal L$ enjoys the principal typing property.

链接与引用

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

BibTeX
@article{paperbot2215,
  title = {Adding Negation to Lambda Mu},
  author = {Steffen van Bakel},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 19, Issue 2},
  year = {2023},
  doi = {10.46298/lmcs-19(2:12)2023}
}