Синхронизирующее слово

В информатике, точнее, в теории детерминированных конечных автоматов (ДКА), синхронизирующее слово (или сжимающая последовательность) во входном алфавите автомата отображает все его состояния в одно и то же состояние. То есть, если слово стартует на ансамбле всех состояний автомата, проходя все ориентированные дуги с одинаковой скоростью, все пути завершатся одновременно в одном и том же состоянии. Не у каждого ДКА есть синхронизирующее слово, например, ДКА с двумя состояниями и циклами длины два никогда не могут быть синхронизированы.

Этот рисунок представляет ДКА с восемью состояниями и двумя входными символами, красным и синим. Слово синий-красный-красный-синий-красный-красный-синий-красный-красный является синхронизирующим словом, которое отправляет все состояния в желтое состояние; слово синий-синий-красный-синий-синий-красный-синий-синий-красный является другим синхронизирующим словом, которое отправляет все состояния в зеленое состояние.

Проблема оценки длины синхронизирующего слова имеет долгую историю и была поставлена независимо несколькими авторами, но широко известной стала как гипотеза Черны. В 1964 году Ян Черны предположил, что (N — 1)² является точной верхней границей для длины кратчайшего синхронизирующего слова для любого ДКА с N состояниями и К разноцветными исходящими ребрами из каждой вершины (ДКА с полным графом переходов). Черны еще в 1964 году нашел класс автоматов (с числом N состояний для любого натурального N), у которых кратчайшее синхронизирующее слово имеет эту длину. Лучшая известная верхняя граница для этой длины на сегодня равна (N³ — N) / 6 и далека от нижней границы.

Для ДКА с N состояниями над алфавитом из K символов, алгоритм Дэвида Эпстайна находит синхронизирующее слово за время O(N³ + n²k) и с объемом памяти O(n²). В этой статье также доказана NP—полнота нахождения синхронизирующего слова минимальной длины.

Проблема раскраски дорог является проблемой раскраски ребер регулярного ориентированного графа символами (цветами) входного алфавита из K символов, (где К является также полустепенью исхода каждой вершины) с целью формирования синхронизируемого ДКА. Бенджамин Вайсс и Рой Адлер в 1970 году высказали гипотезу, что у любого сильно связного орграфа с постоянной полустепенью исхода каждой вершины и равным единице наибольшим общим делителем длин всех циклов существует синхронизирующая раскраска. Их гипотеза была доказана в 2007 году Абрамом Трахтманом.