Экстремальные конструкции в теории синхронизируемых автоматов тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Гусев, Владимир Валерьевич

• Гусев, Владимир Валерьевич
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Гусев, Владимир Валерьевич

Содержание

Введение

0.1 Синхронизируемые автоматы и гипотеза Черни

0.2 Апробация результатов

0.3 Предварительные сведения

1 Примитивные орграфы с большими

экспонентами и медленно синхронизируемые автоматы

1.1 Постановка задачи и структура главы

1.2 Методика и некоторые результаты эксперимента

1.3 Примитивные орграфы и их экспоненты

1.4 Серии медленно синхронизируемых автоматов

1.5 Обсуждение и гипотезы

2 Медленно синхронизируемые

эйлеровы автоматы

2.1 Введение

2.2 Предварительные сведения

2.3 Основные результаты

3 Синхронизация автоматов

ограниченного ранга

3.1 Введение

3.2 Предварительные сведения

3.3 Основные результаты

3.4 Заключение и обсуждение

4 Непокрывающие множества и гипотеза

Рестиво

4.1 Введение

4.2 Множество вк

4.3 Верхняя оценка на величину ии)1(8к)

4.4 Нижняя оценка на величину ии)1(8к)

4.5 Заключение

Список литературы

Введение диссертации (часть автореферата) на тему «Экстремальные конструкции в теории синхронизируемых автоматов»

Введение

0.1 Синхронизируемые автоматы и гипотеза Черни

Конечный автомат представляет собой простую модель вычислений, которая находит свое применение во множестве областей. Автомат характеризуется множеством возможных состояний Q, а также функцией переходов <5, которая определяет, как изменится состояние автомата после чтения очередной входной буквы из Е. Множество Е мы будем называть алфавитом, а его элементы буквами. Прообраз такой модели был представлен в работе нейрофизиологов МакКаллока и Питтса [29], написанной в 1943 году. В ней автоматы были введены как упрощенная модель функционирования нейронов. Примечательно, что в этой работе также были заложены основы машинного обучения. Вскоре Клини [28] значительно расширил результаты МакКаллока и Питтса, чем и заложил основы теории автоматов, как математической дисциплины. Именно в работе [28] была доказана знаменитая теорема об эквивалентности конечных автоматов и регулярных выражений. В дальнейшем теория автоматов обогатилась глубокими взаимосвязями с логикой и алгеброй. Благодаря развитию вычислительной техники теория автоматов пополнилась многочисленными приложениями. На сегодняшний день теория автоматов лежит в основе теории компиляторов и формальной верификации программ. В довершение, чтобы прояснить роль теории автоматов в современной математике приведем слова Сакаровича из книги [42]: «... теория автоматов - линейная алгебра компьютерных наук ... это основополагающий предмет, каждому известный и повсеместно используемый, который настолько давно занимает часть научного кругозора, что это уже незаметно».

Интересные подробности истории теории автоматов на ранних этапах ее развития изложены в лекции Алонзо Чёрча [16] в 1962 году на международном конгрессе математиков в Стокгольме. Современный взгляд на прошлое и будущее теории автоматов изложен в книге «Полвека теории автоматов» [40].

Истоки темы, развиваемой в данной диссертации, можно найти в работе Мура [31] «Gedanken-experiments on Sequential Machines», опубликованной в 1956 году. Автоматом Мура называется конечный автомат, дополненный выходной функцией 7, которая всякому состоянию ставит в соответствие символ из некоторого выходного алфавита Л. Автомат Му-

ра при чтении входного символа не только переходит в новое состояние д, но также выводит символ 7(9). Для Мура такой автомат служил прежде всего моделью некоторого дискретно работающего устройства. Поэтому естественный вопрос, который интересовал Мура, состоит в следующем. Если контроль над устройством потерян, то как вернуть контроль над ним? Иначе говоря, какую последовательность сигналов нужно подать на вход устройства, чтобы по наблюдаемым выходным сигналам однозначно определить его текущее состояние? В работе [31] такая последовательность называлась экспериментом. Отметим, что эксперименты Мура были адаптивными, т.е. всякая следующая буква, зависела от уже полученной выходной строки. В работе Мура уделяется большое внимание оценке длины кратчайшего эксперимента в терминах числа состояний. С практической точки зрения длина эксперимента определяет насколько быстро можно вернуть контроль над устройством. В своей работе [31] Мур показал, что длина кратчайшего эксперимента для автомата с п состояниями не превосходит . Вскоре Карацуба [2], будучи еще

(п—1)(п-2) , -,

студентом, улучшил этот результат, получив точную оценку 1-^-^ + 1.

Следующим важным этапом стала работа Гинзбурга [22], написанная в 1958 году. Он рассмотрел особый вид экспериментов, которые были названы однородными. В таких экспериментах входная последовательность не зависит от порождаемой выходной строки, т.е. является фиксированной. Выходная последовательность в однородных экспериментах используется для определения заключительного состояния автомата после проведения эксперимента.

