Games and Strategies as Event Structures

Simon Castellan (1) , Pierre Clairambault (1, 2) , Silvain Rideau (3) , Glynn Winskel (4)

1 LIP - Laboratoire de l'Informatique du Parallélisme
2 PLUME - Preuves et Langages
3 Department of Mathematics [Berkeley]
4 Computer Laboratory [Cambridge]

In 2011, Rideau and Winskel introduced concurrent games and strategies as event structures, generalizing prior work on causal formulations of games. In this paper we give a detailed, self-contained and slightly-updated account of the results of Rideau and Winskel: a notion of pre-strategy based on event structures; a characterisation of those pre-strategies (deemed strategies) which are preserved by composition with a copycat strategy; and the construction of a bicategory of these strategies. Furthermore, we prove that the corresponding category has a compact closed structure, and hence forms the basis for the semantics of concurrent higher-order computation.

Domaines: Logique [math.LO]

Simon Castellan, Pierre Clairambault, Silvain Rideau, Glynn Winskel. Games and Strategies as Event Structures. Logical Methods in Computer Science, 2017, ⟨10.23638/LMCS-13(3:35)2017⟩. ⟨hal-01302713v3⟩