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

William John Gowers, James Laird

Research output: Chapter or section in a book/report/conference proceedingChapter in a published conference proceeding

1 Citation (SciVal)
59 Downloads (Pure)


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 languageEnglish
Title of host publicationProceedings of 7th Conference on Algebra and Coalgebra in Computer Science
EditorsFilippo Bonchi, Barbara König
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication statusPublished - 31 May 2017
Event7th Conference on Algebra and Coalgebra in Computer Science - Faculty of Mathematics and Physics, University of Ljubljana, Ljubljana, Slovenia
Duration: 12 Jun 201716 Jun 2017

Publication series

PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISSN (Electronic)1868-8969


Conference7th Conference on Algebra and Coalgebra in Computer Science
Abbreviated titleCALCO 2017

Bibliographical note

Accepted for publication in the proceedings of CALCO 2017, published in the Dagstuhl LIPIcs series. 15pp + 2pp bibliography + 12 pp Appendix (the appendix is not part of the conference version)


  • cs.LO
  • F.3.2


Dive into the research topics of 'Sequoidal Categories and Transfinite Games: A Coalgebraic Approach to Stateful Objects in Game Semantics'. Together they form a unique fingerprint.

Cite this