WikiDer > Синхронизация слова

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

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

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

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

Длина

Вопрос, Web Fundamentals.svgНерешенная проблема в математике:
Если в DFA есть синхронизирующее слово, должно ли оно иметь длину не более ?
(больше нерешенных задач по математике)

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

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