Заключительный шаг к главному понятию данной диссертации был сделан Черни [15] в 1964 году. Мы остановимся на его результатах подробнее. Черни исследовал следующий вопрос: если автомат не имеет выходной функции, то как определить его текущее состояние? Пусть некоторый автомат имеет множество состояний <5, входной алфавит £ и функцию перехода 5. Через 5(д, т), или д • и;, если 6 ясна из контекста, обозначим состояние, в которое переходит автомат из состояния д после чтения слова т. Автомат называется синхронизируемым, если найдется слово и) над алфавитом £, под действием которого все состояния переходят в одно: q•w — q'•w для всех д, д' Е Ц. Всякое такое слово ги называется синхронизирующим для . Таким образом, если исходное состояние автомата неизвестно, то после прочтения синхронизирующего слова состояние автомата будет однозначно определено. Минимум длин

синхронизирующих слов автомата называется его порогом синхронизации и обозначается гЬ(^). К примеру, автомат приведенный на рис. 1 синхронизируем. Несложно проверить, что его кратчайшее синхронизирующее слово равно аЪЪЬаЪЪЪа. Таким образом, = 9.

Синхронизируемые автоматы представляют собой очень простую и естественную модель систем, устойчивых к ошибкам. Они используются во многих прикладных областях (тестирование систем и протоколов, кодирование информации, роботика) и в то же время неожиданным образом возникают в некоторых разделах фундаментальной математики (символическая динамика, теория подстановочных систем и др.). Основы теории синхронизируемых автоматов и ее разнообразные связи и приложения обсуждаются, например, в недавних обзорах [41,52].

Сразу возникает два естественных вопроса. Как по данному автомату проверить является ли он синхронизируемым? Как найти его синхронизирующее слово? Ответ на оба этих вопроса по сути содержится в следующей лемме, которая появляется уже в первых работах по теории синхронизируемых автоматов. К примеру, эта лемма встречается как теорема 2 в работе [15].

Лемма 0.1. Автомат ¿¡4 = является синхронизируемым то-

гда и только тогда, когда для всякой пары состояний <7, (/' Е (3 найдется такое слово и) € £*, что q■ w — ^ ■ w.

Ъ

Ъ

Рис. 1: Автомат

Для понимания приведенной леммы крайне удобна следующая конструкция. Автомат пар ¿г/^ = Е, <5(2)) автомата = мы определим следующим образом. Множество состояний

Всякая буква £ Е Е действует на множество состояний следующим образом:

\\У>Ч1, ) если = ^ ' ;

(2)

Например, автомат пар Щ для автомата изображенного на рис. 1, приведен на рис. 2.

а

Рис. 2: Автомат пар

Нетрудно видеть, что благодаря такому определению для пары состояний д, Е Я выполнено <7 • ии = д' • го при некотором слове го € Е* тогда и только тогда, когда ({<7, го) = 2. Таким образом, лемму 0.1 можно переформулировать следующим образом:

Лемма 0.2. Автомат является синхронизируемым тогда и только тогда, когда из всякого состояния

¿/(2)

достижимо состояние 2.

С алгоритмической точки зрения проверка на синхронизируемость может быть осуществлена довольно эффективно. Отметим, что число состоянии в автомате пар равно ' —¿ + 1, а степень исхода всякой вершины равна |£|. Из теории алгоритмов на графах хорошо известно, что обход ориентированного графа поиском в ширину решает поставленную задачу за 0(|<3|2|£|).

Во многих приложениях синхронизирующее слово соответствует набору действий, которые мы производим, для определения точного состояния объекта. Например, последовательность вращений детали или последовательность команд, передаваемых устройству. Таким образом, оказывается важной задача поиска и оценки длины кратчайшего синхронизирующего слова. Ведь чем короче слово, тем меньше вращений нужно будет совершить, послать меньше команд, тем самым, можно повысить эффективность устройства.

Опишем наилучший известный на сегодняшний день алгоритм поиска кратчайшего синхронизирующего слова. Автомат подмножеств 'Р(^) — (Р, 6р) автомата = (<3, определяется следующим образом. Множество состояний Р - это все непустые подмножества Для произвольных 8 С (5 и £ € £ положим <5р(£, £) = 6(8, £). Данная конструкция является классической в теории формальных языков и впервые появилась в работе Рабина и Скотта [36]. Например, автомат подмножеств Т(^) для автомата (рис. 1) приведен на рис. 3.

Лемма 0.3. Слово и> является синхронизирующим для автомата = (<5, £, 6) тогда и только тогда, когда слово и) в автомате "Р(^) переводит состояние <3 в одноэлементное подмножество.

На рис. 3 такой путь помечен жирными стрелками. Таким образом, кратчайшее синхронизирующее можно найти поиском в ширину в автомате из состояния ф. Оценим сложность этого алгоритма. Число состояний в автомате равно

21«! — 1. Таким образом, поиск в ширину займет 0(2^11£|). Следовательно, приведенный алгоритм является экспоненциальным от числа состояний в исходном автомате. Он имеет ограниченную область применения, поскольку на современном компьютере вычисление кратчайшего синхронизирующего слова для автомата с тридцатью состояниями уже представляет некоторую трудность.

