Probabilistic game semantics
- 7 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 204-213
- https://doi.org/10.1109/lics.2000.855770
Abstract
A category of HO/N-style games and probabilistic strategies is developed where the possible choices of a strategy are quantified so as 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.Keywords
This publication has 16 references indexed in Scilit:
- A fully abstract game semantics for finite nondeterminismPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Non-deterministic games and program analysis: An application to securityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- A probabilistic powerdomain of evaluationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Games and full abstraction for FPCPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- On Full Abstraction for PCF: I, II, and IIIInformation and Computation, 2000
- BireflectivityTheoretical Computer Science, 1999
- Full abstraction for Idealized Algol with passive expressionsTheoretical Computer Science, 1999
- Domains for Computation in Mathematics, Physics and Exact Real ArithmeticBulletin of Symbolic Logic, 1997
- Full abstraction for functional languages with controlPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1997
- PCF extended with real numbersTheoretical Computer Science, 1996