The #268;erný Conjecture and Other Synchronization Problems
Ângela Cardoso · 2014
This thesis mainly considers three problems related to the Cerný Conjecture and, more generally, automata synchronization. First we study digraph synchronization. We present two classes of totally synchronizing digraphs: the class of monotonic digraphs and the class of generalized monotonic digraphs, which coincides with the classes of acyclic digraphs and aperiodic digraphs. For these classes, we provide tight upper bounds on the length of shortest universal synchronizing words. We also establish that, in order to find an upper bound on the length of shortest universal synchronizing words for all totally synchronizing digraphs, it is enough to do so for digraphs with a unique sink and totally synchronizing strongly connected digraphs. The second problem considered is related to the synchronization of strongly connected aperiodic automata. A family of such automata is presented. This family has the property that the level of weak monotonicity of its automata grows with the number of states. This undermines a possible method to improve the best known upper bound on the length of shortest synchronizing words for this class of automata, which consists of establishing a better bound for automata with low levels of weak monotonicity. Finally we devote our attention to the synchronization of subsets of states of synchronizing automata. We present a conjecture on the upper bound on the length of shortest synchronizing words for subsets of a given size. We reduce it to the class of strongly connected automata, by establishing it for automata with a unique sink. We prove our conjecture for a subclass of weakly oriented circular automata, which are a special case of strongly connected automata. We also obtain an upper bound for circular automata, although it is not as good as the conjectured one. We provide further evidence for our conjecture, by establishing it for all extreme and slowly synchronizing automata known. In particular for the Cerný automaton, that is also used to show that our proposed upper bound cannot be improved. We also prove Cerný’s Conjecture for weakly oriented automata, thus obtaining a generalization and a simplification of Eppstein’s solution for oriented automata.