Furio Honsell ; Marina Lenisa - Conway games, algebraically and coalgebraically

lmcs:703 - Logical Methods in Computer Science, September 1, 2011, Volume 7, Issue 3 - https://doi.org/10.2168/LMCS-7(3:8)2011
Conway games, algebraically and coalgebraicallyArticle

Authors: Furio Honsell ; Marina Lenisa

    Using coalgebraic methods, we extend Conway's theory of games to possibly non-terminating, i.e. non-wellfounded games (hypergames). We take the view that a play which goes on forever is a draw, and hence rather than focussing on winning strategies, we focus on non-losing strategies. Hypergames are a fruitful metaphor for non-terminating processes, Conway's sum being similar to shuffling. We develop a theory of hypergames, which extends in a non-trivial way Conway's theory; in particular, we generalize Conway's results on game determinacy and characterization of strategies. Hypergames have a rather interesting theory, already in the case of impartial hypergames, for which we give a compositional semantics, in terms of a generalized Grundy-Sprague function and a system of generalized Nim games. Equivalences and congruences on games and hypergames are discussed. We indicate a number of intriguing directions for future work. We briefly compare hypergames with other notions of games used in computer science.


    Volume: Volume 7, Issue 3
    Published on: September 1, 2011
    Imported on: March 30, 2011
    Keywords: Computer Science - Logic in Computer Science,F.3.2, F.4.1

    5 Documents citing this article

    Consultation statistics

    This page has been seen 990 times.
    This article's PDF has been downloaded 522 times.