Seminar on: "The road coloring theorem"
Dominique Perrin
UniversitÚ Paris-Est, LIGM CNRS, France

DEI - Seminar Room
January 20th, 2010

"The road coloring theorem is a result on finite automata obtained in 2008 by A. Trahtman. It solves a 30 years old conjecture of Adler and Weiss known as the road coloring problem. In this talk, I will explain the problem, its motivations in coding and in other fields of application and give an idea of the proof."