Помимо алгоритмических возникают также теоретические вопросы. Пожалуй, самым естественным является следующий: как зависит порог синхронизации от числа состояний в автомате? Условимся для краткости

Рис. 3: Автомат подмножеств

называть автомат с п состояниями п-автоматом. В 1964 г. Черни [15] указал серию синхронизируемых п-автоматов с порогом синхронизации (п — I)2. Немного позднее он высказал предположение, что автоматы из этой серии реализуют наихудший (в смысле скорости синхронизации) случай, т. е что каждый синхронизируемый п-автомат может быть синхронизирован словом длины не более (п — I)2. За этим предположением закрепилось имя гипотеза Черни Приведем этот замечательный пример.

Автоматом Черни мы будем называть п-автомат ^ = ({1,2, , п}, {а, Ь}, 6), где буквы а и Ъ действуют следующим образом. I г, если г < п, |г + 1, если г < п, 5{г,а)=\ 5{г,Ъ) = <

I 1, если г = п, II, если г = п.

Автомат Черни ^ был уже представлен на рис 1 Автомат приведен на рис. 4

а

Одним из результатов диссертации являются два новых доказательства того факта, что гЬ(&п) = (п — I)2. Они будут приведены в главах 1 и 2.

Несмотря на простоту формулировки и усилия многочисленных исследователей, гипотеза Черни остается недоказанной и неопровергнутой уже более 45 лет. Более того, до сих пор нет верхней оценки порядка 0(п2) на порог синхронизации произвольного п-автомата. На сегодняшний день лучшей верхней оценкой на порог синхронизации произвольного п-автомата остается оценка п 6п, полученная Пэном [35] еще в 1983 году. Чуть лучшая оценка п^7п ^Ц"-16^ опубликована недавно в [51], но в ее доказательстве имеется неясное место.

Почему гипотеза Черни оказывается столь неприступной? Одно из затруднений, с которым приходится сталкиваться в теории синхронизируемых автоматов является дефицит примеров экстремальных автоматов, т. е. п-автоматов с порогом синхронизации (п — I)2. Единственной известной на сегодня бесконечной серией экстремальных автоматов остается серия, приведенная Черни в [15]. Кроме нее, известно лишь несколько спорадических примеров экстремальных автоматов, наибольшим из которых по числу состояний является 6-автомат, открытый Кари [26] в 2001 г. Полный список известных экстремальных автоматов см. в [52]. Более того, до сих пор даже п-автоматы с порогом синхронизации, близким к (п — I)2, встречались в литературе крайне редко - кроме серии Черни, здесь можно назвать лишь две бесконечных серии автоматов из работы [9]. Приведем их.

Множеством состояний автомата Зёп является {1,2,... ,п}. Входной алфавит состоит из букв а и Ъ, а функция переходов определена следующим образом:

{г, если г < п — 1,

1, если г = п — 1,

2, если г = п; Автомат 58п изображен на рис. 5.

Одним из основных результатов вышеупомянутой статьи [9] является следующая теорема:

Теорема 0.1. Для всякого нечетного п автомат синхронизируем и его порог синхронизации равен (п — 1)(п — 2).

Новое, более простое доказательство этой теоремы будет представлено в главе 1.

Вторая серия автоматов определена при п > 4. Отметим, что обозначение *2)п является исходным обозначением работы [9], в главе 1 под <3>п мы будем понимать другую серию автоматов. Множеством состояний автомата является {1,2,... ,п}, входной алфавит {а,Ь,с} действует на состояния следующим образом:

т 1 2 3 4 5 .. п

5(т, а) 1 1 1 4 5 .. п

5(т, Ъ) 1 1 2 4 5 .. п

8{т, с) 4 1 4 5 6 .. . 3

, . г + 1, если г < п, г ■ о = <

1, если г = п.

Таким образом, буквы а и Ь оставляют на месте всякое состояние т при 4 < т < п, а с действует на множестве {3,4,..., п} как циклическая перестановка. Автомат £)п приведен на рис. 6.

Рис. 6: Автомат

Для автомата справедлива следующая теорема, также доказанная в [9].

Теорема 0.2. Для всякого п автомат синхронизируем и его порог синхронизации равен (п — 2)2 + 1.

В условиях, когда число примеров крайне ограничено, трудно было подвергать проверке различные предположения и допущения, возникавшие при поисках подходов к гипотезе Черни. Именно поэтому история исследований в данной области богата «ложными следами» - вспомогательными гипотезами, которые сперва казались перспективными, но по прошествии некоторого времени опровергались. Ряд таких «ложных следов» проанализирован в [11].

Как же находить медленно синхронизируемые автоматы, т.е. автоматы, с порогом синхронизации близким к (п — I)2? Эксперименты (см., например, [45]) показывают, что взятый наугад автомат с вероятностью, очень близкой к 1, синхронизируем словом, длина которого значительно меньше числа состояний. Поэтому случайно натолкнуться на автомат, порог синхронизации которого близок к квадрату числа состояний,

