10.46298/fi-2022-8743
https://fi.episciences.org/8743
Brütsch, Benedikt
Benedikt
Brütsch
Thomas, Wolfgang
Wolfgang
Thomas
Solving Infinite Games in the Baire Space
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
episciences.org
Computer Science - Computer Science and Game Theory
Computer Science - Logic in Computer Science
arXiv.org - Non-exclusive license to distribute
2022-06-21
2022-10-21
2022-10-21
eng
journal article
arXiv:2111.10881
10.48550/arXiv.2111.10881
1875-8681
https://fi.episciences.org/8743/pdf
VoR
application/pdf
Fundamenta Informaticae
Volume 186, Issues 1-4: Trakhtenbrot's centenary
Researchers
Students