Abstract:
In this paper we model infinite processes with finite configurations as infinite
games over finite graphs. We investigate those games, called update games, in
which each configuration occurs an infinite number of times during a two-person
play. We also present an efficient polynomial-time algorithm (and partial characterization)
for deciding if a graph is an update network.