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

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

Существование [ править ]

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

Длина [ править ]

Нерешенная задача по математике :

Если в DFA со состояниями есть синхронизирующее слово, должно ли оно иметь не более одной длины ?

(больше нерешенных задач по математике)

Проблема оценки длины синхронизирующих слов имеет долгую историю и была независимо поставлена ​​несколькими авторами, но широко известна как гипотеза Черного . В 1969 году Ян Черны предположил, что ( n  - 1) 2 является верхней границей длины кратчайшего синхронизирующего слова для любого полного DFA с n состояниями (DFA с полным графом переходов состояний ). [3] Если это так, то это было бы сложно: в своей статье 1964 года Черный показал класс автоматов (индексированных числом состояний n ), для которых кратчайшие слова сброса имеют эту длину. [4] Наилучшая известная верхняя граница (n 3 - n) / 6, далеко от нижней границы. [5] Для п -state ДКИ над к -Письму входного алфавита, алгоритм с помощью David Eppstein находит слово синхронизации длины не более 11 л 3 /48 +  О ( п 2 ), и работает в временной сложности O ( п 3 + кн 2 ). Этот алгоритм не всегда находит кратчайшее возможное слово синхронизации для данного автомата; как показывает также Эппштейн, задача поиска кратчайшего синхронизирующего слова является NP-полной.. Однако для специального класса автоматов, в котором все переходы состояний сохраняют циклический порядок состояний, он описывает другой алгоритм со временем O ( kn 2 ), который всегда находит кратчайшее синхронизирующее слово, доказывает, что эти автоматы всегда имеют синхронизирующее слово длины не более ( n  - 1) 2 (оценка, данная в гипотезе Черни), и демонстрирует примеры автоматов с этой специальной формой, у которых кратчайшее синхронизирующее слово имеет длину точно ( n  - 1) 2 . [2]

Раскраска дороги [ править ]

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

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

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

Ссылки [ править ]

  1. ^ Авраам Трахтман: Синхронизация автоматов, алгоритмов, Гипотеза Черни . По состоянию на 15 мая 2010 г.
  2. ^ Б Эпштайна, Дэвид (1990), "Сброс последовательности для монотонных автоматов" (PDF) , SIAM журнал по вычислениям , 19 (3): 500-510, DOI : 10,1137 / 0219033 .
  3. ^ Волков, Михаил В. (2008), "Синхронизация автоматов и гипотеза Черного", Proc. 2nd Int'l. Конф. Язык и теория автоматов и приложения (LATA 2008) , LNCS, 5196 , Springer-Verlag, стр. 11–27, DOI : 10.1007 / 978-3-540-88282-4_4; см., в частности, стр. 19
  4. ^ Черны Ján (1964), "Poznámka к homogénnym experimentom s konečnými automatmi" (PDF) , Matematicko-fyzikálny časopis Slovenskej Akademie соперничали , 14 : 208-216 (на словацком).
  5. ^ Пин, Ж.-Э. (1983), «О двух комбинаторных проблемах, возникающих из теории автоматов» (PDF) , Комбинаторная математика (Marseille-Luminy, 1981) , North-Holland Math. Stud,. 75 , Амстердам.: Северная Голландия, С. 535-548, DOI : 10.1016 / S0304-0208 (08) 73432-7 , MR 0841339  ; см. примечание в конце, касающееся улучшения, сделанного Франклом П. (1982), «Экстремальная задача для двух семейств множеств», European Journal of Combinatorics , 3 (2): 125–127, doi : 10.1016 / S0195-6698 (82 ) 80025-5 , Руководство по ремонту 0670845 
  6. ^ Адлер, RL; Вайс Б. (1970), "Подобие автоморфизмов тора", Мемуары Американского математического общества , 98.
  7. ^ Трахтман, AN (2009), "Дорога окраски проблема", Израиль Журнал математики , 172 : 51-60, Arxiv : 0709,0099 , DOI : 10.1007 / s11856-009-0062-5 , MR 2534238 
  8. ^ Кэмерон, Питер (2013), Группы перестановок и полугруппы преобразований (PDF) .

Дальнейшее чтение [ править ]

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