Abstract
Determinacy of infinite twoplayer games is a topic of descriptive set theory that has triggered intensive research in theoretical computer science since 1957 when A. Church formulated his "synthesis problem" (regarding the construction of circuits with infinite behavior from logical specifications). In the first part of the lecture we review the fascinating development of the algorithmic theory of infinite games that was started by Church's problem, that enriched automata theory and related fields, and that led to interesting applications in verification and program synthesis. In the second part we turn to the question how to lift this theory from the case of the Cantor space (where a play is a sequence of bits) to the case of the Baire space (where a play is a sequence of natural numbers). While this step does not involve difficulties in classical descriptive set theory, the algorithmic approach raises nontrivial questions since it requires to consider automata that work over infinite alphabets. We present recent results (joint work with B. Brütsch) that provide a solution of Church's synthesis problem in this context, and we point to numerous questions that are still open.
BibTeX  Entry
@InProceedings{thomas:LIPIcs:2017:7708,
author = {Wolfgang Thomas},
title = {{Determinacy of Infinite Games: Perspectives of the Algorithmic Approach (Invited Talk)}},
booktitle = {26th EACSL Annual Conference on Computer Science Logic (CSL 2017)},
pages = {6:16:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770453},
ISSN = {18688969},
year = {2017},
volume = {82},
editor = {Valentin Goranko and Mads Dam},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7708},
URN = {urn:nbn:de:0030drops77083},
doi = {10.4230/LIPIcs.CSL.2017.6},
annote = {Keywords: Infinite games, descriptive set theory, automata theory, transducers, automatic synthesis}
}
Keywords: 

Infinite games, descriptive set theory, automata theory, transducers, automatic synthesis 
Seminar: 

26th EACSL Annual Conference on Computer Science Logic (CSL 2017) 
Issue Date: 

2017 
Date of publication: 

14.08.2017 