RAIRO-Theor. Inf. Appl.
Volume 46, Number 2, April-June 201212th Italian Conference on Theoretical Computer Science (ICTCS)
|Page(s)||231 - 259|
|Published online||02 March 2012|
Equivalences and Congruences on Infinite Conway Games∗
Dipartimento di Matematica e Informatica, Università di
Udine, Viale delle Scienze
2 Birla Science Centre, Adarsh Nagar, 500063 Hyderabad, India
Accepted: 17 January 2012
Taking the view that infinite plays are draws, we study Conway non-terminating games and non-losing strategies. These admit a sharp coalgebraic presentation, where non-terminating games are seen as a final coalgebra and game contructors, such as disjunctive sum, as final morphisms. We have shown, in a previous paper, that Conway’s theory of terminating games can be rephrased naturally in terms of game (pre)congruences. Namely, various conceptually independent notions of equivalence can be defined and shown to coincide on Conway’s terminating games. These are the equivalence induced by the ordering on surreal numbers, the contextual equivalence determined by observing what player has a winning strategy, Joyal’s categorical equivalence, and, for impartial games, the denotational equivalence induced by Grundy semantics. In this paper, we discuss generalizations of such equivalences to non-terminating games and non-losing strategies. The scenario is even more rich and intriguing in this case. In particular, we investigate efficient characterizations of the contextual equivalence, and we introduce a category of fair strategies and a category of fair pairs of strategies, both generalizing Joyal’s category of Conway games and winning strategies. Interestingly, the category of fair pairs captures the equivalence defined by Berlekamp, Conway, Guy on loopy games.
Mathematics Subject Classification: 68Q55 / 91A40 / 91A80
Key words: Conway games / non-wellfounded games / coalgebras / equivalences / Joyal’s category
© EDP Sciences 2012
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.