Adversarial Synchronization

报告题目：Adversarial Synchronization

报告人： Mikhail Volkov 教授 俄罗斯乌拉尔联邦大学教授

邀请人：杨丹丹 教授

报告时间：2026年3月2日（周一）15：00-17：00

报告地点：南校区会议中心112会议室

报告人简介：Mikhail Volkov教授于1994年在圣彼得堡大学获得俄罗斯国家博士学位（Doctor of Science degree in Mathematics)，他长期担任乌拉尔国立大学代数与理论计算机科学研究所所长，2016年首位当选俄罗斯教育部首届俄罗斯联邦数学讲席教授，2017年当选芬兰科学与文公司外籍院士，2019年被德国研究基金遴选为Mercator教授。他是几个著名的理论计算机年度会议永久执行委员，是Semigroup Forum执行主编和多份国际杂志编委。他是自动机理论，字上组合学，半群与形式语言等重要研究方向上的研究领袖，谷歌学术引用近2500次，相关工作多次入选理论计算机顶级会议，并曾两次在CIAA会议获得最佳论文奖。

报告摘要：We study a variant of the synchronization game on finite deterministic automata. In this game, Alice chooses one input letter of an automaton. A on each of her moves while Bob may respond with an arbitrary finite word over the input alphabet of A; Alice wins if the word obtained by interleaving her letters with Bob's responses resets A. We prove that if Alice has a winning strategy in this game on A, then A admits a reset word whose length is strictly smaller than the number of states of A. In contrast, for any k, we exhibit automata with shortest reset-word length quadratic in the number of states, on which Alice nevertheless wins a version of the game in which Bob's responses are restricted to arbitrary words of length at most k.

We provide polynomial-time algorithms for deciding the winner in various synchronization games, and we analyze the relationships between variants of synchronization games on fixed-size automata.