Determinacy of infinite games and automata on infinite words

Wenjuan Li

Beijing Institute of Mathematical Science and Applications

报告时间：16：00-17：00，2024-01-12（星期五）

报告地点: 沙河主E404

报告摘要：The Gale-Stewart game, a two-player turn-based infinite game with perfect information, has been intensively studied in descriptive set theory in the past several decades, mainly focusing on the determinacy issue. Automata theory also has a long history and a wide application in theoretical computer science. The topic of this talk lies in the interface of infinite games and automata theory. We will review several variant of finite automata on infinite words and the determinacy studies along this topic. Then we introduce our recent results on determinacy strength of infinite games in which the winning sets are recognized by probabilistic automata with various acceptance and probabilistic semantics. In terms of the foundational program reverse mathematics, the determinacy strength of such games is measured by the complexity of a winning strategy required by the determinacy.

报告人简介：Wenjuan Li is currently a postdoc at Beijing Institute of Mathematical Science and Applications. She got her Ph.D. from Tohoku University and then worked as postdoctoral research fellow at Nanyang Technological University. Her research interests include topics at the interface between mathematical logic and theoretical computer science.

邀请人： 杨义川

欢迎大家参加！