Синхронизация слова - Synchronizing word

О синхронизации слов в теории синхронизированных кодов см. Самосинхронизирующийся код § Синхронизирующее слово.

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

В Информатика, точнее, в теории детерминированные конечные автоматы (DFA), а синхронизирующее слово или же последовательность сброса - это слово во входном алфавите DFA, которое отправляет любое состояние DFA в одно и то же состояние.^[1] То есть, если ансамбль копий DFA запущен в разных состояниях, и все копии обрабатывают синхронизирующее слово с одинаковой скоростью, все они в конечном итоге достигнут того же состояния, что и друг друга, в то же время, что и друг друга. Не в каждом DFA есть синхронизирующее слово; например, DFA с двумя состояниями, одно для слов четной длины и одно для слов нечетной длины, никогда не может быть синхронизировано.

Существование

Учитывая DFA, проблема определения, есть ли у него синхронизирующее слово, может быть решена в полиномиальное время^[2] используя теорему Яна Черни. При простом подходе рассматривается набор степеней состояний DFA и строится ориентированный граф, в котором узлы принадлежат множеству степеней, а направленное ребро описывает действие функции перехода. Путь от узла всех состояний к одноэлементному состоянию показывает наличие синхронизирующего слова. Этот алгоритм экспоненциальный в количестве состояний. Однако в результате получается полиномиальный алгоритм из-за теоремы Черни, которая использует подструктуру задачи и показывает, что синхронизирующее слово существует тогда и только тогда, когда каждая пара состояний имеет синхронизирующее слово.

Длина

Нерешенная проблема в математике: Если в DFA есть синхронизирующее слово, должно ли оно иметь длину не более ${displaystyle (n-1)^{2}}$? (больше нерешенных задач по математике)

Проблема оценки длины синхронизирующих слов имеет долгую историю и была независимо поставлена ​​несколькими авторами, но обычно она известна как Гипотеза Черного. В 1964 г. Ян Черный предположил, что (п − 1)² это верхняя граница на длину кратчайшего синхронизирующего слова для любого п-состояние завершенный DFA (DFA с полным граф перехода состояний ).^{[1][3][неудачная проверка – см. обсуждение]} Если это так, то это будет сложно: в своей статье 1964 года Черный показал класс автоматов (индексированный числом п состояний), для которых кратчайшие слова сброса имеют эту длину. Наилучшая известная верхняя граница (п ³ - n) / 6, далеко от нижней границы.^[4] За п-государственные DFA над k-буквенный ввод алфавита, алгоритм по Дэвид Эппштейн находит синхронизирующее слово длиной не более 11п³/48 + О (п²) и вбегает временная сложность О (п³+кн²). Этот алгоритм не всегда находит кратчайшее возможное слово синхронизации для данного автомата; как показывает также Эппштейн, проблема поиска кратчайшего синхронизирующего слова состоит в НП-полный. Однако для специального класса автоматов, в которых все переходы состояний сохраняют циклический порядок состояний он описывает другой алгоритм со временем O (кн²), который всегда находит кратчайшее синхронизирующее слово, доказывает, что эти автоматы всегда имеют синхронизирующее слово длины не более (п − 1)² (оценка, данная в гипотезе Черни), и демонстрирует примеры автоматов с этой специальной формой, у которых кратчайшее синхронизирующее слово имеет длину точно (п − 1)².^[2]

Раскраска дороги

В проблема окраски дороги проблема разметки краев обычный ориентированный граф с символами k-буквенный ввод алфавита (где k это превосходить каждой вершины), чтобы сформировать синхронизируемый DFA. Это было предположено в 1970 году Бенджамином Вайсом и Рой Адлер что любой сильно связанный и апериодический таким образом можно пометить обычный орграф; их гипотеза была подтверждена в 2007 г. Авраам Трахтман.^[5][6]

Связанный: Трансформационные полугруппы

А полугруппа преобразований является синхронизация если он содержит элемент ранга 1, то есть элемент, изображение которого имеет мощность 1.^[7] DFA соответствует полугруппе преобразований с выделенной образующей.

Рекомендации

1. Авраам Трахтман: Синхронизация автоматов, алгоритмов, гипотеза Черни. По состоянию на 15 мая 2010 г.
2. Эппштейн, Дэвид (1990), «Последовательности сброса для монотонных автоматов» (PDF), SIAM Журнал по вычислениям, 19 (3): 500–510, Дои:10.1137/0219033.
3. Черный, J. (1964), "Poznámka k homogénnym Experimentom s konečnými automatmi" (PDF), Matematicko-fyzikálny časopis Slovenskej Akadémie Vied, 14: 208–216 (на словацком).
4. https://arxiv.org/abs/1104.2409v7 Трахтман в какой-то момент подумал, что доказал лучшую оценку n (7п²+ 6n − 16) / 48, но это доказательство оказалось неверным, и статья была отозвана, оставив наиболее известную оценку (n ^ 3 - n) / 6
5. Адлер, Р. Л .; Вайс Б. (1970), "Подобие автоморфизмов тора", Мемуары Американского математического общества, 98.
6. Трахтман, А. Н. (2009), "Проблема раскраски дороги", Израильский математический журнал, 172: 51–60, arXiv:0709.0099, Дои:10.1007 / s11856-009-0062-5, МИСТЕР  2534238
7. Кэмерон, Питер (2013), Группы перестановок и полугруппы преобразований (PDF).

дальнейшее чтение

• Рыцов И.С. (2004), «Гипотеза Черного: ретроспективы и перспективы», Proc. Worksh. Синхронизация автоматов, Турку (WSA 2004).
• Юргенсен, Х. (2008). «Синхронизация». Информация и вычисления. 206 (9–10): 1033–1044. Дои:10.1016 / j.ic.2008.03.005.
• Волков, Михаил В. (2008), "Синхронизация автоматов и гипотеза Черного", Proc. 2nd Int'l. Конф. Язык и теория автоматов и приложения (LATA 2008) (PDF), LNCS, 5196, Springer-Verlag, стр. 11–27.