Seminar: Characterizing Automata which Admit a Synchronizing Word

Speaker: Alexander Clow, Simon Fraser University

Title: Characterizing Automata which Admit a Synchronizing Word

Abstract: Have you ever had to turn your computer off then on again to fix a bug? Perhaps you have had to share computing time on a cluster, only to encounter some issue as a result of someone else's request of the system? If so, then you might be interested to know that the solution to both of these issues are instances of the (deterministic finite) automata (DFA) synchronization  problem. This problem states, given a DFA does there exist a word $\sigma$,  such that applying $\sigma$ to the DFA synchronizes, or if you prefer ``resets", your machine to a prescribed state no matter its current state.

By considering this problem graph theocratically, we provide a novel characterization for which DFAs admit a synchronizing word. Using this characterization we show a natural class of automata that model movement in Euclidean space admit short synchronizing words, thereby satisfying a conjecture of \v{C}ern\'y from 1969. By applying a modification of our methods, we also show that given certain technical assumptions, two DFAs $G$ and $H$ can be simultaneously synchronized to prescribed states $u$ and $v$, by a single word $\sigma$.

Joint work with Peter Bradshaw (University of Illinois Urbana-Champaign) and Ladislav Stacho (Simon Fraser University).