paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Completions of Kleene's second model

Kleene 第二模型的完备化
LMCS vol.Volume 21, Issue 22025匹配度 1/10 · 论文研究部分组合代数与 Kleene 第二模型的嵌入/完备化,属于纯形式语义与可计算性理论,与用户关注的 ML/Agentic 程序静态分析、LLM 与静态分析/形式化验证交叉、浮点或贝叶斯程序分析均无直接关联。引用 2 inbox
Sebastiaan A. Terwijn
crossref: 2026-09-10

AI 速览

一句话:将 Kleene 第二模型 K2 的弱嵌入性质推广到任意基数,并证明其推广具有强完备化。

本文研究部分组合代数(pca)的完备化,重点关注 Kleene 第二模型 K2 及其推广。作者考察文献中已有的弱与强可嵌入性及完备化概念。已知每个可数 pca 均可弱嵌入 K2;本文通过构造适用于更大基数的 K2 推广,将该结果推广到任意基数,从而进一步凸显 K2 在 pca 研究中的核心地位。此外,论文证明 K2 及其推广均具有强完备化。工作属于可计算性理论与组合代数语义的交叉,采用数学证明与构造性方法,为 pca 的嵌入与完备化理论提供了统一视角。

问题
研究部分组合代数(pca)的完备化,特别是 Kleene 第二模型 K2 及其推广的弱/强可嵌入性与完备化性质。
方法
在已有弱与强可嵌入性、完备化概念下,构造更大基数上的 K2 推广,并通过数学证明分析其嵌入与完备化性质。
评估
理论证明:将可数 pca 弱嵌入 K2 的结果推广到任意基数,并证明 K2 及其推广具有强完备化;无实验评估。
原文摘要(Abstract)

We investigate completions of partial combinatory algebras (pcas), in particular of Kleene's second model $\mathcal{K}_2$ and generalizations thereof. We consider weak and strong notions of embeddability and completion that have been studied before in the literature. It is known that every countable pca can be weakly embedded into $\mathcal{K}_2$, and we generalize this to arbitrary cardinalities by considering generalizations of $\mathcal{K}_2$ for larger cardinals. This emphasizes the central role of $\mathcal{K}_2$ in the study of pcas. We also show that $\mathcal{K}_2$ and its generalizations have strong completions.

链接与引用

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

BibTeX
@article{abs-2312-14656,
  title = {Completions of Kleene's second model},
  author = {Sebastiaan A. Terwijn},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 21, Issue 2},
  year = {2025},
  doi = {10.46298/lmcs-21(2:17)2025}
}