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

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


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

Описание

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

Видео

Материалы