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

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

В лекциях будет рассказано о связях теории синхронизируемых автоматов с различными смежными областями (теория кодов, символическая динамика и др.), изложено решение проблемы раскраски дорог и дан обзор новейших продвижений по гипотезе Черни.

Предварительные знания по теории автоматов, теории кодов и символической динамике не предполагаются. Для понимания некоторых результатов полезно знакомство с основами теории сложности вычислений.