paperbot · PL 论文追踪

全部论文 待读 收藏

P2 On sets of terms having a given intersection type

关于具有给定交集类型的项集
LMCS vol.Volume 18, Issue 32022匹配度 1/10 · 该论文属于类型系统与形式语义的纯理论研究,讨论交集类型、强规范化λ项和可分离性,未涉及LLM/Agentic程序、静态分析、浮点程序分析或贝叶斯程序分析,与用户当前核心研究方向几乎无交集。引用 0 inbox
Andrew Polonsky, Richard Statman
crossref: 2026-09-10

AI 速览

一句话:证明每个强规范化 λ 项都有唯一交集类型,并揭示给定类型闭项集的可分离性与数字系统性质。

本文在 Coppo、Dezani-Ciancaglini 与 Venneri(1981)交集类型指派系统的一个变体中,研究具有给定交集类型的 λ 项集合。作者首先讨论交集类型代数的若干表示及相应类型指派规则的选择,并利用内部化的 Böhm-out 技术分析给定交集类型下的项。主要结果是:每个强规范化项 M 都存在唯一类型(uniqueness typing)(Γ,A),使得 Γ⊢M:A,且任何满足 Γ⊢N:A 的项 N 都与 M 在 βη 下相等。此外,具有给定类型的闭项集是一致可分离的;若该集合无限,则构成一个 adequate numeral system。

问题
刻画具有同一交集类型的 λ 项集合,并研究强规范化项的类型唯一性及给定类型项集的可分离性质。
方法
在 Coppo-Dezani-Ciancaglini-Venneri 交集类型指派系统的变体中,讨论交集类型代数表示与规则选择,并使用内部化 Böhm-out 技术。
评估
证明 uniqueness typing 存在性、给定类型闭项集的一致可分离性,以及无限时构成 adequate numeral system。
原文摘要(Abstract)

Working in a variant of the intersection type assignment system of Coppo, Dezani-Ciancaglini and Venneri [1981], we prove several facts about sets of terms having a given intersection type. Our main result is that every strongly normalizing term M admits a *uniqueness typing*, which is a pair $(\Gamma,A)$ such that 1) $\Gamma \vdash M : A$ 2) $\Gamma \vdash N : A \Longrightarrow M =_{\beta\eta} N$ We also discuss several presentations of intersection type algebras, and the corresponding choices of type assignment rules. Moreover, we show that the set of closed terms with a given type is uniformly separable, and, if infinite, forms an adequate numeral system. The proof of this fact uses an internal version of the B\"ohm-out technique, adapted to terms of a given intersection type.

链接与引用

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

BibTeX
@article{paperbot1650,
  title = {On sets of terms having a given intersection type},
  author = {Andrew Polonsky and Richard Statman},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 18, Issue 3},
  year = {2022},
  doi = {10.46298/lmcs-18(3:35)2022}
}