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

lmcs:703 - Logical Methods in Computer Science, September 1, 2011, Volume 7, Issue 3
Conway games, algebraically and coalgebraically

Authors: Honsell, Furio and Lenisa, Marina

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.


Source : oai:arXiv.org:1107.1351
DOI : 10.2168/LMCS-7(3:8)2011
Volume: Volume 7, Issue 3
Published on: September 1, 2011
Submitted on: March 30, 2011
Keywords: Computer Science - Logic in Computer Science,F.3.2, F.4.1


Share

Consultation statistics

This page has been seen 59 times.
This article's PDF has been downloaded 98 times.