Synchronizing automata of bounded rank

Abstract

We reduce the problem of synchronization of an n-state automaton with letters of rank at most r < n to the problem of synchronization of an r-state automaton with constraints given by a regular language. Using this technique we construct a series of synchronizing n-state automata in which every letter has rank r < n and whose reset threshold is at least r 2-r-1 Moreover, if r > n/2, such automata are strongly connected. © 2012 Springer-Verlag.