Универсальные синхронизирующие и универсальные сжимающие слова
Диссертация
Автор: Петров, Илья Владимирович
Название: Универсальные синхронизирующие и универсальные сжимающие слова
Справка: Петров, Илья Владимирович. Универсальные синхронизирующие и универсальные сжимающие слова : диссертация кандидата физико-математических наук : 01.01.09 / Петров Илья Владимирович; [Место защиты: Ин-т математики и механики УрО РАН] - Екатеринбург, 2009 - Количество страниц: 95 с. ил. Екатеринбург, 2009 95 c. :
Объем: 95 стр.
Информация: Екатеринбург, 2009
Содержание:
11 Синхронизируемость и сжимаемость
12 Универсальные синхронизирующие слова
13 Универсальные сжимающие слова
14 Апробация результатов
2 Разрешимость задачи распознавания сжимающих слов
3 Алгоритм распознавания сжимающих слов
31 Предварительные сведения и определения
311 Фишки и дырки
312 Послойное представление
313 Строение слоя
314 Строение слоя п-собственного автомата
315 Метки состояний и роли букв
316 Основа
317 Операции по изменению основы
318 Вычисления по основе
32 Алгоритм
321 Общее описание алгоритма
322 Проверка слова на п-полноту
323 Генерация ролей букв
324 Распределение ролей и начало рекурсии
325 Шаг рекурсии (разбиение на подклассы)
326 Классы автоматов, не требующие разбиения
327 Корректность
33 Неизоморфность рассматриваемых автоматов
34 Время работы алгоритма
4 Алгоритмы поиска и построения синхронизирующих и сжимающих слов
41 Переборный алгоритм поиска кратчайших синхронизирующих слов
42 Поиск сжимающих слов
43 Распознаватель слов, синхронизирующих автомат
44 Алгоритм построения синхронизирующих слов через пересечение языков
45 Результаты
5 Зеркальный образ 2-синхронизирующих слов
6
Заключение
Введение:
Дефектом действия слова v на автомат srf назовем dfv(stf) = \Q\ — \S(Q,v)\.Рис. 1: Автомат Черни с 4 состояниями На рис. 1 представлен пример синхронизируемого автомата. Легко проверить, что любое состояние этого автомата словом ab3ab3a отображается в состояние 2, т.е. слово ab3ab3a является синхронизирующим словом для данного автомата. Отметим, что у любого синхронизируемого автомата существует бесконечно много синхронизирующих слов, так как если мы припишем к синхронизирующему автомат слову в начало и в конец любые слова, то полученное слово по-прежнему будет синхронизировать этот автомат.Оказывается, что слово ab3ab3a не только является синхронизирующим словом для автомата Черни с 4 состояниями, но еще и кратчайшим с данным свойством.Что же хорошего в синхронизирующем автомат слове и почему здесь уместно слово 'синхронизация' ? Для ответа представим, что мы имеем несколько одинаковых синхронизируемых автоматов, работающих независимо, и пусть каждый из этих автоматов находится в некотором состоянии, причем начальные состояния для разных автоматов могут различаться. Если мы ко всем этим автоматам одновременно применим синхронизирующее их слово, то все они окажутся в одном и том же состоянии — тем самым, дальнейшая работа этих автоматов под действием единого потока сигналов будет синхронизирована. Можно считать, что данное слово выполнило 'сброс' всех этих автоматов в 'начальное' состояние. Другим важным применением синхронизирующего автомат слова является ситуация, когда у нас имеется один синхронизируемый автомат, но мы не знаем, в каком состоянии он находится.Тогда применение синхронизирующего его слова переведет автомат в заранее известное нам состояние. Т. е. синхронизирующее автомат слово позволяет уменьшить неопределенность поведения автомата! Существует множество других применений, некоторые из них описаны в работах [23; 29].Одним из первых понятие синхронизируемое™ сформулировал Черни (Сегпу) в 1964 году, в работе [15]. Черни также высказал гипотезу: Гипотеза 1.1 ( С е т у , 1964). Любой синхронизируемый ДКА srf = (Q,E,<5) может быть синхронизирован словом длины не большей, чем (\Q\ — I ) 2 .С тех пор было много попыток доказать или опровергнуть эту так легко формулируемую гипотезу, но ни одна из них не увенчалась успехом. На данный момент гипотеза доказана для многочисленных классов автоматов (см. [5; 14; 19; 21; 34;38]), а в общем случае получена только кубическая верхняя оценка ' ' IQI (см. [1]). Сам же Черни в работе [15] построил бесконечную серию автоматов, кратчайшие синхронизирующие слова которых имеют длину (|<2| — I ) 2 , и доказал тем самым, что данную оценку нельзя понизить.После этого достаточно рассмотреть пары вида (р,р) и проверить, что из этого множества пар можно, идя по обратным ребрам автомата &/№, достичь все остальные пары. Это условие эквивалентно тому, что любую пару (г, s) состояний автомата я/ можно склеить, т. е. подходящим словом v ? Е* перевести состояния г и s в некоторое состояние р.А как найти кратчайшее синхронизирующее автомат srf = (Q, Е, S) слово? Для этого используем автомат на подмножествах ?Р(&/) = (2^, Е, А), где 2® обозначает множество всех подмножеств множества Q, а функция Д : 2*2 х Е —» 2® определена следующим образом: Л(М, а) = {5(q, a)\q в М} VM С Q Va 6 Е. Саломаа (Salomaa) [35] и Эпштейн [21] доказали, что задача, в которой для заданного автомата лг/ и заданного числа L требуется определить, имеет ли автомат я/ синхронизирующее слово длины L, является NP-полной.По-другому эту задачу можно сформулировать так: проверить, что кратчайшее синхронизирующее слово для автомата srf имеет длину, не превосходящую L. Самотий (Samotij) в работе [36] также показал, что задача проверки того, что кратчайшее слово, синхронизирующее автомат &/, имеет длину ровно L, является одновременно iVP-трудной и со- NP-трудной.Не каждый ДКА может быть синхронизирован, но для каждого ДКА srf = (Q, Е, 8) можно указать ранг автомата rk(#/) = mm{\S(Q, v)\ \ v е Е*}.Ранг показывает, какое минимальное количество состояний может получиться в образе множества Q под действием различных слов; так, для синхронизируемых автоматов ранг равен 1. Как для синхронизируемых автоматов, так и для несинхронизируемых автоматов можно говорить о сжимаемости.Возьмем произвольное натуральное число п. ДКА srf = (Q, Е, 6) называется п-сжимаемым, если найдется такое слово ш G S*, что \8(Q,w)\ п. Такое слово w называется п-сжимающим для автомата з/. Будем также говорить, что слово w сжимает данный автомат j / н а п состояний. Ясно, что для любого числа 0 < п < \Q\ — гк(&/) автомат srf является п-сжимаемым.В 1983 году Пэн (Pin) в работе [30] обобщил гипотезу Черни: Гипотеза 1.2 (Pin, 1983). Любой п-сжимаемый ДКА может быть сжат на п словом длины не большей, чем п 2 .Однако, Кари (Kari) в 2000 году опроверг эту гипотезу [24], построив автомат с 6-ю состояниями такой, что кратчайшее сжимающее этот автомат на 4 состояния слово имеет длину 17 = 4 2 + 1 . Других примеров, опровергающих данную гипотезу, пока не найдено.Синхронизируемости и ее обобщениям посвящено множество работ, в том числе недавние работы Павла Мартюгина [2-4; 26; 27].