paperbot · PL 论文追踪

全部论文 待读 收藏

P2 The recursion hierarchy for PCF is strict

PCF 的递归层级是严格的
LMCS vol.Volume 14, Issue 32018匹配度 1/10 · 该论文属于纯形式语义与函数式语言理论,研究PCF中不动点算子的严格递归层级,与用户关注的静态分析、Agentic/LLM程序分析、浮点程序分析及贝叶斯程序分析无直接关联;仅同属程序语言理论领域。引用 2 inbox
John Longley
crossref: 2026-09-10

AI 速览

一句话:证明在 PCF 中按类型层级限制不动点算子会形成严格递归层级,低层不动点无法定义高层不动点。

论文研究 Plotkin 的 PCF 语言中按类型层级限制不动点算子所得的各个子语言。具体地,对每个 k,只允许层级不超过 k 的类型使用不动点算子,称其为递归层级 k 的子语言。作者证明这些子语言构成严格层级:对于层级为 k 的类型,其不动点算子无法用更低层级的不动点算子定义,即使只要求到观测等价也不行。这回答了 Berger 提出的问题。证明方法大量使用嵌套顺序过程(nested sequential procedures,也称 PCF Böhm 树)理论,该理论在 Longley 与 Normann 的专著中已系统阐述。

问题
PCF 中按类型层级限制不动点算子所得到的子语言是否形成严格层级,即高层类型的不动点能否由低层不动点定义。
方法
利用嵌套顺序过程(PCF Böhm 树)理论,对由低层不动点算子定义的可观测行为进行分析,证明高层不动点算子不可由它们定义。
评估
通过可定义性与观测等价的理论证明,确立递归层级的严格性,并回答 Berger 的问题。
原文摘要(Abstract)

We consider the sublanguages of Plotkin's PCF obtained by imposing some bound k on the levels of types for which fixed point operators are admitted. We show that these languages form a strict hierarchy, in the sense that a fixed point operator for a type of level k can never be defined (up to observational equivalence) using fixed point operators for lower types. This answers a question posed by Berger. Our proof makes substantial use of the theory of nested sequential procedures (also called PCF B\"ohm trees) as expounded in the recent book of Longley and Normann.

链接与引用

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

BibTeX
@article{paperbot387,
  title = {The recursion hierarchy for PCF is strict},
  author = {John Longley},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 14, Issue 3},
  year = {2018},
  doi = {10.23638/lmcs-14(3:8)2018}
}