Введение к работе
Актуальность темы. Конечные автоматы нашли свое применение во множестве областей математики и лежат в основании теоретических компьютерных наук. На раннем этапе развития теории автоматов они служили прежде всего моделью дискретно работающего устройства. При таком подходе естественно возникает следующий вопрос: как вернуть контроль над устройством, если его текущее состояние неизвестно? Впервые эта проблема была рассмотрена Муром [11] в 1956 году. Автоматы, которые он изучал, в ответ на каждую входную букву печатали некоторый выходной символ, зависящий от состояния. Решенную Муром задачу можно сформулировать так: какие сигналы нужно подать на вход устройства, чтобы по полученным откликам можно было однозначно определить его текущее состояние? Для автоматов без выхода аналогичную проблему впервые рассмотрел Черни [6] в 1964 году. Он же ввел следующие понятия. Рассмотрим некоторый автомат «й/ со множеством состояний Q и функцией переходов 8. Автомат «й/ называется синхронизируемым, если найдется слово w, под действием которого все состояния переходят в одно: 8(q, w) = 8(q', w) для всех q, q' Є Q. Всякое такое слово w называется синхронизирующим для «г/. Таким образом, если исходное состояние автомата неизвестно, то после прочтения синхронизирующего слова его состояние будет однозначно определено. К примеру, автомат ^4 приведенный на рис. 1, синхронизируем, поскольку слово abbbabbba переводит все состояния в 1.
Синхронизируемые автоматы естественным образом возникают в ряде прикладных областей (тестирование систем и протоколов, кодирование информации, роботика) и в то же время неожиданным образом возникают в некоторых разделах фундаментальной математики (символическая динамика, теория подстановочных систем и др.). Основы теории синхронизируемых автоматов и ее разнообразные связи и приложения обсуждаются, например, в недавних обзорах [14,18].
Во многих приложениях важным фактором является длина синхронизирующего слова. Минимум длин синхронизирующих слов автомата «г/ называется его порогом синхронизации и обозначается rt(«2/). Условимся для краткости называть автомат с п состояниями п-автоматом. Черни [6] построил серию синхронизируемых гг-автоматов Чоп с порогом синхронизации (п— I)2. Немного позднее он предположил, что эта серия является экстремальной, т.е. порог синхронизации любого гг-автомата не
Рис. 1: Автомат ^4
превосходит (п—1)2. За этим предположением закрепилось имя гипотеза Черни.
п(7п2+6п-16)
48 '
Несмотря на простоту формулировки и усилия многочисленных исследователей, гипотеза Черни остается недоказанной и неопровергнутой уже около 50 лет. Более того, до сих пор нет верхней оценки порядка в(гг2) на порог синхронизации произвольного гг-автомата. На сегодняшний день лучшей верхней оценкой на порог синхронизации произволь-
полученная Трахтманом
ного гг-автомата является оценка
в [17], которая является незначительным улучшением оценки Пэна п ~п, полученной еще в 1983 году [12].
Исследованию синхронизируемых автоматов и их приложений посвящены сотни работ. Результаты в этом направлении докладываются на международных конференциях из ведущих серий: Developments in Language Theory (DLT), Conference on Implementation and Application of Automata (CIAA), Mathematical Foundations of Computer Science (MFCS), и др. Таким образом, есть все основания утверждать, что тема диссертации актуальна.
Основные задачи, решаемые в диссертации. Одно из затруднений, с которым приходится сталкиваться в теории синхронизируемых автоматов является дефицит примеров экстремальных автоматов, т. е. гг-автоматов с порогом синхронизации (п — I)2. Единственной известной
на сегодня бесконечной серией экстремальных автоматов остается серия, приведенная Черни в [6]. Кроме нее, известно лишь несколько спорадических примеров экстремальных автоматов, наибольшим из которых по числу состояний является 6-автомат, открытый Кари [9] в 2001 г. Полный список известных экстремальных автоматов см. в [18]. Более того, до сих пор далее медленно синхронизируемые автоматы, т.е. гг-автоматы с порогом синхронизации близким к (п — I)2, почти не встречались в литературе до наших исследований - кроме серии Черни, здесь молено назвать лишь две бесконечных серии автоматов из работы [2].
В условиях, когда число примеров крайне ограничено, трудно было подвергать проверке различные предположения и допущения, возникавшие при поисках подходов к гипотезе Черни. Именно поэтому история исследований в данной области богата «ложными следами» - вспомогательными гипотезами, которые сперва казались перспективными, но по прошествии некоторого времени опровергались*. Таким образом, оказывается актуальной задача построения новых серий медленно синхронизируемых автоматов.
Поскольку медленно синхронизируемые автоматы встречаются крайне редко, то с практической точки зрения представляют интерес свойства синхронизируемых случайных автоматов. Говорят, что буква а имеет ранг г в автомате «г/, если |#(Q,a)| = г. Ранг буквы а мы будем обозначать через rk(a). Например, в автомате Чо±, изображенном на рис. 1 буква а имеет ранг 3. Известно, см. [8], что математическое ожидание ранга буквы в случайном автомате равно ——-. Таким образом, почти все автоматы обладают буквой небольшого ранга. Естественно оценить влияние рангов букв на порог синхронизации в случайном автомате. Первые шаги в этом направлении были сделаны в [2]. Там были приведены примеры, показывающие что порог синхронизации гг-автомата с буквой ранга п — 2 может достигать значения (п — 1)(п — 2) при нечетном щ если лее п четно, то {п — 2)2 + 1. Если всякая буква автомата «г/ имеет ранг не более г, то мы будем называть «г/ автоматом ограниченного ранга г. Таким образом, с точки зрения изучения свойств синхронизируемых автоматов в среднем валено оценить порог синхронизации в классе автоматов ограниченного ранга.
Несмотря на то, что гипотеза Черни остается довольно неприступной в общем случае, она была подтверледена для многих специальных клас-
*Ряд таких «ложных следов» проанализирован в [3].
сов автоматов. Один из рассматривавшихся в литературе классов естественно определяется в терминах ориентированного графа (орграфа) автомата. Напомним, что его вершинами являются состояния автомата, и для всякого перехода из состояния р в q под действием некоторой буквы проведена дуга из р в q. Автомат называется эйлеровым, если его ориентированный граф является эйлеровым. Такие автоматы часто возникают в различных областях математики, например, эйлеровым автоматом является граф Кэли группы. В 2003 году Кари [10] показал, что порог синхронизации синхронизируемого эйлерового автомата не превосходит п2 — Зп -\- 3. Однако для порога синхронизации эйлеровых автоматов не было известно никакой нижней оценки того же порядка, что и верхняя оценка [10]. Возникает важная задача построения эйлеровых автоматов с квадратичным порогом синхронизации.
Одна из областей, в которых находят применение синхронизируемые автоматы - теория кодирования, см. [4]. Дадим несколько определений из этой области. Слово и Є Е+ является фактором слова w, если w может быть представлено как w = хиу для некоторых х,у Є Е*. Пусть S - конечное множество слов над алфавитом Е. Слово w Є Е* называется покрываемым относительно S, если w является фактором некоторого слова из S*, в противном случае w называется непокрываемым. Множество слов S является покрывающим, если всякое слово над алфавитом Е является покрываемым относительно S. В противном случае S - непо-крывающее множество. Понятие непокрывающих множеств возникло в связи с рядом задач в теории кодирования.
В [1] показано, что всякому множеству слов S можно поставить в соответствие автомат &(S) специального вида таким образом, что S является непокрывающим тогда и только тогда, когда &(S) является синхронизируемым. Более того, множества непокрываемых слов для S и синхронизирующих слов для &(S) совпадают. Отметим, что автомат &(S) может оказаться недетерминированным и тогда синхронизируе-мость нужно понимать в некотором обобщенном смысле.
Обозначим длину кратчайшего непокрывающего слова множества S через uwl(S'). Проблема поиска кратчайших непокрываваемых слов и анализа их длин была предложена Рестиво [13] в 1981 году. Рестиво выдвинул гипотезу о том, что непокрывающее множество S всегда обладает непокрываемым словом w длины не более 2к2, где к - это длина самого длинного слова в S. Это предположение мы будем называть гипотезой Рестиво. По сути, принимая во внимание взаимосвязь между синхро-
низируемыми автоматами и непокрывающими множествами, гипотеза Рестиво является аналогом гипотезы Черни в некотором специальном классе автоматов.
В случае, когда длина самого длинного слова из S не превосходит 12, гипотеза Рестиво была опровергнута в [7]. Пусть к > 6, положим Rk = Ek\ {ак~Щ U ЕЪак~4Е U ЕЪа U Ь4 U Jk, где Jk = ЦЇЇ^Е и аЩ-В [7] вычислено, что при 7 < к < 12 длина кратчайшего непокрываемого слова для Rk равна Зк2 — 9к +1. Однако вопрос о справедливости гипотезы Рестиво при к > 12 оставался открытым. Таким образом, естественно возникает задача построения контрпримеров к гипотезе Рестиво с любой длиной самого длинного слова.
Целью работы является решение всех поставленных выше задач. А именно, построить серии медленно синхронизируемых автоматов; представить серии эйлеровых автоматов с квадратичным порогом синхронизации; изучить порог синхронизации автоматов ограниченного ранга и построить медленно синхронизируемые автоматы ограниченного ранга; предъявить бесконечную серию контрпримеров к гипотезе Рестиво.
Научная новизна. Все результаты, за исключением двух результатов в главе 1, являются новыми. В двух исключительных случаях мы предлагаем новые, существенно более короткие доказательства известных результатов.
Теоретическая и практическая ценность. Диссертационная работа носит теоретический характер. Полученные результаты могут быть использованы в теории конечных автоматов, теории формальных языков и теории кодирования.
Апробация результатов работы. Основные результаты диссертации докладывались на международном симпозиуме по математическим основам компьютерных наук MFCS 2010 (Брно, Чехия, 2010), международной конференции по формальным языкам DLT 2011 (Милан, Италия, 2011), международном семинаре по проблемам достижимости RP 2011 (Генуя, Италия, 2011), международной конференции по реализации и применению автоматов CIAA 2012 (Порту, Португалия, 2012). Ссылки на результаты диссертации присутствуют в работах израильских, итальянских и российских математиков.
Публикации. Основные результаты диссертации опубликованы в [19-24]. Все эти работы опубликованы в ведущих изданиях, входящих в список ВАК. В работах [19,20] постановка задачи и подход принадлежит М.В. Волкову. Реализация экспериментов и доказательства принадлежат диссертанту. Одна из приведенных серий в этих работах была ранее получена Д.С. Ананичевым. В работе [21] постановка задачи, общая схема исследования и некоторые идеи доказательств принадлежат Е.В. При-бавкиной. Реализация вычислительных экспериментов и доказательства основных утверждений принадлежат диссертанту. Все работы прошли рецензирование. Все работы, кроме [19,24], имели трех рецензентов.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав и списка литературы. Объем диссертации составляет 91 страницу. Библиографический список содержит 60 наименований.
