Solving Infinite Games in the Baire Space
Fundamenta Informaticae, vol. 186, pp. 63–88
Abstract
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 $\omega^\omega$. We consider such games defined by a natural kind of parity automata over the alphabet $\mathbb{N}$, called $\mathbb{N}$-MSO-automata, where transitions are specified by monadic second-order formulas over the successor structure of the natural numbers. We show that the classical B\"uchi-Landweber Theorem (for finite-state games in the Cantor space $2^\omega$) holds again for the present games: A game defined by a deterministic parity $\mathbb{N}$-MSO-automaton is determined, the winner can be computed, and an $\mathbb{N}$-MSO-transducer realizing a winning strategy for the winner can be constructed. Comment: Updated header on title page. 26 pages, 1 figure
Authors 2
-
Benedikt Brütsch corresponding Aachen Chair of Computer Science 7 (Logic and Theory of Discrete Systems)
Affiliation as printed
Chair of Computer Science 7, RWTH Aachen University, Germany. bruetsch@automata.rwth-aachen.de, thomas@cs.rwth-aachen.de
-
Affiliation as printed
Chair of Computer Science 7, RWTH Aachen University, Germany. bruetsch@automata.rwth-aachen.de, thomas@cs.rwth-aachen.de
Cited by 1 stored of 1
1 result
No patents citing this paper on Lens.org (checked 2026-10-06).