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

РОССИЙСКАЯ АКАДЕМИЯ НАУК УРАЛЬСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ

На правах рукописи

005535460

Гусев Владимир Валерьевич

ЭКСТРЕМАЛЬНЫЕ КОНСТРУКЦИИ В ТЕОРИИ СИНХРОНИЗИРУЕМЫХ АВТОМАТОВ

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ 2 4 ОКТ 2013

диссертации на соискание учёной степени кандидата физико-математических наук

Екатеринбург, 2013

005535460

Работа выполнена на кафедре алгебры и дискретной математики ФГАОУ ВПО Уральского федерального университета имени первого Президента России Б.Н. Ельцина

Научный руководитель:

Волков Михаил Владимирович, доктор физико-математических наук, профессор.

Официальные оппоненты:

Гутерман Александр Эмилевич, доктор физико-математических наук, доцент, профессор кафедры высшей алгебры Московского государственного университета имени М.В. Ломоносова

Хачай Михаил Юрьевич, доктор физико-математических наук, доцент, зав. отделом математического программирования ИММ УрО РАН.

Ведущая организация:

ФГАОУ ВПО Казанский (Приволжский) федеральный университет

Защита диссертации состоится 13 ноября 2013 года в 1500 часов на заседании диссертационного совета Д 004.006.04 в Институте математики и механики УрО РАН по адресу: 620990, г. Екатеринбург, ул. Софьи Ковалевской, 16.

С диссертацией можно ознакомиться в библиотеке Института математики и механики УрО РАН.

Автореферат разослан " " октября 2013 г.

Учёный секретарь диссертационного совета, доктор физико-математических наук,

с.н.с. / / В. Д. Скарин

Общая характеристика работы

Актуальность темы. Конечные автоматы нашли свое применение во множестве областей математики и лежат в основании теоретических компьютерных наук. На раннем этапе развития теории автоматов они служили прежде всего моделью дискретно работающего устройства. При таком подходе естественно возникает следующий вопрос: как вернуть контроль над устройством, если его текущее состояние неизвестно? Впервые эта проблема была рассмотрена Муром [11] в 1956 году. Автоматы, которые он изучал, в ответ на каждую входную букву печатали некоторый выходной символ, зависящий от состояния. Решенную Муром задачу можно сформулировать так: какие сигналы нужно подать на вход устройства, чтобы по полученным откликам можно было однозначно определить его текущее состояние? Для автоматов без выхода аналогичную проблему впервые рассмотрел Черни [б] в 1964 году. Он же ввел следующие понятия. Рассмотрим некоторый автомат со множеством состояний О, и функцией переходов <5. Автомат называется синхронизируемым, если найдется слово ги, под действием которого все состояния переходят в одно: го) = -ш) для всех q, д' е С}. Всякое такое слово и> называется синхронизирующим для . Таким образом, если исходное состояние автомата неизвестно, то после прочтения синхронизирующего слова его состояние будет однозначно определено. К примеру, автомат

приведенный на рис. 1, синхронизируем, поскольку слово аЪЬЬаЬЪЬа переводит все состояния в 1.

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

Во многих приложениях важным фактором является длина синхронизирующего слова. Минимум длин синхронизирующих слов автомата ^ называется его порогом синхронизации и обозначается Усло-

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

превосходит (n—I)2. За этим предположением закрепилось имя гипотеза Черни.

Несмотря на простоту формулировки и усилия многочисленных исследователей, гипотеза Черни остается недоказанной и неопровергнутой уже около 50 лет. Более того, до сих пор нет верхней оценки порядка ©(га2) на порог синхронизации произвольного га-автомата. На сегодняшний день лучшей верхней оценкой на порог синхронизации произвольного га-автомата является оценка "(7n *g"~16), полученная Трахтманом в [17], которая является незначительным улучшением оценки Пэна полученной еще в 1983 году [12].

