BIMSA >
BIMSA-Tsinghua Quantum Symmetry Seminar
Determinacy of infinite games and automata on infinite words
Determinacy of infinite games and automata on infinite words
Organizers
Speaker
Time
Wednesday, September 21, 2022 1:30 PM - 3:00 PM
Venue
1131
Online
Zoom 537 192 5549
(BIMSA)
Abstract
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. My research interests lie in the interface of infinite games and automata theory. In the first part of this talk, I will introduce the Gale-Stewart game, some celebrated results on determinacy of infinite games, and then move on to a journey to several variant of finite automata on infinite words. In the second half, I will introduce my joint work with Prof. K. Tanaka. We investigate the determinacy strength of infinite games, in which the winning sets are recognized by nondeterministic pushdown automata with various acceptance, e.g., safety, reachability and co-Buchi conditions. 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. For instance, we show that the determinacy of games recognized by pushdown automata with a reachability condition is equivalent to weak Konig lemma, stating that every infinite binary tree has an infinite path.