Michele Pagani (LIPN, Univ. Paris 13), Probabilistic Coherence Spaces are Fully Abstract for Probabilistic PCF



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 and introduces, in denotational semantics, techniques coming from Calculus.

Along the way to the theorem, we design a weighted intersection type assignment system giving a logical presentation of PCOH.

Pièces jointes