Синхронизируемые автоматы

Описание

Детерминированный конечный автомат называется синхронизируемым, если существует такое слово w, что любой путь в автомате, вдоль которого читается w, заканчивается в одном и том же состоянии. Это понятие, естественно возникающее в задаче восстановления контроля над дискретной системой, текущее состояние которой неизвестно, оказалось математически весьма содержательным и породило много просто формулируемых, но оказавшихся весьма трудными задач. Среди таких проблем особо выделяются проблема раскраски дорог, совсем недавно решенная А.Н. Трахтманом, и гипотеза Черни, остающаяся недоказанной уже 46 лет.