Synchronizing automata, primitive matrix sets, and the Černý conjecture

In this master's thesis we study the relationship between primitive matrix sets and synchronizing automata. We define the k-rendezvous time (k-RT) of a primitive matrix set as the length of the shortest product of matrices from the set that has a column or a row of weight at least k, and we show that for any fixed k the k-RT of a primitive matrix set of square matrices of size n that contain no zero rows or columns is upper bounded by a linear function of n for large n. We also prove a cubic bound in n on the n-RT of such a matrix set. We analyze next an algorithm presented recently for randomly generating slowly synchronizing automata, and derive results that suggest certain limitations of this method. Finally we study certain heuristic methods for approximating the k-RT, the exponent of primitive matrix sets, and the reset threshold of synchronizing automata, and we present our own new heuristic that seems to work quite well, at least in the cases tested.