Abstract:
McNaughton in his known paper [7], motivated by the work of Gurevich and
Harrington [4], introduced a class of games played on finite graphs. In his paper
McNaughton proves that winners in his games have winning strategies that can
be implemented by finite state automata. McNaughton games have attracted
attention of many experts in the area, partly because the games have close
relationship with automata theory, the study of reactive systems, and logic (see,
for instance, [12] and [11]). McNaughton games can also be used to develop
game-theoretical approach for many important concepts in computer science
such as models for concurrency, communication networks, and update networks,
and provide natural examples of computational problems. For example, Nerode,
Remmel and Yakhnis in a series of papers (e.g., [8], [9]) developed foundations of
concurrent programming in which finite state strategies of McNaughton games
are identified with distributed concurrent programs. -- from Introduction
