Benedikt Brütsch ; Wolfgang Thomas - Solving Infinite Games in the Baire Space

fi:8743 - Fundamenta Informaticae, October 21, 2022, Volume 186, Issues 1-4: Trakhtenbrot's centenary
Solving Infinite Games in the Baire SpaceArticle

Authors: Benedikt Brütsch ; Wolfgang Thomas

    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üchi-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.

    Volume: Volume 186, Issues 1-4: Trakhtenbrot's centenary
    Published on: October 21, 2022
    Accepted on: June 21, 2022
    Submitted on: November 23, 2021
    Keywords: Computer Science - Computer Science and Game Theory,Computer Science - Logic in Computer Science

    Consultation statistics

    This page has been seen 109 times.
    This article's PDF has been downloaded 93 times.