Синхронизирующее слово

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

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

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

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

Длина

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

Проблема оценки длины синхронизирующих слов имеет долгую историю и была независимо поставлена ​​несколькими авторами, но она широко известна как гипотеза Черны . В 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 соответствует полугруппе преобразований с выделенным набором генераторов.

Ссылки

  1. ^ Авраам Трахтман: Синхронизирующие автоматы, алгоритмы, гипотеза Черни. Доступ 15 мая 2010 г.
  2. ^ ab Эппштейн, Дэвид (1990), «Сброс последовательностей для монотонных автоматов» (PDF) , SIAM Journal on Computing , 19 (3): 500–510 , doi :10.1137/0219033.
  3. ^ Волков, Михаил В. (2008), "Синхронизация автоматов и гипотеза Черны", Труды 2-й Международной конференции по теории и приложениям языков и автоматов (LATA 2008) , LNCS, т. 5196, Springer-Verlag, стр.  11–27 , doi :10.1007/978-3-540-88282-4_4, ISBN 978-3-540-88281-7; см. в частности стр. 19
  4. ^ Черный, Ян (1964), «Познамка к гомогенному эксперименту с конечными автоматами» ( PDF) , Математико-физический часопис Словенской академии Vied , 14 : 208–216(на словацком языке).
  5. ^ Шитов, Ярослав (2019), «Улучшение недавней верхней границы для синхронизации слов конечных автоматов» (PDF) , Журнал автоматов, языков и комбинаторики , 24 ( 2–4 ): 367–373 , arXiv : 1901.06542 , MR  4023068
  6. ^ Адлер, Р. Л.; Вайс, Б. (1970), «Подобие автоморфизмов тора», Мемуары Американского математического общества , 98.
  7. ^ Трахтман, AN (2009), «Проблема раскраски дорог», Israel Journal of Mathematics , 172 : 51–60 , arXiv : 0709.0099 , doi : 10.1007/s11856-009-0062-5 , MR  2534238
  8. ^ Кэмерон, Питер (2013), Группы перестановок и полугруппы преобразований (PDF).

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

  • Рысцов, И.Ч. (2004), "Гипотеза Черны: ретроспективы и перспективы", Труды конференции "Синхронизирующие автоматы", Турку (WSA 2004).
  • Юргенсен, Х. (2008), «Синхронизация», Информация и вычисления , 206 ( 9– 10): 1033– 1044, doi : 10.1016/j.ic.2008.03.005
  • Волков, Михаил В. (2008), «Синхронизация автоматов и гипотеза Черны», Труды 2-й Международной конференции по теории и приложениям языков и автоматов (LATA 2008) (PDF) , LNCS, т. 5196, Springer-Verlag, стр  . 11–27
Взято с "https://en.wikipedia.org/w/index.php?title=Synchronizing_word&oldid=1263768508"