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

33 Downloads (Pure)

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 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

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

Conference

Conference7th Conference on Algebra and Coalgebra in Computer Science
Abbreviated titleCALCO 2017
CountrySlovenia
CityLjubljana
Period12/06/1716/06/17

Keywords

  • cs.LO
  • F.3.2

Fingerprint 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

    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.