Исследованию синхронизируемых автоматов и их приложений посвящены сотни работ. Результаты в этом направлении докладываются на международных конференциях из ведущих серий: Developments in Language Theory (DLT), Conference on Implementation and Application of Automata (CIAA), Mathematical Foundations of Computer Science (MFCS), и др. Таким образом, есть все основания утверждать, что тема диссертации актуальна.

Основные задачи, решаемые в диссертации. Одно из затруднений, с которым приходится сталкиваться в теории синхронизируемых автоматов является дефицит примеров экстремальных автоматов, т. е. га-автоматов с порогом синхронизации (n — I)2. Единственной известной

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

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

Поскольку медленно синхронизируемые автоматы встречаются крайне редко, то с практической точки зрения представляют интерес свойства синхронизируемых случайных автоматов. Говорят, что буква а имеет ранг г в автомате если \5(СЗ, а)| = г. Ранг буквы а мы будем обозначать через гк(а). Например, в автомате изображенном на рис. 1 буква а имеет ранг 3. Известно, см. [8], что математическое ожидание ранга буквы в случайном автомате равно ПЁрИ. Таким образом, почти все автоматы обладают буквой небольшого ранга. Естественно оценить влияние рангов букв на порог синхронизации в случайном автомате. Первые шаги в этом направлении были сделаны в [2]. Там были приведены примеры, показывающие что порог синхронизации п-автомата с буквой ранга п — 2 может достигать значения (п — 1 )(п — 2) при нечетном п; если же п четно, то (п — 2)2 + 1. Если всякая буква автомата имеет ранг не более г, то мы будем называть автоматом ограниченного ранга г. Таким образом, с точки зрения изучения свойств синхронизируемых автоматов в среднем важно оценить порог синхронизации в классе автоматов ограниченного ранга.

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

*Ряд таких «ложных следов» проанализирован в [3].

сов автоматов. Один из рассматривавшихся в литературе классов естественно определяется в терминах ориентированного графа (орграфа) автомата. Напомним, что его вершинами являются состояния автомата, и для всякого перехода из состояния р в д под действием некоторой буквы проведена дуга из р в д. Автомат называется эйлеровым, если его ориентированный граф является эйлеровым. Такие автоматы часто возникают в различных областях математики, например, эйлеровым автоматом является граф Кэли группы. В 2003 году Кари [10] показал, что порог синхронизации синхронизируемого эйлерового автомата не превосходит п2 — Зп + 3. Однако для порога синхронизации эйлеровых автоматов не было известно никакой нижней оценки того же порядка, что и верхняя оценка [10]. Возникает важная задача построения эйлеровых автоматов с квадратичным порогом синхронизации.

Одна из областей, в которых находят применение синхронизируемые автоматы - теория кодирования, см. [4]. Дадим несколько определений из этой области. Слово и Е £+ является фактором слова и/, если ю может быть представлено как и> = хиу для некоторых х, у € £*. Пусть 5 - конечное множество слов над алфавитом Е. Слово ги € £* называется покрываемым относительно 5, если ги является фактором некоторого слова из 5*, в противном случае IV называется непокрываемым. Множество слов 5 является покрывающим, если всякое слово над алфавитом Е является покрываемым относительно Я. В противном случае 5 - непо-крывающее множество. Понятие непокрывающих множеств возникло в связи с рядом задач в теории кодирования.

В [1] показано, что всякому множеству слов 5 можно поставить в соответствие автомат ^(в) специального вида таким образом, что Б является непокрывающим тогда и только тогда, когда ¿^(5) является синхронизируемым. Более того, множества непокрываемых слов для 5' и синхронизирующих слов для ¿^(5) совпадают. Отметим, что автомат ^(5) может оказаться недетерминированным и тогда синхронизируе-мость нужно понимать в некотором обобщенном смысле.

