演讲人：Bakh Khoussainov [电子科技大学]
时间：10:00-11:00, Dec 11, 2025 (Thu)
地点：RM 1-222, FIT Building
内容：
Regular games form a well-established class of games for analysis and synthesis of reactive systems. They include coloured Muller, McNaughton, Muller, Rabin, and Streett games. These games are played on directed graphs G where Player 0 and Player 1 play by generating an infinite path ρ through the graph. The winner is determined by specifications put on the set X of vertices in ρ that occur infinitely often. These games are determined, enabling the partitioning of G into two sets W0 and W1 of winning positions for Player 0 and Player 1, respectively. Numerous algorithms exist that decide instances of regular games, e.g., Muller games, by computing W0 and W1. In this paper we describe general principles for designing uniform algorithms that decide all regular games. For this we utilize various recursive and dynamic programming algorithms that leverage standard notions such as subgames and traps. Importantly, we show that our techniques improve or match the performances of existing algorithms for many instances of regular games.
个人简介:
Bakh Khoussainov is the director of Algorithms & Logic Lab at the University of Eletronic Science and Technology of China. His research interests range from Mathematical logic to theoretical computer science. He is an academician of Europea Academia, Fellow of The Royal Society of New Zealand, a national talent of China (长江学者讲席学者), Winner of Nerode prize of the European Association for TCS and reciever of STOC 2017 best paper award. He supervised over 20 PhD students, and published over 160 research papers. He has held professorship and visiting professorship positions at Cornell University, Heidelberg University, National University of Singapore, Novosibirsk University, Kyoto University, etc.
