City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Synchronizing Automata


A deterministic finite automaton is said to be synchronizing if there exists a word w such that every path labeled w in the automaton ends at the same state. This notion naturally arises in the problem of restoring control over a discrete system whose current state is not known. The notion has turned out to be mathematically interesting and has led to many problems that are easy to formulate but quite hard to solve. Among such problems we may distinguish the Road Coloring Problem (which has been recently solved by Trahtman) and the Cerny Conjecture that remains open for 46 years.

In the lectures we shall explain various connections of the theory of synchronizing automata with other areas (coding theory, symbolic dynamics etc). We also shall present a solution to the Road Coloring Problem and survey the most recent advances towards a proof of the Cerny Conjecture.

No background in automata theory, coding theory or symbolic dynamics is assumed. An acquaintance with some rudiments of complexity theory may be useful for understanding of certain results.

Course Offerings

Semester Branch
autumn 2010 Saint Petersburg