Обозначим длину кратчайшего непокрывающего слова множества 5 через ишЦй1). Проблема поиска кратчайших непокрываваемых слов и анализа их длин была предложена Рестиво [13] в 1981 году. Рестиво выдвинул гипотезу о том, что непокрывающее множество 5 всегда обладает непокрываемым словом ги длины не более 2к2, где к - это длина самого длинного слова в 5. Это предположение мы будем называть гипотезой Рестиво. По сути, принимая во внимание взаимосвязь между синхро-

визируемыми автоматами и непокрывающими множествами, гипотеза Рестиво является аналогом гипотезы Черни в некотором специальном классе автоматов.

В случае, когда длина самого длинного слова из S не превосходит 12, гипотеза Рестиво была опровергнута в [7]. Пусть к > б, положим Rk = Zk\ {ah~2bb} U £bafc-4£ U Sba U Ь4 U Jk, где Jk = (JtffV^ U аЩ. В [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 наименований.

Краткое содержание работы

Во введении обсуждается история вопроса, приводятся основные определения и формулируются основные результаты диссертации.

В первой главе построено несколько бесконечных серий медленно синхронизируемых автоматов. Эксперименты (см.,например, [16]) показывают, что взятый наугад автомат с вероятностью, очень близкой к 1, синхронизируем словом, длина которого значительно меньше числа состояний. Поэтому случайно натолкнуться на автомат, порог синхронизации которого близок к квадрату числа состояний, невозможно. Таким образом, для поиска медленно синхронизируемых автоматов был проведен исчерпывающий вычислительный эксперимент. Методика и некоторые результаты эксперимента описаны в §1.2. Эксперименты указали на глубокие взаимосвязи между синхронизируемыми автоматами и примитивными орграфами. Ориентированный граф называется примитивным, если найдется Ь такое, что для любой пары вершин и и в найдется маршрут аз и в V длины Ь. Наименьшее число £ с таким свойством называется экспонентой орграфа. В §1.3 обсуждается сходство, между наблюдаемым поведением количества синхронизируемых автоматов с фиксированным числом состояний как функции от значения порога

синхронизации и хорошо изученным(см. [5]) поведением количества примитивных орграфов с фиксированным числом вершин как функции от значения экспоненты.

В §1.4 представлены основные результаты главы. В ней исследуется девять серий синхронизируемых п-автоматов с порогом синхронизации, заключенным в пределах от (п — 2)2 + 2 до (n — I)2. Все медленно синхронизируемые автоматы, найденные в ходе эксперимента, принадлежат одной из указанных серий. Две серии ранее встречались в литературе, для них представлены более простые доказательства.

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

Предложение 1.2. Пусть si - сильно связный синхронизируемый п-автомат с порогом синхронизации t. Тогда экспонента его орграфа tie превосходит t + п — 1.

Установленная связь между орграфами и автоматами позволила дать прозрачные и единообразные доказательства утверждений о пороге синхронизации для всех представленных серий автоматов.

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

Во второй главе исследуется порог синхронизации эйлёрового автомата. Представлена серия эйлеровых синхронизируемых п-автоматов Жп с двумя буквами и квадратичным порогом синхронизации. Она тесно связана с примитивными эйлеровыми n-орграфами с максимальной возможной экспонентой(см. [15]). С использованием идей, развитых в главе 1, получен следующий результат:

Предложение 2.2. Порог синхронизации автомата равен "2~44"+11.

Основным результатом главы является бесконечная серия п-автоматов обнаруженная в ходе вычислительных экспериментов. Автомат y/i-j приведен на рис. 2. Справедлива следующая теорема:

Теорема 2.1. Если п > 5 нечетно, то автомат синхронизируем и его порог синхронизации равен " ~2W+4.

Доказательство этой теоремы потребовало дальнейшего развития техники из главы 1.

а

В третьей главе исследуются автоматы, в которых ранг букв ограничен г < п. В данной главе важную роль играет следующая взаимосвязь между автоматами и матрицами. Всякой букве а п-автомата я/ сопоставим квадратную (0,1)-матрицу А размера п на п согласно правилу: элемент {}■,]) матрицы А равен 1, если состояние г переходит в ^ под действием буквы а, иначе элемент (г,]) равен 0. Множество матриц, соответствующих буквам автомата л/, мы будем называть матричным представлением автомата ¿г/. Если п-автомат «к/ имеет матричное представление (А, В), то множество пар матриц а = ((X, У), (Г, Д)) будем называть г-разложением автомата ¿г/, если:

