paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Simply-typed constant-domain modal lambda calculus I: distanced beta reduction and combinatory logic

简单类型常域模态 λ 演算 I:距离化 β-归约与组合逻辑
LMCS vol.Volume 22, Issue 32026匹配度 1/10 · 该论文研究模态简单类型 λ 演算的元理论、组合逻辑模型与保守性,属于形式语义/逻辑基础,与用户关注的静态分析、LLM/Agent、浮点程序分析、贝叶斯程序分析等方向无直接关联。引用 1 inbox
Sean Walsh
crossref: 2026-09-10

AI 速览

一句话:提出参数化模态简单类型 λ 演算 λθ,给出基于 BCKW 组合逻辑的模型刻画及与最大系统 λω 的保守性结果。

本文在简单类型 λ 演算中发展系统 λθ,将模态逻辑与简单类型 λ 演算结合,并推广 Montague 与 Gallin 的框架。与后者基于 Church 简单类型论不同,λθ 由参数 θ 控制,允许更丰富的状态类型与状态变量选择。论文旨在建立其基本元理论:给出类似 Andrews 的模型刻画,用组合逻辑表示模型,且该组合逻辑采用 BCKW 式而非 SKI 式基;证明 λθ 与最大系统 λω 的语义保守性与可表达性,并类似比较 λω 与 λ,回答 Zimmermann 的问题。文章还建立以 BCKW 式基为核心的纯组合逻辑与 λω 弱演绎系统(不允许在 λ 抽象下 β-归约)的部分对应,并得到 λω 与 λθ 的部分演绎保守性。

问题
Montague 与 Gallin 的模态语义基于 Church 简单类型论,本文要在现代简单类型 λ 演算中发展更一般的模态 λ 演算,并研究其模型与保守性等元理论性质。
方法
定义由参数 θ 控制状态类型与状态变量的系统 λθ,并借助组合逻辑与指称模型给出模型刻画,比较 λθ、最大系统 λω 与普通简单类型 λ 演算 λ。
评估
通过语义保守性/可表达性以及部分演绎保守性等定理进行理论评估,涉及 BCKW 式组合逻辑基与 λ 抽象下禁用 β-归约的弱演绎系统。
原文摘要(Abstract)

A system $\boldsymbolλ_θ$ is developed that combines modal logic and simply-typed lambda calculus, and that generalizes the system studied by Montague and Gallin. Whereas Montague and Gallin worked with Church's simple theory of types, the system $\boldsymbolλ_θ$ is developed in the typed base theory most commonly used today, namely the simply-typed lambda calculus. Further, the system $\boldsymbolλ_θ$ is controlled by a parameter $θ$ which allows more options for state types and state variables than is present in Montague and Gallin. A main goal of the paper is to establish some basic metatheory of $\boldsymbolλ_θ$: (i) an Andrews-like characterization of its models in terms of combinatory logic is given, and this combinatory logic involves a $\mathsf{BCKW}$-like basis rather than an $\mathsf{SKI}$-like basis and (ii) semantic conservation and expressibility results relating $\boldsymbolλ_θ$ to the maximal system $\boldsymbolλ_ω$ are proven. Similar results are proven for the relation between $\boldsymbolλ_ω$ and $\boldsymbolλ$, the corresponding ordinary simply-typed lambda calculus. This answers a question of Zimmermann in the semantics of the simply typed setting. In a companion paper this is extended to Church's simple theory of types. We further develop a partial correspondence between a pure combinatory logic centered on the $\mathsf{BCKW}$-like basis and the weak deductive system for $\boldsymbolλ_ω$ wherein $β$-reduction is not allowed under a lambda abstract, and we use this to show partial deductive conservation between the maximal system $\boldsymbolλ_ω$ and the intermediary systems $\boldsymbolλ_θ$.

链接与引用

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

BibTeX
@article{Walsh26,
  title = {Simply-typed constant-domain modal lambda calculus I: distanced beta reduction and combinatory logic},
  author = {Sean Walsh},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 22, Issue 3},
  year = {2026},
  doi = {10.46298/lmcs-22(3:4)2026}
}