Russ Harmer - Probabilistic Game Semantics

A notion of probabilistic strategy is introduced to give a quantitative, rather than qualitative, account of nondeterminism. A factorization theorem shows that any probabilistic strategy can be decomposed as the interaction of a deterministic strategy with a fair coin. This allows us to extend previous full abstraction results for deterministic languages to probabilistic variants where "randomized" and "adaptive" algorithms can be programmed.

This is joint work with Vincent Danos.