Abstract:
In this paper we consider a class of infinite one player games played on finite
graphs. Our main questions are the following: given a game, how efficient
is it to find whether or not the player wins the game? If the player wins
the game, then how much memory is needed to win the game? For a given
number n, how does the underlying graph look like if the player has a winning
strategy of memory size n?