невозможно. Приходится выявлять такие автоматы путем исчерпывающего перебора. Именно такой переборный эксперимент и послужил отправной точкой для главы 1. В результате было построено значительное количество новых серий медленно синхронизируемых автоматов. Оказалось, что каждая полученная серия тесно связана с некоторой известной серией примитивных орграфов с большой экспонентой. Установленная связь между орграфами и автоматами позволила дать прозрачные и единообразные доказательства утверждений о пороге синхронизации для всех без исключения серий медленно синхронизируемых автоматов - как для серий, уже встречавшихся в литературе, так и для серий, впервые появившихся в данной работе. Техника, примененная в этих доказательствах, представляет самостоятельный интерес.

Говорят, что буква £ е £ имеет ранг г в автомате — (ф, Е, 5), если

• £\ = г. Если в п-автомате буква £ имеет ранг г, то мы также будем говорить, что буква £ имеет дефект п — г. Ранг буквы £ мы будем обозначать гк(£), а дефект с!^). Например, в автомате "г^, изображенном на рис. 4 буква а имеет ранг п — 1 и дефект 1. Гипотеза Черни утверждает, что всякий п-автомат имеет порог синхронизации не более (п — I)2. Довольно естественно попытаться уточнить данную гипотезу. К примеру, можно оценить влияние рангов букв входящих в п-автомат. А именно, каково наибольшее значение порога синхронизации п-автомата с буквой ранга г?

Уже упомянутые результаты работы [9] позволяют нам утверждать, что если в п-автомате есть буква ранга п — 2, то порог синхронизации может достигать (п —1)(п —2) при нечетном п. Таким примером является серия изображенная на рис. 5. Если п четно, то порог синхронизации может достигать значения (п — 2)2 + 1. Примером служит серия приведенная на рис. 6. Глава 3 целиком посвящена связанному вопросу: каково наибольшее значение порога синхронизации может достигать п-автомат, если все его буквы имеют ранг не более г? Был разработан специальный подход, для анализа порога синхронизации таких автоматов. С помощью него были построены п-автоматы, всякая буква которых имеет ранг г и порог синхронизации не менее г2 — г + 1. При этом, при г > ^ построенные автоматы являются сильно связными. Полученные примеры, являются важным шагом к получению уточненной гипотезы Черни, которая учитывает ранг букв.

Несмотря на то, что гипотеза Черни остается довольно неприступной в общем случае, она была подтверждена для многих специальных

классов автоматов. С одной стороны, такие результаты интересны сами по себе, поскольку дают ответ на вопрос, как то или иное свойство автомата влияет на его порог синхронизации. С другой, доказательства для конкретных классов потенциально могут быть перенесены на общий случай. Например, уже в 1978 году Пэн в работе [34] показал, что гипотеза Черни справедлива для автоматов, в которых существует буква, действующая как циклическая перестановка, и количество состояний является простым числом. Позднее, Дюбук в работе [17] расширил этот результат, на произвольное число состояний. Справедливость гипотезы Черни для различных специальных классов автоматов подтверждена в работах [20,53].

Автомат называется эйлеровым, если его ориентированный граф является эйлеровым. В 2003 году в работе [27] Кари показал, что порог синхронизации эйлерова автомата не превосходит п2 — Зп + 3. При этом, не было представлено никакой серии эйлеровых автоматов с «большим» порогом синхронизации. Таким образом, точность полученной верхней оценки была совершенно не ясна. Глава 2 посвящена частичному прояснению этого вопроса. В ней приводится две серии эйлеровых автоматов Жп и ^п с порогами синхронизации п ~44п+и и п ~2П+4 соответственно. Доказательство утверждения о пороге синхронизации для первой серии проводится с помощью техники из главы 1. Она была получена из известной серии эйлеровых ориентированных графов с большой экспонен-той, см. [44]. Серия <Мп была выявлена в ходе исчерпывающего перебора эйлеровых автоматов. Для доказательства утверждения о пороге синхронизации автомата была использована существенно обобщенная техника главы 1. По сути, предложенный подход представляет основной интерес в главе 2, а полученные серии эйлеровых автоматов являются полезной иллюстрацией.

Слово и € Е+ является фактором ъи (префиксом или суффиксом соответственно) если ги может быть представлено как т = хиу (ги — иу или ги = хи соответственно) для некоторых х, у £ Е*. Пусть 5 - конечное множество слов над алфавитом Е. Слово ги Е Е* называется покрываемым относительно 5, если и) является фактором некоторого слова из 51*, в противном случае и) называется непокрываемым. Множество слов Б является покрывающим, если всякое слово над алфавитом Е является покрываемым относительно Б. В противном случае <5 - непокрывающее множество.

Пример 0.4. Пусть Е = {о, Ь}. Рассмотрим множества ^ = {аа, аЬ, Ь} и 5*2 = {ааа,Ь}. Нетрудно видеть, что множество 5*1 является покрывающим, в то время как для ¿2 слово ЬааЬ является непокрываемым.

