Skip to Main content Skip to Navigation
Conference papers

Variants of the road coloring problem

Abstract : 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.
Document type :
Conference papers
Complete list of metadatas

https://hal-upec-upem.archives-ouvertes.fr/hal-00620455
Contributor : Dominique Perrin <>
Submitted on : Wednesday, September 7, 2011 - 5:12:16 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:05 PM

Identifiers

  • HAL Id : hal-00620455, version 1

Citation

Dominique Perrin. Variants of the road coloring problem. Journées Montoises d'Informatique Théorique, 2008, France. ⟨hal-00620455⟩

Share

Metrics

Record views

86