{"docId":9970,"paperId":8743,"url":"https:\/\/fi.episciences.org\/8743","doi":"","journalName":"Fundamenta Informaticae","issn":"0169-2968","eissn":"1875-8681","volume":[{"vid":599,"name":"Volume 186, Issues 1-4: Trakhtenbrot's centenary"}],"section":[],"repositoryName":"arXiv","repositoryIdentifier":"2111.10881","repositoryVersion":4,"repositoryLink":"https:\/\/arxiv.org\/abs\/2111.10881v4","dateSubmitted":"2021-11-23 10:39:27","dateAccepted":"2022-06-21 22:00:41","datePublished":"2022-10-21 22:01:52","titles":["Solving Infinite Games in the Baire Space"],"authors":["Br\u00fctsch, Benedikt","Thomas, Wolfgang"],"abstracts":["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"],"keywords":["Computer Science - Computer Science and Game Theory","Computer Science - Logic in Computer Science"]}