Variants of the road coloring problem
Résumé
The road coloring problem has been solved by Trahtman recently. In this talk, I will discuss its relation with other problems concerning synchronized automata, in particular in connexion with the commutative equivalence. I will present a proof, due to M.P. Schutzenberger, of the fact that any finite maximal prefix code is commutatively equivalent to a synchronized one.