Natalie Behague - “Synchronizing Times for k-sets in Automata“ | MoCCA’20

The talk “Synchronizing Times for k-sets in Automata“ by Natalie Behague on the Moscow Conference on Combinatorics and Applications at MIPT. Annotation: An automaton consists of a finite set of states and a collection of functions from the set of states to itself. An automaton is synchronizing if there is a word (that is, a sequence of functions) that maps all states onto the same state. Cerny’s conjecture on the length of the shortest such word is one of the most famous open problems in automata theory. We consider the closely related question of determining the minimum length of a word that maps some k states onto a single state. For synchronizing automata, we have improved the upper bound on the minimum length of a word that sends some triple to a single state from ^2 to ^2. I will discuss this result and some related results, including a generalisation of this approach that leads to an improved bound on the length of a synchronizing word for 4 states and 5 states.