(I) X, Г суть (0,1)-матрицы размера п на г

(II) У, А суть (0,1)-матрицы размера г на п

(III) А = ХУ, В = ГД

(гу) во всякой строке X, У, Г, Д содержится лишь одна 1.

Отметим, что каждый автомат ограниченного ранга г обладает г-разложени Всякому п-автомату .е/ над двухбуквенным алфавитом ограниченного ранга с г-разложением а мы ставим в соответствие г-автомат ¿з^ над четырехбуквенным алфавитом. Автомат мы будем называть приведенным автоматом автомата ¿г/. Это соответствие является ключевым в данной главе. Приведенный автомат тесно связен с исходным:

Предложение 3.3. Пусть srf - некоторый синхронизируемый автомат с двумя буквами. Тогда для всякого разложения а приведенный автомат синхронизируем и rt(£/a) < + 1.

На самом деле, задачи синхронизации автоматов srf и säa практически идентичны. Будем говорить, что автомат srf синхронизируем с ограничением где & - некоторый регулярный язык, если найдется слово w, синхронизирующее автомат yJ и принадлежащее языку Будем называть наименьшую возможную длину такого слова w порогом синхронизации с ограничением и обозначать rtc(£/,M). Оказывается, что при некотором регулярном языке зафиксированном для всех автоматов над двухбуквенным алфавитом, справедливо следующее предложение:

Предложение 3.5. Пусть srf - некоторый автомат над двухбуквенным алфавитом. Тогда для всякого разложения а автомат синхронизируем с ограничением М тогда и только тогда, когда автомат si синхронизируем. Более того, rtc(£/a,&) — 1 < rt(j/) < rtc(&/,&) + 1.

Отметим, что приведенные автоматы для автоматов ограниченного ранга г с различным числом состояний могут совпадать. Таким образом, на основании одного фиксированного r-автомата ёё можно построить целую серию n-автоматов которые имеют 38 в качестве своего приведенного. При этом по предложению 3.5 их порог синхронизации будет оценен очень точно. На основании этой идеи и разработанной техники доказывается следующее предложение:

Предложение 3.7. Для всякого г < п существует синхронизируемый двух буквенный п-автомат ограниченного ранга г с порогом синхронизации не менее г2 —г —1. Если г > то автомат будет сильно связен.

В четвёртой главе исследуется бесконечная серия непокрывающих множеств Sk- Пусть Е = {а, Ь}. Тогда

Sk = (Ek \ {bak~\bk-1a}) U (S^1 \ {a^1,^1}) .

Рассуждения данной главы существенно опираются на понятие запрещенной позиции в слове. Это понятие впервые было сформулировано в работе [1]. Рассмотрим некоторое непокрывающее множество S и непокрываемое им слово w. Будем говорить, что 0 < j < |го| — 1 является запрещенной позицией в w относительно S, если суффикс слова

ь), начинающийся в позиции не является префиксом никакого слова в Б*. Отметим, что если длины слов в Б не превосходят к и позиции 0,1,..., к — 1 запрещены в некотором слове ю, то т является непокры-ваемым относительно 5.

В разделе 4.2 приводится несколько технических результатов о расположении запрещенных позиций в некотором слове ги относительно множества Б к-

Основным результатом раздела 4.3 является следующая теорема:

