Uniform winning strategies for the synchronization games on subclasses of finite automata

Abstract

The pseudovariety $\mathbf{DS}$ consists of all finite monoids whose regular $D$-classes form subsemigroups. We exhibit a uniform winning strategy for Synchronizer in the synchronization game on every synchronizing automaton whose transition monoid lies in $\mathbf{DS}$, and we prove that $\mathbf{DS}$ is the largest pseudovariety with this property.

18 pages, 5 figures. Expanded and essentially modified version of the authors' paper in the Proceedings of 14th International Workshop on Non-Classical Models of Automata and Applications, NCMA. EPTCS 407, 77-85 (2024)