paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Fully Abstract Normal Form Bisimulation for Call-by-Value PCF

按值调用 PCF 的完全抽象正规形式双模拟
LICS 2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2023匹配度 2/10 · 该论文属于纯 PL/形式语义与程序等价性验证,虽与形式化验证基础相关,但不涉及 LLM/Agent 改进验证、ML/Agentic 程序静态分析、浮点程序分析或贝叶斯程序分析等画像核心问题。引用 9 inbox
Vasileios Koutavas, Yu-Yang Lin, Nikos Tzevelekos
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:提出首个针对按值调用 PCF 的完全抽象正规形式双模拟,并实现有界检查工具。

论文为按值调用 PCF(PCFv)提出首个完全抽象的正规形式双模拟。问题在于获得既可靠又完备、且无需语义商化的程序等价证明方法。方法上,作者构建了一个标记迁移系统(LTS),融合应用双模拟、环境双模拟与博弈语义;该 LTS 生成与可能函数上下文交互对应的轨迹,从而在避免语义商化的同时获得完备性。由此得到检查 PCFv 程序等价的可靠且完备技术,并实现有界双模拟检查工具。评估方面,作者在文献中已知的等价实例和新例子上测试了该工具。

问题
如何为按值调用 PCF 建立完全抽象且可操作的程序等价证明或检查方法,同时避免使用语义商化。
方法
构造融合应用双模拟、环境双模拟和博弈语义的标记迁移系统,用与可能函数上下文交互的轨迹刻画上下文等价,并实现有界双模拟检查工具。
评估
在文献中已知的等价实例以及新构造的例子上测试有界双模拟检查工具。
原文摘要(Abstract)

We present the first fully abstract normal form bisimulation for call-by-value PCF (PCFv). Our model is based on a labelled transition system (LTS) that combines elements from applicative bisimulation, environmental bisimulation and game semantics. In order to obtain completeness while avoiding the use of semantic quotiening, the LTS constructs traces corresponding to interactions with possible functional contexts. The model gives rise to a sound and complete technique for checking of PCFv program equivalence, which we implement in a bounded bisimulation checking tool. We test our tool on known equivalences from the literature and new examples.

链接与引用

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

BibTeX
@inproceedings{KoutavasLT23,
  title = {Fully Abstract Normal Form Bisimulation for Call-by-Value PCF},
  author = {Vasileios Koutavas and Yu-Yang Lin and Nikos Tzevelekos},
  booktitle = {LICS},
  year = {2023},
  doi = {10.1109/lics56636.2023.10175778}
}