CS Seminars

The aim of this talk is to present an elementary survey on a problem concerning synchronizing automata. A synchronizing automaton is a model of computation, represented by a finite and oriented graph, that satisfies a property called `synchronization'. Synchronizing automata play a natural role in the solutionof several very interesting problems of mathematics and theoretical computer science. In the mid of 60s, Cerny proposed a conjecture on the length of a minimal synchronizing word for a synchronizing automaton in terms of the number of states. The validity of his conjecture is still open, although it has been verified in many special cases. Many of the nicest results concerning Cerny's conjecture are algebraic in nature and essentialy use the theory of matrix representations. In this talk, after a historical introduction of the problem, we describe some relevant results as well as the ideas underlying the techniques used to study the problem.