The Winning Ways of Concurrent Games
Authors:
- Pierre ClairambaultPCPierre Clairambault
- Julian GutierrezJGJulian Gutierrez
- Glynn WinskelGWGlynn Winskel
- 1 June 2012
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10436871,p. 235-244
Abstract
A bicategory of concurrent games, where nondeterministic strategies are formalized as certain maps of event structures, was introduced recently. This paper studies an extension of concurrent games by winning conditions, specifying players' objectives. The introduction of winning conditions raises the question of whether such games are determined, that is, if one of the players has a winning strategy. This paper gives a positive answer to this question when the games are well-founded and satisfy a structural property, race-freedom, which prevents one player from interfering with the moves available to the other. Uncovering the conditions under which concurrent games with winning conditions are determined opens up the possibility of further applications of concurrent games in areas such as logic and verification, where both winning conditions and determinacy are most needed. A concurrent-game semantics for predicate calculus is provided as an illustration.Keywords
This publication has 11 references indexed in Scilit:
- Concurrent Strategies2011
- Logic Games: From Tools to Models of Interaction2011
- Concurrent Logic Games on Partial OrdersLecture Notes in Computer Science, 2011
- Concurrent reachability gamesTheoretical Computer Science, 2007
- Asynchronous games 2: The true concurrency of innocenceTheoretical Computer Science, 2006
- Probabilistic event structures and domainsTheoretical Computer Science, 2006
- Concurrent games and full completeness2003
- Concurrent omega-regular games2002
- Game Semantics1997
- Games and full Completeness for multiplicative Linear Logic1992