Locally strongly transitive automata and the Hybrid Cerny-Road coloring problem

Abstract. An independent system of words for a finite automaton is a set of k words taking any state s into k distinct states which do not depend on s. We present some recent application of independent sets to the synchronization problem and to synchronizing colorings of aperiodic graphs. In particular, we prove that if an aperiodic, strongly connected digraph of costant outdegree with n vertices has an Hamiltonian path, then it admits a synchronizing coloring with a reset word of length 2(n− 2)(n − 1) + 1. An important concept in Computer Science is that of synchronizing automa-ton. A deterministic automaton is called synchronizing if there exists an input-sequence, called synchronizing or reset word, such that the state attained by the automaton, when this sequence is read, does not depend on the initial state of the automaton itself. Two fundamental problems which have been intensively in-vestigated in the last decades are based upon this concept: the Černy ́ conjecture and the Road coloring problem