Degrees of Lookahead in Regular Infinite Games
by
Michael Holtmann, Lukasz Kaiser, and Wolfgang Thomas

Abstract. We study variants of regular infinite games where the strict
alternation of moves between the two players is subject to
modifications. The second player may postpone a move for a finite
number of steps, or, in other words, exploit in his strategy some
lookahead on the moves of the opponent. This captures situations in
distributed systems, e.g. when buffers are present in communication or
when signal transmission between components is deferred. We
distinguish strategies with different degrees of lookahead, among them
being the continuous and the bounded lookahead strategies. In the
first case the lookahead is of finite possibly unbounded size, whereas
in the second case it is of bounded size. We show that for regular
infinite games the solvability by continuous strategies is decidable,
and that a continuous strategy can always be reduced to one of bounded
lookahead. Moreover, this lookahead is at most doubly exponential in
the size of the parity automaton recognizing the winning condition. We
also show that the result fails for non-regular games where the
winning condition is given by a context-free omega-language.