Probabilistic game semantics
- 1 July 2002
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computational Logic
- Vol. 3 (3), 359-382
- https://doi.org/10.1145/507382.507385
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 two-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 that provides a fully abstract model of a probabilistic extension of Idealized Algol.Keywords
This publication has 6 references indexed in Scilit:
- On Full Abstraction for PCF: I, II, and IIIInformation and Computation, 2000
- 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
- PCF extended with real numbersTheoretical Computer Science, 1996
- Rational probability measuresTheoretical Computer Science, 1989
- Cpo's of measures for nondeterminismTheoretical Computer Science, 1980