2026/01/26 by Anton E. Lipin, Mikhail V. Volkov · 1 voice
Computer Science · #cs.FL #cs.GT
paper · pdf · doi:10.48550/arxiv.2601.18362
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≥ 1, 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.