Paper: Probabilistic Game Semantics (at LICS 2000)

Authors: Vincent Danos Russell Harmer

Abstract

A category of HO/N-style games and probabilistic strategies is developed where the possible choices of a strategy are quantified to give a measure of the likelihood of seeing a given play. A 2-sided die is shown to be universal in this category, in the sense that any strategy breaks down into a composition between some deterministic strategy and that die. The interpretative power of the category is then demonstrated by delineating a Cartesian closed subcategory, which provides a fully abstract model of a probabilistic extension of Idealized Algol.

BibTeX

  @InProceedings{DanosHarmer-ProbabilisticGameSe,
    author = 	 {Vincent Danos and Russell Harmer},
    title = 	 {Probabilistic Game Semantics},
    booktitle =  {Proceedings of the Fifteenth Annual IEEE Symposium on Logic in Computer Science (LICS 2000)},
    year =	 {2000},
    month =	 {June}, 
    pages =      {204--213},
    location =   {Santa Barbara, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }