paperbot · PL 论文追踪

全部论文 待读 收藏

P2 The concurrent game semantics of Probabilistic PCF

概率PCF的并发博弈语义
LICS Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science2018匹配度 2/10 · 论文属于概率程序语言的形式语义与博弈语义,与用户关注的静态分析、LLM/Agent 结合、浮点程序分析等方向无直接关联;仅因涉及概率编程而与贝叶斯程序分析有非常边缘的理论联系。引用 30 inbox
Simon Castellan, Pierre Clairambault, Hugo Paquet, Glynn Winskel
crossref: 2026-09-12

AI 速览

一句话:提出概率PCF的并发博弈语义,证明其内涵完全抽象并给出有限可定义性。

本文为概率PCF(PPCF)提出一种新的博弈语义。作者在Castellan等人最近引入的带对称性的thin concurrent games上加入概率,得到支持PPCF的顺序与并行两种解释的并发博弈模型。通过利用概率并发策略的因果结构,论文证明PPCF程序所得策略的交互无死锁,并构造一个保持解释的函子,从该模型映射到Ehrhard等人已证明完全抽象的概率关系模型,由此推出该模型是内涵完全抽象的。作者还定义了概率innocence,并证明有限可定义性,从而给出完全抽象性的第二个独立证明。

问题
如何为概率PCF建立同时容纳顺序与并行解释的语义模型,并证明其完全抽象性。
方法
在thin concurrent games与对称性基础上引入概率,构造并发博弈模型,并利用概率并发策略的因果结构定义概率innocence。
评估
通过证明策略交互无死锁、构造到概率关系模型的保持解释函子,以及证明有限可定义性,给出内涵完全抽象与第二个完全抽象证明。
原文摘要(Abstract)

We define a new games model of Probabilistic PCF (PPCF) by enriching thin concurrent games with symmetry, recently introduced by Castellan et al, with probability. This model supports two interpretations of PPCF, one sequential and one parallel. We make the case for this model by exploiting the causal structure of probabilistic concurrent strategies. First, we show that the strategies obtained from PPCF programs have a deadlock-free interaction, and therefore deduce that there is an interpretation-preserving functor from our games to the probabilistic relational model recently proved fully abstract by Ehrhard et al. It follows that our model is intensionally fully abstract. Finally, we propose a definition of probabilistic innocence and prove a finite definability result, leading to a second (independent) proof of full abstraction.

链接与引用

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

BibTeX
@inproceedings{paperbot4343,
  title = {The concurrent game semantics of Probabilistic PCF},
  author = {Simon Castellan and Pierre Clairambault and Hugo Paquet and Glynn Winskel},
  booktitle = {LICS},
  year = {2018},
  doi = {10.1145/3209108.3209187}
}