2512.11007

Total: 1

#1 Uniform winning strategies for the synchronization games on subclasses of finite automata [PDF] [Copy] [Kimi] [REL]

Authors: Henning Fernau, Carolina Haase, Stefan Hoffmann, Mikhail Volkov

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.

Subjects: Formal Languages and Automata Theory , Computer Science and Game Theory

Publish: 2025-12-11 08:37:02 UTC