Solving Infinite Games in the Baire Space
share
Infinite games (in the form of Gale-Stewart games) are studied where a play is a sequence of natural numbers chosen by two players in alternation, the winning condition being a subset of the Baire space ω^ω. We consider such games defined by a natural kind of parity automata over the alphabet ℕ, called ℕ-MSO-automata, where transitions are specified by monadic second-order formulas over the successor structure of the natural numbers. It is shown that the classical Büchi-Landweber Theorem (for finite-state games in the Cantor space 2^ω) holds again for the present games: A game defined by a parity ℕ-MSO-automaton is determined, the winner can be decided, and a winning strategy of the winner can be constructed that is realizable by an ℕ-MSO-transducer.
READ FULL TEXT