Natalie Behague

Ryerson University

Synchronizing Times for k-sets in Automata

Combinatorics Seminar

20th April 2021, 4:00 pm – 5:00 pm
Virtual (online) Zoom seminar; a link will be sent to the Bristol Combinatorics Seminar mailing list, the week before the seminar.

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 probably the most famous open problem in automata theory. We consider the closely related question of determining the minimum length of a word that maps 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 0.5n^2 to 0.19n^2. I will discuss this result and some related results, including a generalisation of this approach leading to an improved bound on the length of a synchronizing word for 4 states and 5 states.

This is joint work with Robert Johnson.

Comments are closed.