В информатике , точнее, в теории детерминированных конечных автоматов (DFA), синхронизирующее слово или последовательность сброса — это слово во входном алфавите DFA, которое переводит любое состояние DFA в одно и то же состояние. [1] То есть, если ансамбль копий DFA запускается в разных состояниях, и все копии обрабатывают синхронизирующее слово, все они окажутся в одном и том же состоянии. Не каждый DFA имеет синхронизирующее слово; например, DFA с двумя состояниями, одним для слов четной длины и одним для слов нечетной длины, никогда не может быть синхронизирован.
При наличии DFA, задача определения, имеет ли он синхронизирующее слово, может быть решена за полиномиальное время [2] с использованием теоремы Яна Черны. Простой подход рассматривает множество состояний DFA и строит направленный граф, где узлы принадлежат множеству состояний, а направленное ребро описывает действие функции перехода. Путь от узла всех состояний до состояния-одиночки показывает существование синхронизирующего слова. Этот алгоритм экспоненциален по числу состояний. Однако полиномиальный алгоритм получается из-за теоремы Черны, которая использует подструктуру задачи и показывает, что синхронизирующее слово существует тогда и только тогда, когда каждая пара состояний имеет синхронизирующее слово.
Проблема оценки длины синхронизирующих слов имеет долгую историю и была независимо поставлена несколькими авторами, но она широко известна как гипотеза Черны . В 1969 году Ян Черны предположил, что ( n − 1) 2 является верхней границей для длины кратчайшего синхронизирующего слова для любого n -состоянного полного DFA (DFA с полным графом переходов состояний ). [3] Если это правда, то это было бы тесно: в своей статье 1964 года Черны представил класс автоматов (индексированных по числу n состояний), для которых кратчайшие слова сброса имеют эту длину. [4] Лучшая известная верхняя граница составляет 0,1654 n 3 , что далеко от нижней границы. [5] Для n -состояний DFA над k -буквенным входным алфавитом алгоритм Дэвида Эппштейна находит синхронизирующее слово длины не более 11 n 3 /48 + O ( n 2 ), и работает со сложностью времени O ( n 3 + kn 2 ). Этот алгоритм не всегда находит кратчайшее возможное синхронизирующее слово для заданного автомата; как также показывает Эппштейн, задача нахождения кратчайшего синхронизирующего слова является NP-полной . Однако для специального класса автоматов, в которых все переходы состояний сохраняют циклический порядок состояний, он описывает другой алгоритм со временем O( kn 2 ), который всегда находит кратчайшее синхронизирующее слово, доказывает, что эти автоматы всегда имеют синхронизирующее слово длины не более ( n − 1) 2 (граница, указанная в гипотезе Черны), и демонстрирует примеры автоматов с этой специальной формой, кратчайшее синхронизирующее слово которых имеет длину ровно ( n − 1) 2 . [2]
Задача раскраски дорог — это задача маркировки рёбер правильного ориентированного графа символами k -буквенного входного алфавита (где k — исходящая степень каждой вершины) для формирования синхронизируемого DFA. В 1970 году Бенджамин Вайс и Рой Адлер предположили , что любой сильно связный и апериодический правильный орграф может быть помечен таким образом; их гипотеза была доказана в 2007 году Авраамом Трахтманом . [6] [7]
Полугруппа преобразований является синхронизирующей, если она содержит элемент ранга 1, то есть элемент, образ которого имеет мощность 1. [8] DFA соответствует полугруппе преобразований с выделенным набором генераторов.