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.
翻译:无限游戏( 以 Gale- Stewart 游戏的形式) 由两个玩家在交替时选择自然数字序列, 获胜条件为 Baire 空间的子集 $\ omega ⁇ omega$。 我们考虑以字母 $\ mathbb{N} 美元( 称为$\ mathbb{N}$- MSO- automata ) 的自然等同自动等式定义的游戏, 称为 $\ mathbb{N} $- MSO- automata, 该游戏的过渡由月经二阶公式指定, 而不是自然数字的后续结构。 我们显示经典 B\ “ uchi- Land Weber Theorem ” (用于坎托尔空间的限定状态游戏 $@ ⁇ omega$) 的优胜条件再次为当前游戏保留 : 由确定性等同 $\\ mathb{ N} $- MSO- momatomatton 定义的游戏, 胜者可以进行计算, 和 $\\\\\\\ b{ MSO - modudududustrationer 实现获胜者获胜战略的优胜者。