Понятие покрывающих множеств возникло в связи с некоторыми задачами теории кодирования.

Всякому множеству слов Б мы можем поставить в соответствие автомат специального вида, который мы будем обозначать ^(в) и называть цветочным автоматом. Цветочный автомат множества 5 может оказаться недетерминированным. Отличие такого автомата от обыкновенного, детерминированного автомата состоит в том, что образом состояния под действием буквы является множество состояний. Неформально говоря, автомат состоит из выделенного состояния 1, а также «ле-

пестков», т.е. путей из 1 в 1, помеченных словами из Б. Определим его более формально. Пусть Я = {«1, и2,..., щ}. Множество состояний ^{Б) равно 1и{(г,_7)|1 < г < к, 1 < у < |«г| }• Определим действие букв на состояния следующим образом: Положим (г,= (г,+1), если ]-\-1 < и I является .7 + 1 буквой щ. (г,\щ\ — 1) • £ = 1, если £ является последней буквой щ. И наконец \ ■ = {(г,1) \ I является первой буквой слова щ}. Именно из-за действия букв на состояние 1 автомат может оказаться недетерминированным.

Пример цветочного автомата для множества 5 = {аа, аЬ, Ьа, ЪЪ, ааЬ}

Рис. 7: Цветочный автомат для 5 = {аЬ, Ьа, ааЬ}.

Нам понадобится некоторая модификация автомата ^"(5), которую мы обозначим через ^"(5). Пополним автомат нулевым состоянием

О, и немного изменим функцию перехода. В автомате ^(5) действие

всякой буквы оставляет 0 на месте, т.е. О • £ = 0 для всякой буквы £. Если д • £ — 0 для некоторого состояния д и буквы £ в автомате ^{Б), то в автомате мы полагаем д • £ = {0}.

Понятие синхронизируемости недетерминированного автомата было введено несколькими различными способами, см. [25]. Здесь нам понадобится синхронизируемостъ в сильном смысле.

Недетерминированный автомат ¿¡4 = (С}, Е, 6) мы будем называть синхронизируемым, если найдется слово ги со свойством: <5(д, ги) = {р} для любого д € <5. Иными словами, каким бы способом мы не читали слово и) из произвольного состояния д мы все равно окажемся в р.

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

Теорема 0.3. Слово и) является непокрываемым относительно в тогда и только тогда, когда слово и) является синхронизирующим для автомата ^"(5).

Обозначим длину кратчайшего непокрывающего слова множества 5 через ггагЦ,?). Проблема поиска кратчайших непокрываваемых слов и анализа их длин была предложена Рестиво в 1981. В своей статье [39] он выдвинул гипотезу о том, что непокрывающее множество 5 всегда обладает непокрываемым словом ги длины не более 2к2, где к - это длина самого длинного слова в 5, причем ги имеет вид и> = иУ\иУ2 • • • иьк~\и, где и <£ в,\и\ = ки\ьг\ < к для всех г — 1, 2,..., к — 1. Это предположение мы будем называть гипотезой Рестиво.

Отметим, что используя теорему 0.3 мы можем переформулировать задачу, поставленную Рестиво в следующем виде: какого наибольшего значения может принимать порог синхронизации цветочного автомата, построенного по множеству слов 5, если самое длинное слово в 5 имеет длину к?

Приведем пример непокрывающего множества, которое уже появляется в работе Рестиво [39]. Слово ги называется неокаймленным, если никакой его собственный префикс не является его суффиксом. Обозначим через множество слов длины к. В работе [5] была доказана следующая теорема:

Теорема 0.4. Пусть и - некоторое неокаймленное слово длины к, тогда множество слов Ик \ {и} является непокрывающим, причем длина

кратчайшего непокрываемого слова равна к2 + к — 1.

Непокрываемость данного множества была показана Рестиво, в то время как точное значение длины кратчайшего синхронизирующего слова было получено Прибавкиной в [5]. Она использовала данное непо-крывающее множество для построения детерминированных автоматов с нулем с большим порогом синхронизации.

