On the Finiteness of Infinite Regular Games

Starting with McNaughton’s pioneering technical report of 1965 in which he initiated the automata theoretic study of infinite games, we pursue his view that plays of an infinite game should terminate in finite time with the correct declaration of the winner. Such a reduction of regular infinite games to reachability games or safety games is well-known, for example, in the study of parity games. We focus on this reduction for Muller games (reporting on work of D. Neider, R. Rabinovich, M. Zimmermann, Aachen) which offers a so far unexploited player-dependent approach for solving Muller games, based on a new kind of memory structure and avoiding the step through parity games. We conclude with a more general discussion of determinacy proofs for infinite games, motivated by Büchi’s difficult last paper that has not received attention since it appeared in 1983.

Authors

• Wolfgang Thomas

Keywords

No keywords are indexed for this paper.