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

Проблема раскраски дорог. Часть 1
Synchronizing Automata

What: Lecture
When: Sunday, 14 November 2010, 13:00–14:35
Where: ПОМИ РАН
Slides: synchronizingautomata_lecture_141110.pdf

Description

Сведение задачи о длине кратчайшего синхронизирующего слова для автоматов с данным числом состояний к случаю сильно связных автоматов. Примитивность орграфов сильно связных синхронизируемых автоматов. Проблема раскраски дорог. Отношение стабильности. Теорема Трахтмана о раскраске дорог. Сложностные аспекты проблемы раскраски дорог.

Video