Synchronizing random automata on a 4-letter alphabet

Abstract

The paper deals with the synchronization of a random automaton that is sampled uniformly at random from the set of all automata with n states and m letters. We show that for m = 4, the probability that a random automaton is synchronizing is larger than a positive constant. Bibliography: 9 titles. © 2013 Springer Science+Business Media New York.