Degrees of Lookahead in Regular Infinite Games

Speaker

Michael Holtmann
Title Degrees of Lookahead in Regular Infinite Games
When 05.11.2008
Where Lecture Room Informatik 11
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. In one case the lookahead is of finite possibly unbounded size, whereas in another case it is of bounded size.

We show that for regular infinite games the solvability by strategies of the first kind is decidable, and that such a 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.
Slides download