Equivalences and Congruences on Infinite Conway Games∗

Furio Honsell; Marina Lenisa; Rekha Redamalla

RAIRO - Theoretical Informatics and Applications (2012)

  • Volume: 46, Issue: 2, page 231-259
  • ISSN: 0988-3754

Abstract

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

How to cite

top

Honsell, Furio, Lenisa, Marina, and Redamalla, Rekha. "Equivalences and Congruences on Infinite Conway Games∗." RAIRO - Theoretical Informatics and Applications 46.2 (2012): 231-259. <http://eudml.org/doc/276373>.

@article{Honsell2012,
abstract = {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.},
author = {Honsell, Furio, Lenisa, Marina, Redamalla, Rekha},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Conway games; non-wellfounded games; coalgebras; equivalences; Joyal’s category; Joyal's category},
language = {eng},
month = {4},
number = {2},
pages = {231-259},
publisher = {EDP Sciences},
title = {Equivalences and Congruences on Infinite Conway Games∗},
url = {http://eudml.org/doc/276373},
volume = {46},
year = {2012},
}

TY - JOUR
AU - Honsell, Furio
AU - Lenisa, Marina
AU - Redamalla, Rekha
TI - Equivalences and Congruences on Infinite Conway Games∗
JO - RAIRO - Theoretical Informatics and Applications
DA - 2012/4//
PB - EDP Sciences
VL - 46
IS - 2
SP - 231
EP - 259
AB - 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.
LA - eng
KW - Conway games; non-wellfounded games; coalgebras; equivalences; Joyal’s category; Joyal's category
UR - http://eudml.org/doc/276373
ER -

References

top
  1. S. Abramsky and R. Jagadesaan, Games and full completeness for multiplicative linear logic, J. Symb. Log.59 (1994) 543–574.  
  2. P. Aczel, Non-wellfounded sets. CSLI Lecture Notes14 (1988).  
  3. J. Barwise and L. Moss, Vicious Circles. CSLI Lecture Notes60 (1996).  
  4. E. Berlekamp, J. Conway and R. Guy, Winning Ways. Academic Press (1982).  
  5. J.H. Conway, On Numbers and Games, 2nd edition (1st edition by Academic Press (1976). AK Peters Ltd. (2001).  
  6. M. Forti and F. Honsell, Set-theory with free construction principles. Ann. Scuola Norm. Sup. Pisa Cl. Sci.10 (1983) 493–522.  
  7. O. Grumberg, M. Lange, M. Leucker and S. Shoham, When not losing is better than winning : abstraction and refinement for the full μ-calculus. Inform. Comput.205 (2007) 1130–1148.  
  8. P.M. Grundy, Mathematics and games. Eureka2 (1939) 6–8.  
  9. F. Honsell and M. Lenisa, Conway Games, algebraically and coalgebraically. Log. Meth. Comput. Sci.7 (2011).  
  10. M. Hyland and A. Schalk, Games on Graphs and Sequentially Realizable Functionals, in Proc. of LICS’02. IEEE Computer Science Press (2002) 257–264.  
  11. C. Kissig and Y. Venema, Complementation of Coalgebra Automata, in Proc. of CALCO’09. Lect. Notes Comput. Sci.5728 (2009) 81–96.  
  12. B. Jacobs and J.J.M.M. Rutten, A Tutorial on (Co)algebras and (Co)induction. Bull. of EATCS62 (1997) 222–259.  
  13. A. Joyal, Remarques sur la théorie des jeux à deux personnes. Gaz. Sci. Math. du Québec1 (1977).  
  14. P.L. Curien, H. Herbelin, J.L. Krivine and P.A. Melliès, Categorical semantics of linear logic, in Interactive models of computation and program behaviour. Panoramas et Synthèses, Société Mathématique de France 27 (2009).  
  15. P.A. Melliès, N. Tabareau and C. Tasson, An explicit formula for the free exponential modality of linear logic, in Proc. of ICALP’09. Lect. Notes Comput. Sci.555 (2009).  
  16. M. Pauly, From Programs to Games : Invariance and Safety for Bisimulation, in Proc. of CSL’09 (2009) 485–496.  
  17. L. Santocanale, Free μ-lattices. J. Pure Appl. Algebra168 (2002) 227–264.  
  18. R. Sprague, Über mathematische kampfspiele. Tohoku Math. J.41 (1935) 438–444.  
  19. W. Thomas, Infinite games and verification, in Proc. of CAV’02. Lect. Notes Comput. Sci.2404 (2002) 58–64.  
  20. J. van Benthem, Extensive games as process models, J. Log. Lang. Inf.11 (2002). 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.