В конечном числе случаев гипотеза Рестиво была опровергнута представлением контрпримера в работе [21]. А именно, пусть к > 6 и = Е* \ {ак~2ЬЬ} и ЕЬак~4Е и ЕЬа и Ь4 и Л, где Зк = ()кГ*(Ьа*Е и аЩ. В работе [21] авторы вычислили, что при 7 < к < 12 длина кратчайшего непокрываемого слова для Як равна ЗА;2 — 9к + 1, но они не смогли показать это при любом к.

В главе 4 мы представляем новую серию непокрывающих множеств Бк с длиной кратчайшего непокрываемого слова 5к2 — 17к + 13 при к > 4, где длина самого длинного слова в равна к. Таким образом, мы окончательно опровергаем гипотезу Рестиво. Построенный нами пример при небольших значениях параметра к был обнаружен в ходе вычислительного эксперимента, а затем был обобщен на произвольное к. Благодаря теореме 0.3 было возможно использование программного обеспечения, разработанного в ходе работы над главой 1.

16

- .....---

0.2 Апробация результатов

Основные результаты диссертации опубликованы в [55-60]. В работах [55, 56] постановка задачи и подход принадлежит М.В. Волкову. Реализация экспериментов и доказательства принадлежат диссертанту. Одна из приведенных серий в этих работах была ранее получена Д.С. Ананичевым. В работе [57] постановка задачи, общая схема исследования и некоторые идеи доказательств принадлежат Е.В. Прибавкиной. Реализация вычислительных экспериментов и доказательства основных утверждений принадлежат диссертанту. Все работы прошли рецензирование. Все работы, кроме [55,60], имели трех рецензентов.

Ссылки на результаты диссертации присутствуют в работах израильских, итальянских, канадских, и российских математиков.

Основные результаты диссертации докладывались на международном симпозиуме по математическим основам компьютерных наук MFCS 2010 (Брно, Чехия, 2010), международной конференции по формальным языкам DLT 2011 (Милан, Италия, 2011), международном семинаре по проблемам достижимости RP 2011 (Генуя, Италия, 2011), международной конференции по реализации и применению автоматов CIAA 2012 (Порто, Португалия, 2012).

Автор выражает глубокую благодарность родителям, своему научному руководителю профессору М.В.Волкову за свое математическое развитие и своей жене за постоянное внимание к работе.

0.3 Предварительные сведения

Алфавитом называется некоторое конечное множество. Элементы алфавита называются буквами В данной работе алфавит мы будем обычно обозначать через Е, а буквы маленькими латинскими буквами. Всякая конечная последовательность букв называется словом. Пустым словом словом мы будем называть пустую последовательность букв и обозначать через е. Множество всех слов над алфавитом Е, включая пустое, мы будем обозначать £*, а множество непустых слов через Е+. Детерминированным конечным автоматом называется тройка «к/ = (ф, Е, 6), где <3 - конечное множество состояний, Е - конечный входной алфавит, а 6 . <5 хЕ —> ф - всюду определенная функция переходов. Функция 5 естественным образом продолжается на <5 х Е*: для д е Ц и т 6 Е* полагаем 5(д,ги) = д, если IV = е, и <5(д,ги) = 5(д(д,у),а), если т = уа для некоторого у 6 Е* и а € Е. Таким образом, функция <5 определяет действие каждого слова из Е* на множестве <3 Также действие функции 6 можно расширить до действия на подмножествах <3- Положим для всякого Я С. и всякого слова и> £ Е* значение — и^¿(д, ги).

Список литературы диссертационного исследования кандидат наук Гусев, Владимир Валерьевич, 2013 год

Список литературы

Страница проекта «Синхронизируемые автоматы» [Электронный ресурс] https://github.com/vlgusev/SynchronizingAutomata.

Карацуба А. А. Решение одной задачи из теории конечных автоматов // Успехи матем. наук. - I960. - Т.15, Вып. 3(93). - С. 157-159.

Лисковец В. А. Число связных инициальных автоматов // Кибернетика. - 1969. - №3. - С. 16-19.

Мартюгин П. В. Нижние оценки длины кратчайших бережно синхронизирующих слов для двух- и трехбуквенных частичных автоматов // Дискретн. анализ и исслед. опер. — 2008. — Том 15, е 4. — С. 44-56

Прибавкина Е. В. Медленно синхронизируемые автоматы с нулем и непокрывающие множества // Матем. заметки. — 2011. — Т.90, Вып. 3. - С. 422-430.

Сачков В.Н., Тараканов В.Е. Комбинаторика неотрицательных матриц // М.: ТВП, 2000. - 448 с.

Adler R. L., Goodwyn L. W., Weiss В. Equivalence of topological Markov shifts // Israel J. Math. - 1977. - Vol. 27, No. 1. - P. 49-63.

Almeida M., Moreira N., Reis R. Enumeration and generation with a string automata representation // Theor. Comput. Sei. — 2007. — Vol. 387(2) - P. 93-102.

Ananichev D. S., Volkov M. V., Zaks Yu. I. Synchronizing automata with a letter of deficiency 2 // Theor. Comput. Sei. — 2007. — Vol. 376(1-2).

- P. 30-41.

Berlinkov M. V. Approximating the minimum length of synchronizing words is hard // In F. Ablayev, E. W. Mayr (eds.) Computer Science

- Theory and Applications. — Lect. Notes Comput. Sei. — SpringerVerlag, Berlin-Heidelberg-New York. - 2010. - Vol. 6072. - P. 37-47.

[11] Berlinkov M.V. On a conjecture by Carpi and D'Alessandro // Int. J. Foundations Comp. Sei. - 2011. - Vol. 22. - P. 1565-1576.

Berstel J., Perrin D., and Reutenauer C. Codes and automata // Cambridge University press, 2009. — 634 p.

Brualdi R., Ryser H. Combinatorial matrix theory // Cambridge University Press, 1991. — 380 p.

Carpi A., D'Alessandro F. On the hybrid Cerny-Road Coloring problem and Hamiltonian paths //In Gao Yu., Lu H., Seki S., Yu S. (eds.) Developments in Language Theory. — Lect. Notes Comput. Sci. — Springer-Verlag, Berlin-Heidelberg-New York. — 2010. — Vol. 6224. — P. 124-135.

Cerny J. Poznamka k homogennym eksperimentom s konecnymi automatami // Mat.-F>z. Cas. Slovensk. Akad. Vied. — 1964. — V.14. — P. 208-216. [in Slovak]

Church A. Logic, arithmetic, and automata //In Proc. Int. Congr. Math. 1962. — Inst. Mittag-Leffler, Djursholm, Sweden. — 1963. — P. 2335.

Dubuc L. Sur les automates circulaires et la conjecture de Cerny // RAIRO Inform. Theor. Appl. - 1998. - Vol. 32, No. 1-3. - P. 21-34 [in French]

Dulmage A. L., Mendelsohn N. S. The exponent of a primitive matrix // Can. Math. Bull. - 1962. - Vol. 5. - P. 241-244.

Dulmage A. L., Mendelsohn N. S. Gaps in the exponent set of primitive matrices // Illinois J. Math. - 1964. — Vol. 8, Issue 4. — P. 642-656.

Eppstein D. Reset sequences for monotonic automata / / SI AM J. Comput. - 1990. - Vol. 19., Issue 3. - P. 500-510

Fici G., Pribavkina E., Sakarovitch J. On the minimal uncompletable word problem // CoRR, http://arxiv.org/abs/1002.1928. — 2010.

Ginsburg S. On the length of the smallest uniform experiment which distinguishes the terminal states of a machine //J. Assoc. Comput. Mach. - 1958. - Vol. 5. - P. 266-280.

Higgins P. Techniques of semigroup theory // Oxford University Press, 1992. - 272 p.

[24] Huffman D. A. The synthesis of sequential switching circuits //J. Franklin Inst. - 1954. - Vol. 257. - P. 161-190 and 275-303.

[25] Ito M., Shikishima-Tsuji K. Some results on directable automata //In Theory is forever. — Lect. Notes Comp. Sci. — Springer-Verlag, Berlin-Heidelberg-New York. - 2004. - P. 125-133.

[26] Kari J. A counter example to a conjecture concerning synchronizing words in finite automata // Bull. European Assoc. Theor. Comput. Sci.

- 2001. - Vol. 73. - P. 146.

[27] Kari J. Synchronizing finite automata on Eulerian digraphs // Theoret. Comput. Sci. - 2003. - Vol. 295. - P. 223-232.

[28] Kleene S.C. Representation of events in nerve nets and finite automata // In C. E. Shannon and J. McCarthy (eds.) Automata Studies, Ann. Math. Studies. — Princeton Univ. Press, Princeton, N. J. — 1956. — Vol. 34. - P. 3-41.

[29] McCulloch W.S., Pitts, W. A logical calculus of the ideas immanent in nervous activity // Bull. Math. Biophys. — 1943. — Vol. 5. — P. 115-133.

[30] Mealy G. H. A method for synthesizing sequential circuits // Bell Systems Technical Journal. - 1955. - Vol. 34. - P. 1045-1079.

[31] Moore E. Gedanken-experiments with sequential machines // In C. E. Shannon, J. McCarthy (eds.) Automata Studies, Ann. Math. Studies. — Princeton Univ. Press, Princeton, N. J. — 1956. — Vol. 34.

- P. 129-153.

[32] Olesky D.D., Shader B., van den Driessche P. Exponents of tuples of nonnegative matrices // Linear Algebra Appl. — 2002. — Vol. 356. — P. 123-134.

[33] Olschewski J., Ummels M. The complexity of finding reset words in finite automata // In P. Hlineny, A. Kucera (eds.) Mathematical Foundations of Computer Science. — Lect. Notes Comput. Sci. — Springer-Verlag, Berlin-Heidelberg. - 2010. - Vol. 6281. — P. 568-579.

[34] Pin J.-E. Sur un cas particulier de la conjecture de Cerny //In G. Ausiello, C. Bdhm (eds.) Proc. 5th Colloq. on Automata, Languages,

and Programming (ICALP). — Lect. Notes Comput. Sci.— SpringerVerlag. - 1978. - Vol. 62. - P. 345-352. [in French]

Pin J.-E. On two combinatorial problems arising from automata theory // Ann. Discrete Math. - 1983. - Vol. 17. - P. 535-548.

Rabin M. O., Scott D. Finite automata and their decision problems // IBM J. Res. Develop. - 1959. - Vol. 3, Issue 2. - P. 114-125.

Ramirez Alfonsin J. L. The diophantine Frobenius problem // Oxford University Press, 2005. - 260 p.

Rampersad N., Shallit J., Xu Z. The computational complexity of universality problems for prefixes, suffixes, factors, and subwords of regular languages // Fundam. Inform. — 2012. — Vol. 116, No. 1-4. - P. 223-236.

Restivo A. Some remarks on complete subsets of a free monoid // Quaderni de "La ricerca scientifica". — CNR Roma. — 1981. — Vol. 109. - P. 19-25.

Salomaa A., Wood D, Yu S. A half-century of automata theory: celebration and inspiration // World Scientific, 2001. — 164 p.

Sandberg S. Homing and synchronizing sequences // In M. Broy et al (eds.) Model-Based Testing of Reactive Systems. — Lect. Notes Comput. Sci. — Springer-Verlag, Berlin-Heidelberg-New York. — 2005. — Vol. 3472. - P. 5-33.

Sakarovitch J. Elements of automata theory // Cambridge University Press, 2009. — P. xvii.

Shader B.L., Suwilo S. Exponents of nonnegative matrix pairs // Linear Algebra Appl. - 2003. - Vol. 363. - P. 275-293.

Shen J. Exponents of 2-regular digraphs // Discrete Math. — 2000. — Vol. 214. - P. 211-219.

Skvortsov E. Tipikin E. Experimental study of the shortest reset word of random automata // In B. Bouchou-Markhoff et al (eds.) Implementation and Application of Automata. — Lect. Notes Comput.

Sci. - Springer-Verlag, Berlin-Heidelberg. - 2011. - Vol. 6807. P. 290298.

[46] Steinberg B. The Cerny conjecture for one-cluster automata with prime length cycle // Theor. Comput. Sci. - 2011. - Vol. 412. - P. 5487-5491.

[47] Trahtman A.N. An efficient algorithm finds noticeable trends and examples concerning the Cerny conjecture // In R. Kralovic, P. Urzyczyn (eds.) Mathematical Foundations of Computer Science. — Lect. Notes Comput. Sci. — Springer-Verlag, Berlin-Heidelberg. — 2006.

- Vol. 4162. - P. 789-800.

[48] Trahtman A. N. Notable trends concerning the synchronization of graphs and automata // Electr. Notes Discrete Math. — 2006. — Vol. 25. — P. 173-175.

[49] Trahtman A. N. The Cerny conjecture for aperiodic automata // Discrete Math. Theor. Comput. Sci. — 2007. — Vol. 9, No. 2. — P. 3-10.

[50] Trahtman A. N. The Road Coloring Problem // Israel J. Math. — 2009.

- Vol. 172. - P. 51-60.

[51] Trahtman A. N. Modifying the upper bound on the length of minimal synchronizing word // In O. Owe, M. Steffen, J. A. Telle (eds.) Fundamentals of Computation Theory. FCT 2012. — Lect. Notes Comput. Sci. — Springer Berlin Heidelberg. — 2011. — Vol. 6914. — P. 173-180.

[52] Volkov M. V. Synchronizing automata and the Cerny conjecture // In C. Martin-Vide, F. Otto, H. Fernau (eds.) Languages and Automata: Theory and Applications. LATA 2008. — Lect. Notes Comp. Sci. — Springer-Verlag, Berlin-Heidelberg-New York. — 2008. — Vol. 5196. — P. 11-27.

[53] Volkov M.V. Synchronizing automata preserving a chain of partial orders. - Theor. Comput. Sci. - 2009. - Vol. 410. P. 3513-3519.

[54] Wielandt H. Unzerlegbare, nicht negative Matrizen // Math. Z. — 1950.

- Vol. 52. - P. 642-648. [in German]

Работы автора по теме диссертации

[55] Ананичев Д. С., Волков М.В., Гусев В. В. Примитивные орграфы с большими экспонентами и медленно синхронизируемые автоматы // Записки научных семинаров ПОМИ. (Комбинаторика и теория графов. IV). - 2012. - Том 402. - С. 9-39.

[56] Ananichev D.S., Gusev V. V., Volkov M.V. Slowly synchronizing automata and digraphs // In P. Hlineny, A. Kucera (eds.) Mathematical Foundations of Computer Science. — Lect. Notes Comput. Sci. — Springer-Verlag, Berlin-Heidelberg. - 2010. - Vol. 6281. - P. 55-64.

[57] Gusev V., Pribavkina E. On non-complete sets and Restivo's conjecture // In G. Mauri, A. Leporati (eds.) Developments in Language Theory. — Lect. Notes Comput. Sci. — Springer-Verlag, Berlin-Heidelberg. — 2011.

- Vol. 6795. - P. 239-250.

[58] Gusev V. Lower bounds for the length of reset words in Eulerian automata // In G. Delzanno, I. Potapov (eds.) Reachability Problems.

— Lect. Notes Comput. Sci. — Springer-Verlag, Berlin-Heidelberg. — 2011. - Vol. 6945. - P. 180-190.

[59] Gusev V. Synchronizing automata of bounded rank // In N. Moreira, R. Reis (eds.) Implementation and Application of Automata. — Lect. Notes Comput. Sci. — Springer-Verlag, Berlin-Heidelberg. — 2012. — Vol. 7381. - P. 171-179.

[60] Gusev V. Lower bounds for the length of reset words in Eulerian automata // Int. J. Found. Comput. Sci. — 2013. — Vol. 24. - P. 251262.