Finding the Shortest Synchronizing Sequence

ABSTRACT
Cerný conjecture states that, for every automaton A with N > 1 states, the shortest reset word has the length (N-1)2 (Cerný ,1964). We designed an algorithm to compute a shortest reset word for automata. The main idea is the use of a breadth-first- search and inverse-breadth-first-search to scan and compare the subsets. In our experiments, we used automata with up to N = 200 states and P = 2 input letters. We computed a shortest reset word for automata N = 200 states with P = 2 input letters under a minute on average.