Seminar Details
2013-09-17 (14.00) : Synchronizing automata
At Euler building
Organized by Mathematical Engineering
Speaker :
Vladimir Gusev (Ural Federal University)
Abstract :
An automaton is called synchronizing if there is a word w and a state q such that w applied to an arbitrary state p leads to q. This
notion naturally appears in different areas of computer science, usually, as a model of error resistant system. In my talk I will tell about
applications of synchronizing automata and about two famous problems related to synchronizing automata: road coloring problem and Cerny conjecture.
Former was open for 37 years and was recently settled. Latter is widely open for already 48 years.