Probabilistic coherence spaces are fully abstract for probabilistic PCF
Probabilistic coherence spaces are fully abstract for probabilistic PCF
复制标题
概率相干空间对于概率 PCF 来说是完全抽象的
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Michele Pagani
中科院分区：
文献类型：
--
作者：
T. Ehrhard;C. Tasson;Michele Pagani
概率相干空间（PCoh）产生高阶概率计算的语义，将类型解释为凸集，将程序解释为幂级数。我们证明了Pcoh中的解释相等性刻画了PCF中具有随机原语的程序的操作不变性。这是概率PCF语义完全抽象的第一个结果。关键因素依赖于幂级数的规律性。沿着定理，我们设计了一个加权交集型分配系统，给出了PCoh的逻辑表示。
Probabilistic coherence spaces (PCoh) yield a semantics of higher-order probabilistic computation, interpreting types as convex sets and programs as power series. We prove that the equality of interpretations in Pcoh characterizes the operational indistinguishability of programs in PCF with a random primitive. This is the first result of full abstraction for a semantics of probabilistic PCF. The key ingredient relies on the regularity of power series. Along the way to the theorem, we design a weighted intersection type assignment system giving a logical presentation of PCoh.