Теорема 4.1. При к > 4 множество Б к является непокрывающим и существует непокрываемое слово длины Ък2 — 17к + 13.

В разделе 4.4 показано, что оценка, достигнутая в теореме 4.1, является точной:

Теорема 4.4. Длина кратчайшего непокрываемого слова для Бк не менее 5к2 - 17к + 13 при к > 4.

Для доказательства теорем и потребовалось тщательно изучить распределение запрещенных позиций в непокрываемых словах множества Бк- Из теоремы немедленно следует, что гипотеза Рестиво не верна ни при каком к > 4.

Основные результаты диссертации

• Построено несколько серий медленно синхронизируемых автоматов.

• Построены серии эйлеровых автоматов с квадратичным порогом синхронизации.

• Изучена зависимость порога синхронизации от максимума рангов букв автомата. Построены серии автоматов ограниченного ранга с порогом синхронизации, являющимся квадратичной функцией ранга.

• Представлена бесконечная серия контрпримеров к гипотезе Рестиво.

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

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

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

[2] Ananichev D.S., Volkov M.V., Zaks Yu.I. Synchronizing automata with a letter of deficiency 2 // Theor. Comput. Sci. - 2007. - Vol. 376(1-2). - P. 30-41.

[3] Berlinkov M.V. On a conjecture by Carpi and D'Alessandro //flnt. J. Foundations Сотр. Sci. - 2011. - Vol. 22. - P. 1565-1576.

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

[5] Brualdi R., Ryser H. Combinatorial matrix theory // Cambridge University Press, 1991. - 380 p.

[6] Cerny J. Poznamka k homogermym eksperimentom s konecnymi auto-matami // Mat.-Fyz. Cas. Slovensk. Akad. Vied. - 1964. — V.14. - P. 208-216.

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

[8] Higgins P. Techniques of semigroup theory // Oxford University Press, 1992.

- 272 p.

[9] 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.

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

[11] Moore E. Gedanken-experiments with sequential machines // In С. E. Shannon, J. McCarthy (eds.) Automata Studies, Ann. Math. Studies.

- Princeton Univ. Press, Princeton, N. J. — 1956. — Vol. 34. — P. 129-153.

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

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

[14] 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. 533.

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

[16] 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. 290-298.

[17] Trahtman A. N. Modifying the upper bound on the length of minimal synchronizing word // In 0. 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.

[18] 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 Сотр. Sci. — Springer-Verlag, Berlin-Heidelberg-New York. - 2008. - Vol. 5196. - P. 11-27.

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

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

[20] 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, BerlinHeidelberg. - 2010. - Vol. 6281. - P. 55-64.

[21] 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.

[22] 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.

[23] 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.

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

Копировальный центр "Таймер", г. Екатеринбург, ул. Луначарского, 136 http://copytimer.ru, тел.: +7 (343) 350-39-03 тираж_экз. заказ N2_

ГОУ ВПО УРАЛЬСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ ИМЕНИ ПЕРВОГО ПРЕЗИДЕНТА РФ Б.Н. ЕЛЬЦИНА

04201365532

На правах рукописи

Гусев Владимир Валерьевич

УДК 519.713

ЭКСТРЕМАЛЬНЫЕ КОНСТРУКЦИИ В ТЕОРИИ СИНХРОНИЗИРУЕМЫХ АВТОМАТОВ

01.01.09 — дискретная математика и математическая кибернетика

Диссертация на соискание учёной степени кандидата физико-математических наук

Научный руководитель — доктор физ.-мат. наук, профессор М. В. Волков

Екатеринбург, 2013

Содержание

Введение 3

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

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

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

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

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

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

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

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

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

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

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

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

2.1 Введение .............................47

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

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

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

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

3.1 Введение ..........................................................58

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

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

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

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

Рестиво 70

4.1 Введение..........................................................70

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

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

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

4.5 Заключение............................84

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

Введение

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. Г