Thomas Ehrhard

Probabilistic coherence spaces are fully abstract for probabilistic PCF

Jeudi 6 mars 2014 à 10H30

(joint work with Michele Pagani and Christine Tasson)

Abstract: 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.