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.
This is a joint work with Anton Lipin and the paper can be found at https://arxiv.org/abs/2601.18362.