Синхронизация слова
В информатике , точнее, в теории детерминированных конечных автоматов (ДКА), синхронизирующее слово или последовательность сброса — это слово во входном алфавите ДКА, которое переводит любое состояние ДКА в одно и то же состояние. [1] То есть, если ансамбль копий DFA запускается в разных состояниях и все копии обрабатывают синхронизирующее слово, все они окажутся в одном и том же состоянии. Не у каждого DFA есть синхронизирующее слово; например, DFA с двумя состояниями: одним для слов четной длины и одним для слов нечетной длины, никогда не может быть синхронизирован.
Существование
[ редактировать ]Учитывая DFA, проблема определения наличия в нем синхронизирующего слова может быть решена за полиномиальное время. [2] используя теорему Яна Черного. Простой подход рассматривает степенной набор состояний DFA и строит ориентированный граф, где узлы принадлежат степенному набору, а направленное ребро описывает действие функции перехода. Путь от узла всех состояний к одноэлементному состоянию показывает наличие синхронизирующего слова. Этот алгоритм является экспоненциальным по числу состояний. Однако полиномиальный алгоритм получается благодаря теореме Черны, которая использует подструктуру проблемы и показывает, что синхронизирующее слово существует тогда и только тогда, когда каждая пара состояний имеет синхронизирующее слово.
Длина
[ редактировать ]
Проблема оценки длины синхронизирующихся слов имеет долгую историю и была поставлена независимо несколькими авторами, но широко известна как гипотеза Черного . В 1969 году Ян Черны предположил, что ( n - 1) 2 является верхней границей длины кратчайшего синхронизирующего слова для любого полного DFA с n состояниями (DFA с полным графом переходов состояний ). [3] Если это правда, то это было бы сложно: в своей статье 1964 года Черны представил класс автоматов (индексированных по числу n ), для которых самые короткие слова сброса имеют такую длину. состояний [4] Наилучшая известная верхняя граница составляет 0,1654 n. 3 , далеко от нижней границы. [5] Для DFA с n -состояниями во входном алфавите из k- букв алгоритм Дэвида Эппштейна находит синхронизирующее слово длиной не более 11 n. 3 /48 + О ( н 2 ) и работает за временную сложность O ( n 3 + кн 2 ). Этот алгоритм не всегда находит кратчайшее возможное синхронизирующее слово для данного автомата; как также показывает Эппштейн, проблема поиска кратчайшего синхронизирующего слова является NP-полной . Однако для специального класса автоматов, в которых все переходы состояний сохраняют циклический порядок состояний, он описывает другой алгоритм со временем O( kn 2 ), который всегда находит самое короткое синхронизирующее слово, доказывает, что эти автоматы всегда имеют синхронизирующее слово длины не более ( n − 1) 2 (оценка, данная в гипотезе Черны) и демонстрирует примеры автоматов этой специальной формы, у которых самое короткое синхронизирующее слово имеет длину ровно ( n - 1). 2 . [2]
Дорожная раскраска
[ редактировать ]Задача раскраски дорог — это задача маркировки ребер регулярного ориентированного графа символами входного k -буквенного алфавита (где k — исходящая степень каждой вершины) для формирования синхронизируемого ДКА. выдвинули гипотезу В 1970 году Бенджамин Вайс и Рой Адлер , что любой сильно связный и апериодический регулярный орграф можно пометить таким образом; их гипотеза была доказана в 2007 году Авраамом Трахтманом . [6] [7]
Связано: полугруппы преобразований
[ редактировать ]Полугруппа преобразований является синхронизирующей , если она содержит элемент ранга 1, то есть элемент, образ которого имеет мощность 1. [8] DFA соответствует полугруппе преобразований с выделенным набором генераторов.
Ссылки
[ редактировать ]- ^ Авраам Трахтман: Синхронизация автоматов, алгоритмов, гипотеза Черни . По состоянию на 15 мая 2010 г.
- ^ Перейти обратно: а б Эппштейн, Дэвид (1990), «Последовательности сброса для монотонных автоматов» (PDF) , SIAM Journal on Computing , 19 (3): 500–510, doi : 10.1137/0219033 .
- ^ Волков, Михаил В. (2008), «Синхронизация автоматов и гипотеза Черного», Proc. 2-й международный Конф. Теория и приложения языка и автоматов (LATA 2008) , LNCS, vol. 5196, Springer-Verlag, стр. 11–27, номер документа : 10.1007/978-3-540-88282-4_4 ; см., в частности, стр. 19
- ^ Черны, Ян (1964), «Заметки об однородных экспериментах с конечными автоматами» (PDF) , Математико-физический журнал Словацкой академии наук , 14 : 208–216 (на словацком языке).
- ^ Шитов, Ярослав (2019), «Улучшение недавней верхней границы для синхронизации слов конечных автоматов» (PDF) , Журнал автоматов, языков и комбинаторики , 24 (2–4): 367–373, arXiv : 1901.06542 , MR 4023068
- ^ Адлер, РЛ; Вайс, Б. (1970), «Сходство автоморфизмов тора», Мемуары Американского математического общества , 98 .
- ^ Трахтман, А.Н. (2009), «Проблема раскраски дорог», Израильский математический журнал , 172 : 51–60, arXiv : 0709.0099 , doi : 10.1007/s11856-009-0062-5 , MR 2534238
- ^ Кэмерон, Питер (2013), Группы перестановок и полугруппы преобразований (PDF) .
Дальнейшее чтение
[ редактировать ]- Рысцов И.С. (2004), «Гипотеза Черного: ретроспектива и перспективы», Учеб. Воркш. Синхронизация автоматов, Турку (WSA 2004) .
- Юргенсен, Х. (2008), «Синхронизация», Information and Computation , 206 (9–10): 1033–1044, doi : 10.1016/j.ic.2008.03.005
- Волков, Михаил В. (2008), «Синхронизация автоматов и гипотеза Черного», Proc. 2-й международный Конф. Теория и приложения языка и автоматов (LATA 2008) (PDF) , LNCS, vol. 5196, Springer-Verlag, стр. 11–27.