Combinatorics Seminar 2017

Speaker: Mikhail V. Volkov (Волков Михаил Владимирович), Ural Federal University

Date: Sun, May 07, 2017

Time: 14:00 - 15:00

Venue: Middle Meeting Room

Title: Expansion method


We describe the "bottom-up" method for constructing reset words in synchronizing automata as opposed to the "top-down" approach used in Lectures 1 and 2. The method is illustrated by Kari's elegant solution to the Černý problem for Eulerian automata. We discuss further applications of the method as well as its limitations.

Slides: View slides