# Sequoidal Categories and Transfinite Games: A Coalgebraic Approach to Stateful Objects in Game Semantics

William John Gowers, James Laird

Research output: Chapter in Book/Report/Conference proceedingConference contribution

### Abstract

The non-commutative sequoid operator $\oslash$ on games was introduced to capture algebraically the presence of state in history-sensitive strategies in game semantics, by imposing a causality relation on the tensor product of games. Coalgebras for the functor $A \oslash \_$ - i.e. morphisms from $S$ to $A \oslash S$ - may be viewed as state transformers: if $A \oslash \_$ has a final coalgebra, $!A$, then the anamorphism of such a state transformer encapsulates its explicit state, so that it is shared only between successive invocations. We study the conditions under which a final coalgebra $!A$ for $A \oslash \_$ is the carrier of a cofree commutative comonoid on $A$. That is, it is a model of the exponential of linear logic in which we can construct imperative objects such as reference cells coalgebraically, in a game semantics setting. We show that if the tensor decomposes into the sequoid, the final coalgebra $!A$ may be endowed with the structure of the cofree commutative comonoid if there is a natural isomorphism from $!(A \times B)$ to $!A \otimes !B$. This condition is always satisfied if $!A$ is the bifree algebra for $A \oslash \_$, but in general it is necessary to impose it, as we establish by giving an example of a sequoidally decomposable category of games in which plays will be allowed to have transfinite length. In this category, the final coalgebra for the functor $A \oslash \_$ is not the cofree commutative comonoid over A: we illustrate this by explicitly contrasting the final sequence for the functor $A \oslash \_$ with the chain of symmetric tensor powers used in the construction of the cofree commutative comonoid as a limit by Melli\'es, Tabareau and Tasson.
Original language English Proceedings of 7th Conference on Algebra and Coalgebra in Computer Science Filippo Bonchi, Barbara König Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing Published - 31 May 2017 7th Conference on Algebra and Coalgebra in Computer Science - Faculty of Mathematics and Physics, University of Ljubljana, Ljubljana, SloveniaDuration: 12 Jun 2017 → 16 Jun 2017

### Publication series

Name LIPIcs Schloss Dagstuhl - Leibniz-Zentrum für Informatik 1868-8969

### Conference

Conference 7th Conference on Algebra and Coalgebra in Computer Science CALCO 2017 Slovenia Ljubljana 12/06/17 → 16/06/17

• cs.LO
• F.3.2

• ## Cite this

Gowers, W. J., & Laird, J. (2017). Sequoidal Categories and Transfinite Games: A Coalgebraic Approach to Stateful Objects in Game Semantics. In F. Bonchi, & B. König (Eds.), Proceedings of 7th Conference on Algebra and Coalgebra in Computer Science (LIPIcs). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing.