Abstract:
Games played on finite graphs were first introduced by McNaughton in [6]. McNaughton,
using the ideas of the paper by Gurevich and Harrington [3], proved that winners in his
games have finite state winning strategies. Later based on McNaughton games, Nerode,
Remmel and Yakhnis in a series of papers (see [7] and [8], for example) developed foundations
of concurrent programming by identifying distributed concurrent programs with
finite state strategies and studied complexities of finding winners in McNaughton games.
Dinneen and Khoussainov use McNaughton games for modelling and studying structural
and complexity-theoretical properties of update networks (see [1]). Later in [2] Bodlaender,
Dinneen and Khoussainov generalize the study of update networks by introducing the
concept of relaxed update network. They proved that it is possible to detect in polynomial
time whether or not a given game represents a relaxed update network. In this paper we
continue the line of research of the above mentioned work and begin with the following
definition from [6]. -- from Introduction