Equivalences and Congruences on Infinite Conway Games
| Autor: | Furio Honsell, Rekha Redamalla, Marina Lenisa |
|---|---|
| Rok vydání: | 2012 |
| Předmět: |
Discrete mathematics
Computer Science::Computer Science and Game Theory Semantics (computer science) General Mathematics Coalgebra Conway games ComputingMilieux_PERSONALCOMPUTING Joyal's category Congruence relation Coalgebras Equivalences Non-wellfounded games Surreal number Computer Science Applications Algebra Morphism Disjunctive sum Mathematics::Category Theory Equivalence (measure theory) Categorical variable Software Mathematics |
| Zdroj: | RAIRO - Theoretical Informatics and Applications. 46:231-259 |
| ISSN: | 1290-385X 0988-3754 |
| DOI: | 10.1051/ita/2012001 |
| Popis: | 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 . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|