Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Проблема раскраски дорог. Часть 2
Синхронизируемые автоматы


Что: Лекция
Когда: Воскресенье, 14 ноября 2010, 15:35–17:10
Где: ПОМИ РАН
Слайды: synchronizingautomata_lecture_141110.pdf

Описание

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

Видео

Материалы