文章基本信息

标题：Determinacy of Infinite Games: Perspectives of the Algorithmic Approach (Invited Talk)
本地全文：下载
作者：Wolfgang Thomas
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：82
页码：6:1-6:1
DOI：10.4230/LIPIcs.CSL.2017.6
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Determinacy of infinite two-player 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 non-trivial 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.
关键词：Infinite games; descriptive set theory; automata theory; transducers; automatic synthesis