автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Синхронизируемость конечных автоматов в экстремальном и среднем случаях

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

ЗАКС Юлия Иосифовна

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

05.13.17 — тсорстичсскис основы информатики

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

з 1 маи 2012

Челябинск - 2012

005045106

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

Научный ВОЛКОВ Михаил Владимирович

руководитель: доктор физ.-ыат. наук, профессор

зав. кафедрой алгебры и дискретной математики,

ФГЛОУ ВПО «Уральский федеральный университет имени

первого Президента России Б. Н. Ельцина»

Официальные РОЖКОВ Александр Викторович

оппоненты: доктор физ.-ыат. наук, профессор

профессор кафедры цифровых радиотехнических систем, ФГБОУ ВПО «Южно-Уральский государственный университет» (национальный исследовательский университет)

РЛЙГОРОДСКИЙ Андрей Михайлович доктор фпз.-мат. наук, профессор

профессор кафедры математической статистики и случайных процессов. ФГБОУ ВПО «Московский государственный университет имени М. В. Ломоносова»

Ведущая Федеральное государственное бюджетное учреждение науки

организация: Институт математики имени С. Л. Соболева Сибирского

отделения Российской академии наук (ИМ СО РАН) (г. Новосибирск)

Защита диссертации состоится "15" шопя 2012 года в 12 : 00 час. па заседании диссертационного совета Д 212.298.18 при ФГБОУ ВПО «Южно-Уральский государственный университет» (национальный исследовательский университет) по адресу: 454080, г. Челябинск, пр. Ленина, 76, ауд. 1001.

С диссертацией можно ознакомиться в научной библиотеке Южно-Уральского государственного университета.

Автореферат разослан ІЧ ' мая 2012 года.

Ученый секретарь диссертационного совета

М. Л. Цымблср

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

Актуальность темы. Работа посвящена исследованиям в бурно развивающейся области теоретической информатики - теории синхронизируемых конечных детерминированных автоматов. Детерминированным конечным автоматом или просто автоматом называется тройка объектов = ((2,1,6), где (2 - конечное множество состояний, I - конечный входной алфавит, 6 : х I —> - всюду определенная функция переходов автомата. Функция переходов естественным образом продолжается до отображения (также обозначаемого через 5) из х I* в С?, где через как обычно, обозначается множество всех слов над алфавитом I.

Автомат л/ = 5) называется синхронизируемым, если суще-

ствует слово ГУ 6 I*, переводящее его в состояние, "зависящее только от слова IV и не зависящее от того состояния автомата, в котором XV было применено. В символах это свойство выражается равенством 6(р,™>) = Для всех р, q 6 (2- Любое слово с таким свойством называется синхронизирующим для автомата л/. ■■■■.•

Синхронизируемый автомат - это прозрачная, и в то же время достаточно адекватная математическая модель дискретной управляемой системы, описывающая важную для приложений ситуацию, когда необходимо восстановить контроль над системой, текущее состояние которой неизвестно. Синхронизируемые автоматы нашли широкое применение в различных прикладных областях: в промышленной роботике при проектировании механизмов для ориентации, сортировки и установки деталей на сборочном конвейере [16, 17], в тестировании электронных схем как на физическом уровне, так и на уровне спецификаций и протоколов [10], в тестировании программного обеспечения [7]. Теоретическая мотивация к изучению синхронизируемых автоматов происходит из таких областей математики и информатики, как многозначная логика [15], символическая динамика [4], теория кодирования [6], теория подстановочных систем [11]. Подробнее о различных применениях синхронизируемых автоматов см. недавние обзоры [21, 28].

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

В 1964 году Черни [8] указал серию синхронизируемых п-автоматов с длиной кратчайшего синхронизирующего слова равной (п—1 )2. Немного позднее он высказал предположение, что автоматы из этой серии реализуют наихудший в смысле скорости синхронизации случай, т. е. что каждый синхронизируемый п-автомат может быть синхронизирован словом длины не более (п — 1 )2. Это предположение и получило название гипотезы Черни. Несмотря на простоту формулировки и длинную историю попыток доказательства гипотезы, наилучшей верхней оценкой длины кратчайшего синхронизирующего слова произвольного п-автомата является оценка порядка 0(п3). Трахтман [27] в 2011 году показал, что указанная длина

п(7п2+6п—16) не превосходит —1--'-.

Одной из трудностей, с которой сталкиваются специалисты, занимающиеся гипотезой Черни, является дефицит примеров медленно синхронизируемых автоматов, т. е. автоматов с длиной кратчайшего синхронизирующего слова порядка п2 + О(п), где п - число состояний. Более 40 лет единственной известной бесконечной серией с таким свойством была серия, построенная Черни, а кроме нее было известно только несколько отдельных примеров автоматов с числом состояний от 3 до 6, у которых длина кратчайшего синхронизирующего слова была такой же, как у автомата из серии Черни с тем же числом состояний [13, 19, 26]. В условиях, когда число примеров крайне ограничено, трудно было подвергать проверке различные предположения и допущения, возникавшие при поисках подходов к гипотезе Черни. Именно поэтому история исследований в данной области богата «ложными следами» - вспомогательными гипотезами, которые сперва казались перспективными, но по прошествии некоторого времени опровергались. Исходя из сказанного, представляется весьма естественной задача построения новых бесконечных серий медленно синхронизируемых автоматов.

То, что примеры медленно синхронизируемых автоматов оказались столь редкими, приводит к предположению, что типичные, «средние» синхронизируемые автоматы (в частности, автоматы, возникающие в приложениях) синхронизируются значительно быстрее, чем автоматы из серии Черни. Это предположение подтверждается результатами вычислительных экспериментов, которые показывают, что взятый наугад автомат с вероятностью, очень близкой к 1, синхронизируем словом, длина которого значительно меньше числа состояний [14, 22]. Такое поведение длины кратчайшего синхронизирующего слова согласуется с поведением других параметров конечного автомата, связанных с длиной путей в нем: диа-

метра, степени различимости, длины однородного эксперимента. Значение всех этих параметров для почти всех автоматов существенно отличается от оценки сверху (см., например, обзор [1]). Мы будем говорить, что какое-то свойство выполнено для почти всех автоматов, если доля автоматов с п состояниями, для которых оно выполняется, среди всех автоматов п состояниями стремится к 1 при п —) оо. Если свойство выполнено для почти всех автоматов, будем также говорить, что оно выполняется с высокой вероятностью. Изложенные выше обстоятельства делают актуальными задачу исследования синхронизируемости конечных автоматов в среднем случае и задачу оценки наиболее вероятной длины кратчайшего синхронизирующего слова.

Хиггинс (см. монографию [12]) показал, что математическое ожидание дефекта отображения п-элементного множества в себя, выбранного равномерно случайно из множества всех таких отображений, стремится к ^ при п —> оо. Применив схожие рассуждения, можно получить, что дисперсия этого дефекта стремится к Отсюда вытекает, что с высокой вероятностью дефект случайного отображения (а значит и дефект буквы в случайном автомате) имеет порядок 0(п). Таким образом, в случайном автомате почти наверняка найдется буква достаточно большого дефекта. Поэтому, в свете задачи изучения синхронизируемости в среднем случае, можно также сформулировать задачу изучения синхронизируемости автоматов с буквой большого дефекта и задачу оценки длины кратчайшего синхронизирующего слова для таких автоматов.

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

1. построение бесконечных серий медленно синхронизируемых автоматов;

2. оценка длины кратчайшего синхронизирующего слова автоматов с буквой большого дефекта;

3. исследование синхронизируемости случайных автоматов.

Методы исследования. В работе применяются как классические методы исследования из различных областей математики: теории автоматов, теории вероятностей, теории графов и теории случайных процессов, так и некоторые методы, по-видимому, впервые примененные в теории синхронизируемых автоматов. Так, при оценке длины кратчайшего синхронизирующего слова используется теоретико-игровой подход. Граф автомата в рамках данного подхода является полем некоторой игры. Состояния авто-

мата в игре покрыты монетами, которые в процессе игры перемещаются вдоль стрелок автомата. При доказательстве основных результатов работы используются два варианта таких игр. В дальнейшем предложенный метод нашел применение в работах других авторов, например, [2]. При работе со случайными автоматами применяется теорема Вормальда [29], которая позволяет заменить вероятностный анализ комбинаторного алгоритма решением детерминированной системы дифференциальных уравнений и которая ранее применялась только для доказательства результатов, связанных со случайными графами [29] и задачей выполнимости [3].

Научная новизна. Все результаты диссертации являются новыми.

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

Апробация результатов работы. Основные результаты диссертации докладывались на следующих конференциях и семинарах:

• Семинар по словам и автоматам в составе международного симпозиума "Компьютерные науки в России" \YoWA06 (8 июня 2011 г., г. Санкт-Петербург).

• Международная конференция по теории формальных языков БЬТ'Об (26-29 июня 2006 г., г. Санта-Барбара, США).

• Международная конференция "Автоматы: от математики к приложениям" А^оМа^А'ОЭ (8-12 июня 2009 г., г. Льеж, Бельгия).

• Русско-финский симпозиум по дискретной математике (21-24 сентября 2011 г., г. Санкт-Петербург).

Ссылки на результаты диссертации присутствуют в работах других авторов: [5, 6, 9, 20, 22-25, 28].

Публикации. Основные результаты диссертации опубликованы в работах [30-35]. Совместные работы [32-34] с Е. С. Скворцовым выполнены в нераздельном соавторстве. Совместные работы [30, 31] с Д. С. Ананиче-вым и М. В. Волковым содержат два независимых результата, один из которых получен автором самостоятельно, второй - в нераздельном соавторстве. Работы [30-32] опубликованы в изданиях, включенных ВАК в перечень научных журналов и изданий, в которых должны быть опубликованы основные результаты диссертаций на соискание ученой степени

доктора и кандидата наук.

Структура и объем диссертации. Диссертация состоит из введения, трех глав и списка литературы. Объем диссертации составляет 89 страниц. Библиографический список содержит 72 наименования.

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

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

Пусть л/ — ((^,1,6) - автомат с |<3| > 3. Если буква а е I такова, что преобразование множества состояний порождаемое действием а, имеет дефект 2, то возможны в точности две следующие ситуации.

1. Существует четыре различных состояния Ць Яг, Яз, Ц4 € (2 такие,

что

В этом случае будем говорить, что а - буква-бактриан.

2. Существует три различных состояния Ц], ц2, Яз £ такие, что

В этом случае назовем а буквой-дромадером.

Рис. 1 иллюстрирует введенные понятия и поясняет выбранную терминологию.

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

Содержание работы

6(Чъ а) = 6(ц2, а) Ф 6(яз, а) = 6(Ч4, а).

б(ц,,а) = 6(чг,а) = б(яз, а).

Действие буквы-бактриана Действие буквы-дромадера

Рис. 1: Два типа букв дефекта 2

Теорема 1.1. Для любого нечетного п > 3 существует синхронизируемый автомат 38п с п состояниями и двумя входными буквами, одна из которых - буква-бактриан, т.акой, что кратчайшее синхронизирующее слово для имеет длину (п — 1 )(п — 2).

Автомат серии с наименьшим числом состояний представлен на рис. 2.

Отметим, что в теореме 1.1 ограничение на четность существенно. Если п четно, автомат подобный по-прежнему можно построить, однако он не будет синхронизируемым.

Теорема 1.2. Для любого п > 4 существует синхронизируемый авто-льат с п состояниями и тремя входными буквами, одна из которых - буква-дромадер, такой, что кратчайшее синхронизирующее слово для имеет длину (п — 2)2 + 1.

Автомат изображен на рис. 3.

В §1.1 приводятся необходимые определения и формулируются основные результаты главы. В §1.2 с использованием теоретико-игрового метода доказывается теорема 1.1, а также обсуждается точность нижней оценки, которую она доставляет. Численный эксперимент показывает, что для п = 5, п = 7ип = 9 полученная оценка точна. Кроме того, в §1.2 приведены полученные при помощи численного эксперимента автоматы с буквой-бактрианом на 6 и 8 состояниях, имеющие длинное синхронизирующее слово, однако построить бесконечную серию медленно синхронизируемых автоматов, их включающую, не удается. В §1.3 приводится доказательство теоремы 1.2 в котором, как и в доказательстве теоремы 1.1, используется теоретико-игровой подход. Приводятся также

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

результаты численных экспериментов, в которых были найдены автоматы с 5 и 6 состояниями и буквой-дромадером, у которых длины кратчайших синхронизирующих слов на единицу больше чем длины кратчайших синхронизирующих слов у соответствующих автоматов из серии

Во второй главе диссертации рассматриваются автоматы, имеющие веерную букву.

Пусть si = (Q,l, 6) - автомат с |Q| > 3. Если буква а € I такова, что существуют число к > 3 и состояния qi, q2,..., qk 6 Q такие, что S(qi,a) = 5(q2, a) = ... = 6(qk,a), то будем называть эту букву к-веерной, или, без указания к, просто веерной. Коэффициент к будем называть веерпостъю буквы а. Дефект k-веерной буквы превосходит к. Заметим, что определенная выше буква-дромадер является 3-веерной.

В §2.1 строятся бесконечные серии синхронизируемых автоматов с п состояниями, имеющих k-веерную букву. Для каждой этих серий выполняется соотношение п — k = const. Изучаются длины кратчайших синхронизирующих слов для автоматов из построенных серий. Результаты §2.1 сходны между собой по сути и формулировкам, поэтому приведем здесь только один из них в качестве примера:

Теорема 2.2. Длина кратчайшего синхронизирующего слова автомата п > 6, п-нечетное, равна 2п -+- 4.

Автомат изображен на рис. 4.

Доказательство теоремы 2.2 строится на анализе автомата подмножеств "У38п, достижимых из множества всех состояний автомата.

В §2.2 обсуждается вопрос об экстремальности построенных серий на основе численных экспериментов, проведенных автором, а также результатов численных экспериментов, проведенных Романом [18].

В третьей главе диссертации исследуются вопросы синхронизиру-емости случайных автоматов.

Дадим определение случайного автомата. Рассмотрим множество состояний и алфавит 1. Выберем функцию переходов 6 равномерно случайно из множества функций (6^x1-) Получившаяся тройка (<3, б) определяет случайный (конечный детерминированный) автомат. Следует отметить, что случайный автомат может быть построен следующим образом: для каждого состояния ц €Е и для каждой буквы а € £ выбираем состояние ц' = а) равномерно случайно из <3.

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

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

Теорема 3.3. Пусть si = (Q,I,6) - случайный автомат такой, что IQI = п, Щ > 72 In Tl. Тогда А синхронизируем с высокой вероятностью. Более того, длина кратчайшего синхронизирующего слова этого автомата с высокой вероятностью меньше чем 3n2 In п.

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

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

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

Теорема 3.4. Пусть si = (Q,E,6) - случайный автомат такой, что IQI = п, |1| > п1/2+е для некоторой константы е > 0. Тогда si синхронизируем с высокой вероятностью. Более того, длина кратчайшего синхронизирующего слова этого автомата с высокой вероятностью не превышает n(n — 1 )/2.

Основу доказательства теоремы 3.4 составляет доказательство двух следующих лемм.

Лемма 3.11. Пусть si = (Q,{a,b},5) - случайный автомат над двухбуквенным алфавитом, х g Q. Тогда существует константа т, 0 < г < < I, такая, что для достаточно больших п. вероятность того, что для каждого состояния q g Q существует слово wq_,x g {a, b}*, удовлетворяющее условию qwq_>x = хг больше г.

Лемма 3.12. Пусть si = (Q,I,6) - случайный автомат такой, что IQI = т1, |I| = tlp, ß > 0.5. Пусть Ii,I2 - случайная пара множеств таких, что I Э I, U I2, Zj П 12 = 0, |Ii| = |12| = па для действительного числа ос такого, что 0.5 < а < ß. Тогда с высокой вероятностью множество троек (a,b,q), а g Ibb g 12, для которых выполняется

qQ = qb = q, (1)

содержит более п2а_1/2 элементов.

Результат леммы 3.11 можно переформулировать в терминах задачи распространения инфекции по дугам ориентированного графа. Мы показали, что если в ориентированном графе, обратном графу двух случайных отображений, одна особь (вершина) заражена некоторой инфекцией, то вся популяция (множество всех вершин) будет заражена с конечной вероятностью. Конечной мы называем вероятность, ограниченную снизу некоторой положительной константой при п —) оо.

В доказательстве леммы 3.11, также как и в доказательстве теоремы 3.3, используется некоторый алгоритм на графе. Мы рассматриваем алгоритм, который на каждом шаге либо находит новое состояние q 6 Q, для которого существует слово wq_>x е {а,ъ}*, либо завершается неуспехом. Для данного алгоритма мы оцениваем вероятность того, что он проработает п— 1 шаг. Оценка данной вероятности разбивается на три этапа, на каждом из которых используется своя техника доказательства:

1. Для оценки вероятности того, что алгоритм не завершится неуспехом в начале, проработав не более 0.1 п шагов, используется анализ данного алгоритма как модификации процесса Гальтона-Ватсона.

2. Вероятность того, что алгоритм, проработав 0.1 п шагов, успешно проработает до 0.9п-го шага, оценивается при помощи теоремы Вормаль-да.

3. Для оценки вероятности того, что проработав 0.9п шагов, алгоритм успешно проработает п—1 шаг, применяются комбинаторные методы теории графов.

Отметим, что во всех доказательствах условие, что алгоритм рассматривается не на всей области определения, а только на ее участке, является существенным.

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

Теорема 3.5. Существует константа ро > 0 такая, что для любого п случайный автомат sd = (Q,I,6) с |Q| = n,|I| = 4 синхронизируем с вероятностью больше ро-

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

Идея доказательства данной теоремы аналогична идее доказательства теоремы 3.3 за исключением того, что длина полученного слова в данном случае не оценивается.

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

На защиту выносятся следующие научные результаты.

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

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

3. Доказано, что случайный автомат над алфавитом из 72 1п п букв синхронизируем с высокой вероятностью словом длины Зп2 1п п.

4. Доказано, что случайный автомат над алфавитом из п,/2+е букв синхронизируем и удовлетворяет гипотезе Черни с высокой вероятностью.

5. Доказано, что случайный автомат над четырехбуквенным алфавитом синхронизируем с конечной вероятностью.

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

1. Коршунов А. Д. О перечислении конечных автоматов // Проблемы кибернетики. - 1978. - Т. 34. - С. 5-82.

2. Мартюгин П. В. Задачи, связанные с синхронизацией конечных автоматов: Дисс. ... кандидата физ.-мат. наук. - Екатеринбург, 2008 -173 с.

3. Achlioptas D. Lower bounds for random 3-SAT via differential équations // Theoret. Comput. Sci. - 2001. - V. 265. - P. 159-185.

4. Adler R.L., Goodwyn L.W., Weiss B. Equivalence of topological Markov shifts // Israël J. Math. - 1977. - V. 27. - №1. - P. 49-63.

5. Ananichev D.S., Gusev V.V., Volkov M.V. Slowly synchronizing automata and digraphs // Mathematical Foundation« of Computer Science, Lect. Notes Comput. Sci. - 2010. - V. 6281. - P. 55-64.

6. Biskup M.T., Plandowski W. Shortest synchronizing stringsfor Huffman codes Ц Theoret. Comput. Sci. - 2009. - V. 410. - №38-40. - P. 3925-3941.

7. Blass A., Gurevich Yu., Nachmanson L., Veanes M. Play to test // Formal Approaches to Software Testing. Lect. Notes Comput. Sci. - 2006. -V. 3997. - P. 32-46.

8. Cerny J. Poznamka к homogennym eksperimentom s konecnymi automatami // Mat.-Fyz.'Cas. Slovensk. Akad. Vied. - 1964. - V. 14. - P. 208-216.

9. Chmiel K., Roman A. COMPAS: a computing package for synchronization // Implementation and Application of Automata. Lect. Notes Comput. Sci. - 2010. - V. 6482. - P. 79-86.

10. Cho H., Jeong S.-W., Somenzi F., Pixley C. Synchronizing sequences and symbolic traversal techniques in test generation // J. Electronic Testing. - 1993. - V. 4. - P. 19-31.

11. FrettlohD., Sing B. Computing modular coincidences for substitution tilings and point sets // Discrete Comput. Geom. - 2007. - V. 37. - P. 381-407.

12. Higgins P. Techniques of semigroup theory - Oxford University Press; Oxford; New York; Tokyo, 1992.

13. Kari J. A counter example to a conjecture concerning synchronizing words in finite automata // Bull. European Assoc. Theoret. Comput. Sci. -2001. - V. 73. - P. 146.

14. Kisielewicz A., Kowalski J., Szykula M. Fast algorithm finding the shortest reset words [Электронная публикация] // http://arxiv.org/pdf/ 1203.2822.pdf

15. Mateescu A., Salomaa A. Many-valued truth functions, Cerny's conjecture and road coloring // Bull. European Assoc. Theoret. Comput. Sci. -1999. - V. 68. - P. 134-150.

16. Natarajan В. K. An algorithmic approach to the automated design of parts orienters // Proc. 27th Annual Symp. Foundations Comput. Sci. -IEEE Press, 1986. - P. 132-142.

17. Natarajan В. K. Some paradigms for the automated design of parts feeders // Internat. J. Robotics Research. - 1989. - V. 8. - №6. - P. 89-109.

18. Roman A. Synchronization of finite automaton. Computations for different alphabet sizes [Электронная публикация] // Proc. WoWA'06, Saint-Petersburg. - 2006.

19. Roman A. A note on Cerny Conjecture for automata over 3-letter alphabet // J. Automata, Languages and Combinatorics. - 2008. - V. 13. -№2. - P. 141-143.

20. Roman A. Genetic algoiithm for synchronization // Languages and Automata: Theory and Applications. LATA 2009, Lect. Notes Сотр. Sci. -2009. - V. 5457. - P. 684-695.

21. Sandbcrg S. Homing and synchronizing sequences // Model-Based ting of Reactive Systems, Lect. Notes Comput. Sci. - 2005. - V. 3472. - P. 3.

22. Skvortsov E., Tipikin E. Experimental study of the shortest reset -d of random automata // Implementation and Application of Automata, t. Notes Comput. Sci. - 2011. - V. 6807. - P. 290-298.

23. Steinberg B. Cerny's conjecture and group representation theory // Ugebraic Combinatorics. - 2010. - V. 31. - .>1. - P. 83-109.

24. Steinberg B. The averaging trick and the Сету conjecture // Int. J. mdations Comput. Sci. - 2011. - V. 22. - №7. - P. 1697-1706.

25. Steinberg B. The Cerny conjecture for one-cluster automata with 'me length cycle // Theoret. Comput. Sci. - 2011. - V. 412. - №39. - P.

7-5491.

26. Trahtman A. An efficient algorithm finds noticeable trends and examples cerning the Сету conjecture // Mathematical Foundations of Computer mce. Lect. Notes Comput. Sci. - 2006. - V. 4162. - P. 789-800.

27. Trahtman A. Modifying the upper bound on the length of minimal chronizing word // Fundamentals of Computation Theory. Lect. Notes nput. Sci. - 2011. - V. 6914. - P. 173-180.

28. Volkov M. V. Synchronizing automata and the Cerny conjecture // Lguagcs and Automata: Theory and Applications. Lect. Notes Comput. Sci. 308. - V. 5196. - P. 11-27.

29. Wormald N. C. Differential equations for random processes and random ohs // Ann. Appl. Probab. - 1995. - V. 5. - №4. - P. 1217-1235.

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

Статьи, опубликованные в журналах из списка ВАК

30. Ananichcv D. S., Volkov М. V., Zaks Yu.I. Synchronizing automata г a letter of deficiency 2 // Developments in Language Theory. Lect. Notes nput. Sci. - 2006. - V. 4036. - P. 433-442.

31. Ananichcv D. S., Volkov M. V., Zaks Yu.I. Synchronizing automata і a letter of deficiency 2 І і Theoret. Comput. Sci. - 2007. - V. 376. - P. 41.

32. Skvortsov E., Zaks Yu. Synchronizing random automata // Discr. :h. Theoret. Comput. Sci. - 2010. - V. 12. - №4. - P. 95-108.

Другие публикации

33. Skvortsov Е., Zaks Yu. Synchronizing random automata // AutoMathA'l Proceedings; Liege. - 2009. - P. [39-46].

34. Skvortsov E., Zaks Yu. Synchronizing random automata on 4~letter alphabet // First Russian-Finnish Symposium on Discrete Mathematics, Abstracts. - 2011. - P. 62-63.

35. Закс Ю. И. Синхронизация конечных автоматов с буквой большого дефекта - Гуманитарный ун-т. - Екатеринбург, 2012. - Дсп. в ВИ-НИТИ 17.04.2012, №154-В2012.

ЗАКС Юлия Иосифовна Синхронизирусмость конечных автоматов в экстремальном и среднем случаях Автореферат диссертации на соискание ученой степени кандидата

физ.-мат. наук.

Подписано в печать 12.05.2012. Заказ № 138 Формат 60x90/16. Псч. л. 1. Тираж 120 экз.

Печатный центр "Глобус-Принт" www.globus-print.net 6200010. г. Екатеринбург, ул. Грибоедова, 13. тел (343)346-37-13

Введение

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

0.2 Синхронизируемость автоматов в экстремальном случае, гипотеза Черни.

0.3 Синхронизируемость автоматов в среднем случае.

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

1 Синхронизируемые автоматы с буквой дефекта

1.1 Формулировка и обсуждение результатов.

1.2 серия автоматов с буквой-бактрианом.

1.3 серия автоматов с буквой-дромадером.

2 Синхронизируемые автоматы с буквой большого дефекта

2.1 Постановка задачи и основные определения.

2.2 Медленно синхронизируемые автоматы с буквой большого дефекта.

2.3 Экспериментальная проверка экстремальности серий при небольших п.

3 Синхронизируемость случайных автоматов

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

3.2 Случайные автоматы, синхронизируемые с высокой вероятностью

3.3 Случайные автоматы, для которых выполняется гипотеза Черни.

3.4 Случайные автоматы, синхронизируемые с конечной вероятностью

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

Детерминированным конечным автоматом, или просто автоматом называется тройка объектов = ((2, 6), где - конечное множество состояний, Г - конечный входной алфавит, и 6 : х 21 —> - всюду определенная функция переходов автомата. Заметим, что в теории формальных языков к набору данных, определяющему конечный детерминированный автомат, обычно добавляют выделенное начальное состояние и множество заключительных состояний, но мы таким вариантом определения пользоваться не будем. Состояния из множества мы будем обозначать буквами преимущественно из середины латинского алфавита, выделенными жирным шрифтом, например, р, q. Буквы алфавита I будем обозначать буквами из начала латинского алфавита, например, а, Ъ, с.

Как обычно, через 1* обозначим свободный моноид над I. Элементы свободного моноида мы будем называть словами и обозначать буквами из конца латинского алфавита, например, V. Функция 5 естественным образом продолжается на множество Q х I*, это продолжение мы также будем обозначать через б. Таким образом, каждый элемент свободного моноида ту 6 Г*, в частности, каждая буква алфавита Г, порождает отображение б (, -и>) : 0. —> множества в себя. Мы будем отождествлять слово уу с этим отображением и пользоваться выражениями "слово лу действует на автомате «$/" или "под действием слова IV состояние с^ переходит в состояние с\2". Образ состояния с\ под действием слова для краткости мы будем часто обозначать через

В данной работе мы будем систематически использовать наглядное представление конечного автомата в виде ориентированного графа. При этом представлении автомат изображается в виде диаграммы, на которой состояния автомата изображаются в виде точек или кругов, а переходы - в виде стрелок, помеченных буквами входного алфавита. Если в автомате выполняется с\а — р, это означает, что в диаграмме, его визуализирующей, из точки, соответствующей q, в точку, соответствующую р, ведет стрелка, помеченная буквой а. В дальнейшем мы часто будем отождествлять автомат с его графическим представлением, а переходы будем называть стрелками. Заметим, что стиранием букв со стрелок автомата и "склеиванием" одинаковых стрелок мы получим ориентированный граф: назовем его графом автомата. Более строго, граф автомата я/ - это орграф, множество вершин которого совпадает с множеством состояний автомата ¿г/, а дуги соответствуют переходам автомата, т. е. из вершины с\ есть дуга в вершину р тогда и только тогда, когда с\ а = р для некоторой буквы а £

Основное понятие, изучаемое в данной диссертации, - это понятие синхронизируемого автомата. Автомат = 5) называется синхронизируемым, если существует слово 6 £*, переводящее его в одно состояние, независимо от текущего состояния автомата. В символах это свойство выражается равенством р"п> = с\\к для всех р, q € Q. Любое слово с таким свойством называется синхронизирующим для автомата . Пример синхронизируемого автомата с четырьмя состояниями приведен на рис. 0.1. Нетрудно проверить, что слово уу = аЪ3аЪ3а синхронизирует этот автомат, а именно, применение этого слова к любому состоянию автомата приводит его в состояние 1. Более того, IV является кратчайшим словом с таким свойством, хотя проверка этого факта уже менее тривиальна.

Синхронизируемые автоматы нашли широкое практическое применение в различных областях: роботике, а точнее в производстве механизмов для сортировки, обработки и установки деталей определенной конструкции [45], тестировании реагирующих систем и протоколов [56]. Теоа Ь Ъ а

Рис. 0.1: Автомат Черни ретическая мотивация к изучению синхронизируемых автоматов происходит из таких областей математики, как теория полугрупп [14], многозначная логика и символическая динамика [43], теория подстановочных систем [28]. Подробнее о различных применениях синхронизируемых автоматов см. недавние обзоры [56,65].

Особо хочется остановиться на мотивации, одновременно интересной теоретически и непосредственно практически применимой, а именно, на мотивации из теории кодирования. Для описания данной мотивации нам понадобится несколько определений, связанных со словами. Слово ибГ называется префиксом слова у\> Е £*, если существует слово V Е I* такое, что IV = т>. Если слово V непустое, то префикс называется собственным. Слово х £ I* является фактором слова уу Е £*, если существуют слова и, V Е I* такие, что у\> = ихч. Префиксным кодом над конечным алфавитом 1 называется множество X слов из I* таких, что никакое слово из X не является префиксом никакого другого слова из X. Префиксный код называется максимальным, если он не содержит другого префиксного кода над тем же алфавитом. Максимальный префиксный код X над алфавитом I называется синхронизируемым, если существует слово х Е X* такое, что для любого слова п> Е выполняется мгк Е X*. Такое слово х называется синхронизирующим словом кода X. Преимущество синхронизирующих кодов состоит в том, что в случае возникновения помех при передаче информации от передатчика к приемнику, передачу можно восстановить. Достаточно передать синхронизирующее слово, и все последующие символы будут декодироваться верно. Более того, поскольку вероятность того, что некоторое слово V Е I* содержит фиксированный фактор х, с ростом длины слова стремится к 1, при передаче большого количества информации в некоторые моменты времени синхронизирующие коды синхронизируются сами. Как показано в [23], это свойство синхронизирующих кодов является характеристическим.

Рассмотрим пример, иллюстрирующий введенные понятия. Пусть I = {0,1}, X = {000,0010,0011,010,0110,0111,10,110,111}. Слова кода - это листья бинарного дерева на рис. 0.3 слева. Легко проверить, что X является максимальным префиксным кодом и каждое из слов 010,011110, 01111110,. его синхронизирует. Допустим, передатчик передает кодовое слово ООО, а приемник в силу помех в канале принимает слово 100. Тогда приемник интерпретирует слово 10 как кодовое, и синхронизация между приемником и передатчиком будет потеряна. Однако, с высокой вероятностью1 синхронизация быстро восстановится, а именно в тот момент, когда в потоке передаваемых данных встретится одна из этих последовательностей 010, 011110, 01111110,Некоторые примеры синхронизации потоков приведены на рис. 0.2, вертикальными линиями отмечено разделение потоков на кодовые слова, жирным шрифтом выделены слова, содержащие позицию, с которой восстанавливается синхронизация.

Передано 000|0010 |0111|.

Получено 10 |000 | 10101111.

Передано 000|0111 |110|0011 | 000 | 1 0 | 110 | .

Получено 1010011 |111 | 000 | 110100101 110).

Передано 000 | 000 | 1 1 1 | 10 | .

Получено 101000|0111 |10|.

Рис. 0.2: Пример синхронизации префиксного кода

Пусть X - максимальный конечный префиксный код над алфавитом 1, тогда он может быть декодирован с помощью автомата, определенного следующим образом. В качестве возьмем множество всех собственных префиксов слов из X, включая пустое слово Л, в качестве алфавита - Г, функцию переходов для с\ € и а 6 I определим следующим образом: с\ а, если (\ а - собственный префикс некоторого слова из X, 5(4, а) = <

Л, если с^аеХ.

Получившийся автомат полон в силу того, что X максимален. Нетрудно видеть, что ~ синхронизируемый автомат тогда и только тогда, когда X - синхронизируемый код. Более того, слово х синхронизирует код X тогда и только тогда, когда оно переводит автомат в состояние Л. Рис 0.3 иллюстрирует описанные построения для кода X = од высокой вероятностью мы понимаем вероятность, которая стремится к 1 при длине символьной последовательности, стремящейся к бесконечности.

ООО, 0010,0011,010,0110,0111,10,110,111} из примера выше. Сплошные и пунктирные линии соответствуют символам 0 и 1.

Рис. 0.3: Синхронизируемый код (слева) и его автомат (справа)

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

Интересно, что, несмотря на большое практическое значение, само понятие синхронизируемого автомата произошло не из практики, а из некоторых достаточно абстрактных рассмотрений - так называемых "умозрительных экспериментов" (в оригинале Gedanken Experiments) Мура [44]. Предположим, что мы управляем некоторым дискретно работающим устройством, являющимся опечатанным "черным ящиком", получать информацию о его состояниях мы можем только воздействуя на него некоторыми входными сигналами и наблюдая за выходными. Пусть в устройстве произошел сбой и мы утратили контроль над нам, наша задача на основании только этих наблюдений восстановить контроль над устройством, т. е. установить его текущее состояние. Процедура определения заключительного состояния устройства после введения в него некоторой конечной входной последовательности сигналов и наблюдения за выходной последовательностью называется экспериментом. В 1956 году Мур [44] показал существование такого эксперимента при некоторых условиях. Эксперимент Мура был адаптивным: на каждом шаге следующий сигнал выбирался на основании предыдущих наблюдений. Позднее Гинзбург [33] рассмотрел однородный эксперимент, т. е. эксперимент, в котором входная последовательность выбиралась заранее и не менялась в ходе эксперимента.

А что, если мы не можем наблюдать за ответами нашего "черного ящика" и должны восстановить контроль над ним вслепую? В этом случае мы должны применить к устройству такую входную последовательность символов, которая приведет его в какое-то заранее определенное состояние. Эта идея легла в основу определения синхронизируемого автомата, которое дал в 1964 году словацкий математик Ян Черни [24]. Мотивацией его исследований стала задача восстановления контроля над космическим спутником в моменты, когда он находится вне пределов видимости стан

В связи с введенным понятием синхронизируемости возникает ряд естественных вопросов:

Как по данному автомату проверить, является ли он синхронизируемым?

Как по данному синхронизируемому автомату найти некоторое слово, его синхронизирующее?

Как по данному синхронизируемому автомату найти кратчайшее синхронизирующее слово этого автомата?

Алгоритм, отвечающий на все три вопроса сразу, использует такую классическую конструкцию, как автомат подмножеств Данная конструкция была введена в 1959 году Рабиным и Скоттом [50] и использовалась в алгоритме детерминизации конечного недетерминированного автомата. Множество состояний автомата подмножеств определяется как множество всех непустых подмножеств множества а функция переходов - как естественное продолжение функции б на множество ^'((2) х X (это продолжение также обозначается через б). Рассмотрим некоторое множество состояний автомата (2' = {с^,., с|к}, тогда 6((2', а) ={6(Ч1,а),.,б(ч1с, а)}.

На рис. 0.4 приведен автомат подмножеств для автомата ^4, представленного на рис. 0.1. Нетрудно видеть, что некоторое слово wGГ синхронизирует автомат тогда и только тогда, когда оно читается вдоль пути в автомате Т^) из состояния в некоторое одноэлементное подмножество. Таким образом, задача проверки синхронизируемости автомата сводится к задаче достижимости в графе, которая легко решается поиском в ширину (см. [4]). Слово, прочитанное вдоль пути, найденного поиском в ширину, очевидно, будет кратчайшим синхронизирующим словом данного автомата. Такой способ поиска кратчайшего слова будет использоваться нами в главе 2. На рис. 0.4 жирным шрифтом выделены стрелки пути, вдоль которого читается кратчайшее синхронизирующее слово.

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

Лемма 0.1 Автомат = Г, 6) является синхронизируемым тогда и только тогда, когда для любой пары состояний р, (\ € существует слово уо € X* такое, что ргу = с]уу.

Иными словами, автомат является синхронизируемым тогда и только тогда, когда любую пару (р, q) состояний можно "склеить", или "слить", т.е. подходящим словом перевести р и q в некоторое состояние г. Этот критерий будет использоваться нами при доказательстве синхронизируе-мости в главе 3.

Алгоритм Эпштейна работает за время 0(|Q|2), однако он отвечает только на первый вопрос, на выходе он не строит никакого синхронизирующего слова2. Алгоритм, строящий некоторое синхронизирующее слово автомата, также предложен Эпштейном [27], за время 0(|Q|3) он строит синхронизирующее слово длины 0(|Q|3). Что касается последнего вопроса - поиска кратчайшего синхронизирующего слова - существенно улучшить алгоритм с автоматом подмножеств не удастся. Задача, в которой для заданного автомата ¿rf и заданного натурального числа I требуется определить, имеет ли автомат srf синхронизирующее слово длины не больше £, является NP-полной3 [27].

Самотий [55] указал, что задача проверки того, что кратчайшее слово, синхронизирующее автомат «я/, имеет длину ровно t, является NP-трудной и co-NP-трудной. Таким образом, если co-NP^NP, эта задача не может принадлежать NP. Хотя построения Самотия оказались ошибочными, заявленный результат верен и может быть доказан другими способами. Точная сложность данной задачи установлена сравнительно недавно Гавричовским [31] и, независимо, Ольшевским и Уммельсом [46]. Они показали, что задача DP-полна. Класс сложности DP (Difference Polynomial-Time) был введен Пападимитриоу и Яннакакисом [47]. Этот класс состоит из языков вида Li П L2, Li из NP, a L2 из coNP.

Более того, не существует полиномиального алгоритма, вычисляю

2Обозначения О, о и Э в работе полагаются известными. Формальное определение о вводится в §3.1, более подробно с понятиями можно ознакомиться в книге [4].

3 Вопросы сложности алгоритмов не затрагиваются в диссертации и обсуждаются в данном параграфе сугубо для введения читателя в проблематику и обоснования актуальности проблемы. Поскольку владение понятийным аппаратом теории сложности не требуется для понимания результатов диссертации, определения в работе не приводятся. С терминологией можно ознакомиться в [4]. щего длину кратчайшего синхронизирующего слова с "хорошим" приближением. Берлинков [20] показал, что не существует полиномиального алгоритма, вычисляющего длину кратчайшего синхронизируемого слова с любой конечной относительной погрешностью (в предположении Р Ф ИР).

0.2 Синхронизируемость автоматов в экстремальном случае, гипотеза Черни

В связи с тем, что задача нахождения кратчайшего синхронизирующего слова для конкретного автомата трудна, особую актуальность приобретает вопрос оценки длины кратчайшего синхронизирующего слова сверху. Пусть «с/ - автомат с п состояниями (далее для краткости будем называть такие автоматы п-автоматами, символом п всегда будем обозначать число состояний), пусть синхронизируем. Длину кратчайшего синхронизирующего слова автомата будем обозначать через Отображение, ставящее в соответствие автомату число будем называть функцией Черни. Аналогичным образом введем функцию Черни для классов синхронизируемых автоматов. Для натурального числа п и класса синхронизируемых автоматов Ж через обозначим наибольшую длину кратчайших синхронизирующих слов среди всех синхронизируемых п-автоматов из класса Ж, т. е. лг{п) — тах ел?, кг^|=п.

Эту функцию называют функцией Черни, ограниченной на класс Ж. Символом £(п) будем обозначать функцию Черни для класса всех п-автоматов.

В 1964 году Черни [24] построил бесконечную серию п-автоматов над двухбуквенным алфавитом, кратчайшее синхронизирующее слово которых имеет длину (п—1 )2, т. е. для которых = (п— 1 )2. Автомат приведен на рис 0.1. Позднее Черни предположил, что данная серия реализует наихудший в смысле скорости синхронизации случай, т. е. что любой синхронизируемый п-автомат обладает синхронизирующим словом длины не более (п — 1 )2. Во введенных обозначениях это можно записать равенством С(п) = (п—1 )2. Это предположение, впослед-ствие получившее название гипотезы Черни, все еще остается открытым.

Это одна из самых "старых" открытых проблем в теории автоматов, при том, что гипотеза привлекает внимание многочисленных исследователей, работы, связанные с различными продвижениями в этой области, публикуются ежегодно (например, [15,26,40,54,59,62,64]).

Долгое время наилучшей верхней оценкой (£(п) была кубическая оценка, полученная в 1983 году Пэном [49] с использованием комбинаторного результата Франкля [29]. Пэн показал, что £(п) < Сравнительно недавно, в 2011 году, результат Пэна был незначительно улучшен Трахтманом [63], который показал, что C(n) < п(7п +бп-1б)^ таким 0g разом, с учетом того, что серия Черни доставляет нижнюю оценку для функции Черни, текущее состояние проблемы можно выразить следующим двойным неравенством: n-1)*<g(n)<n(7n2+4f-16).

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

1. Первый класс, который мы рассмотрим, это класс циклических автоматов, обозначим его через cycle. Автомат называется циклическим, если одна из его букв действует на множестве состояний как циклическая перестановка. Этот класс автоматов интересен тем, что в него попадает серия автоматов Черни, соответственно, Ccycie(n) > (n — I)2. В 1998 году Дюбук [26] нашел для этих автоматов и оценку сверху, показав, что £cycie(n) < (п. — I)2. Таким образом, cycled = (rt — 1 )2.

В работе [19] Беал, Берлинков и Перрен рассматривают класс однокла-стерных автоматов - обобщение класса циклических автоматов. Автомат называется однокластерным, если он имеет "связную" букву, т. е. такую букву а € Г, что для любой пары состояний р, q € Q найдутся натуральные числа k, t такие, что pak = qаг. Граф действия этой буквы представляет собой один цикл, из которого "растут" деревья. Авторы показали, что для этого класса автоматов справедливо неравенство: cluster^ <2п2-7п + 7.

Стейнберг [60] усиливает результат Беал, Берлинкова и Перрена, показывая, что с1из1еАп)<2п2-9п+и.

Кроме того, Стейнберг доказывает, что для подкласса однокластер-ных автоматов - однокластерных автоматов с циклом простой длины -выполняется гипотеза Черни.

2. В 2003 году Кари [40] получил верхнюю оценку функции Черни для класса синхронизируемых автоматов, чей граф является эйлеровым, т.е. входящая степень каждой вершины равна исходящей. Гусев [34] в 2011 году получил нижнюю оценку функции Черни для таких автоматов. Таким образом, была доказана справедливость следующего двойного неравенства. п2 — Зп + 4 ^ ^ , ^ ^ ? -2-- Сеи1еАп) < - 3и + 3.

Для нижней оценки построен пример, на котором она достигается; вопрос точности верхней оценки остается открытым.

3. Моноидом переходов автомата = (С^, I, 6) называется моноид преобразований множества состояний порожденный действием букв алфавита 1 на этом множестве. Моноид называется апериодическим, если все его подгруппы тривиальны; автомат называется апериодическим, если его моноид переходов является апериодическим. Апериодические автоматы играют важную роль в теории формальных языков. В теории синхронизируемых автоматов этот класс интересен тем, что верхняя оценка функции Черни для него существенно отличается от нижней. Первая получена в 2007 году Трахтманом [62], вторая - в 2005 году Ананиче-вым [1,12]. Было показано, что верно следующее двойное неравенство: п-1

TL + СарегМ <

4. Рассмотрим класс автоматов с нулем, т. е. автоматов, обладающим выделенным состоянием 0, таким что 0а = 0 для любой буквы а. Обозначим этот класс через zero. Ясно, что если автомат с 0 синхронизируем, то 0 достижим из любого другого состояния автомата и, поэтому, длина синхронизирующего слова не больше суммы длин кратчайших путей из вершин автомата в 0. Следовательно, легко получается оценка сверху СгегоЫ) < (см. например, [54]). Более того, для каждого п несложно построить синхронизируемый п-автомат с нулем, имеющий п—1 букв, для которого кратчайшее синхронизирующие слово имеет длину Следовательно, п(п- 1)

-zero п) = 2

Гораздо более интересной задачей является построение серий синхронизируемых автоматов с нулем с постоянным количеством букв и квадратичной длиной синхронизирующего слова, т. е. рассмотрение класса автоматов с нулем с к символами (обозначим через zero^). Для этого класса, с учетом оценки сверху, в [9,42] доказано неравенство для функции Черни п2 п , ^ , , , ^ п(п — 1 ) + 1 < £zer02(n) < 2 \

Результат для автомата с нулем интересен тем, что ввиду того, что автоматы с нулем удовлетворяют гипотезе Черни, получение оценки сверху для любого автомата можно свести к случаю, когда граф автомата сильно-связен (см. например, [64, предложение 3]).

В главе 1 мы вводим новый класс автоматов - автоматы с буквой дефекта 2 (обозначим этот класс def2). Дефект буквы определяется стандартно как дефект отображения, порождаемого этой буквой, df(a) = = |Q| - |6(Q, а)|. Мотивацией изучения этого класса служит тот факт, что квадратичность верхней оценки функции Черни для этого класса влечет ее квадратичность для всех автоматов, или, точнее, из неравенства ^def2 — "f(n)> где f(n) - квадратичная функция, следует неравенство €(п) < 16f (тг). В главе 1 нами получены следующие нижние оценки функции Черни для описанного класса автоматов:

2}2 + 1, def2 — (n ~ 1 ) (n ~ 2), если п нечетно.

Отметим, что полученные нами в главе 1 бесконечные серии автоматов представляют самостоятельный интерес в силу того, что на текущий момент известно очень мало серий медленно синхронизируемых автоматов, т. е. автоматов с кратчайшим синхронизирующим словом длины 0(п2). Длительное время единственной известной бесконечной серией была серия Черни, кроме нее было известно только несколько отдельных медленно синхронизируемых автоматов с небольшим числом состояний [39,52,61]. В нашей работе [68] в 2007 году были описаны две первые серии автоматов, существенно отличных от серии Черни. Сравнительно недавно, в 2010 году, в работе Ананичева, Волкова и Гусева было получено еще некоторое количество бесконечных серий, а также предложен новый метод доказательства оценки длины кратчайшего синхронизирующего слова, проходящий в том числе для серии Черни и для одной из наших серий [13].

В главе 2 мы также обращаемся к автоматам, имеющим фиксированный дефект выделенной буквы. В данном случае мы рассматриваем дефект буквы, близкий к числу состояний автомата, т. е. дефект в некотором смысле экстремальный. В качестве мотивации рассмотрения этого класса отметим, что доля автоматов с большим дефектом выделенной буквы довольно существенна. В монографии [37] Хиггинс показал, что математическое ожидание дефекта отображения n-элементного множества в себя, выбранного равномерно случайно из множества всех таких отображений, стремится к j при п —> оо. Применив схожие рассуждения, можно получить, что дисперсия этого дефекта стремится к Используя неравенство Чебышева, получим, что с высокой вероятностью дефект случайного отображения (а значит и дефект буквы в случайном автомате) имеет порядок 0(п). В главе 2 нами доказано несколько нижних оценок функции Черни для автоматов с различными значениями дефекта выделенной буквы.

0.3 Синхронизируемость автоматов в среднем случае

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

Результаты вычислительных экспериментов показывают, что поведение этой величины в среднем существенно отличается от ее поведения экстремальных случаях. Скворцов и Типикин [57] с помощью вычислительного эксперимента над автоматами со 100 состояниями получили оценку средней длины кратчайшего синхронизирующего слова случайного n-автомата с двумя буквами входного алфавита, которая оказалась сублинейной, а именно равной 1,95п0'55. Кисилевич, Ковальски и Сзыку-ла [41 ] провели эксперименты над автоматами с 300 состояниями и получили оценку, приблизительно равную 2,5(п — 5)0'5.

Синхронизируемость случайных автоматов ранее не привлекала внимание исследователей, при этом, для ряда других характеристик конечных автоматов получены оценки как для всего множества автоматов, так и для почти всех автоматов4, т. е. в среднем случае. Перед тем, как привести обзор подобных результатов, дадим строгое определение случайного автомата.

Рассмотрим множество состояний Q и алфавит L. Выберем функцию переходов 5 равномерно случайно из множества функций {6 : Q х Z —> —> Q}. Получившаяся тройка (Q, Z, 6) определяет случайный (конечный детерминированный) автомат. Следует отметить, что случайный автомат может быть построен следующим образом: для каждого состояния q 6 Q и для каждой буквы a G L выбираем q' = 6(q,a) равномерно случайно из Q.

Обозначим через Л[п, к) множество всех конечных автоматов «с/ = = (Q, I, б) таких, что |Q| = п > 2, |I| = k > 1.

Пусть cji,c|2 6 Q - состояния некоторого автомата <е/ = (Q, L, б). Отклонением состояния q2 от q] называется величина d^fq^ q2), равная длине кратчайшего слова wq]>q2 £ L* такого, что q1.Wq1^q2 = q2, если оно существует, и бесконечности в противном случае. Величина d¿/ — = max dA(qt, qj) называется диаметром автомата я/, максимум берется по всем парам состояний qi} qj таким, что qj достижимо из qt.

Нетрудно видеть, что диаметр любого автомата оценивается сверху числом п—1, причем эта оценка точна. Результат впервые был сформулирован и доказан Муром в [44]. Барздинь и Коршунов показали, что верно следующее утверждение.

4Под почти всеми автоматами мы понимаем долю автоматов, стремящуюся к 1 при п —> оо.

Теорема 0.1 (Барздинь, Коршунов, 1967)

Пусть к > 2, п+к —> оо. Тогда не менее, чем |Л(п, к)|(1 — 1 /к) автоматов stf 6 Л[п} к) имеют диаметр d^, удовлетворяющий неравенствам: lognM < d^ < ci logn(k), где Cl —> 1 при n —> оо.

В [2] приводится доказательство данной теоремы при условии, что k = const > 2. В более поздней работе [7] Коршунов отмечает, что результат верен при любом к > 2.

Следующий параметр определяется для т. н. автоматов с выходом, или автоматов Мили. Напомним, что автоматом Мили называется пятерка — (Q, Z, Л, 6, Л), где Q - множество состояний, Z, Л - соответственно входной и выходной алфавиты, б : Q х £ —» Q - функция переходов, Л : Q х L —> Л - функция выходов. Иными словами, автомат Мили представляет собой конечный детерминированный автомат, в котором стрелки дополнительно подписаны буквами выходного алфавита. Аналогично множеству Д(п, к) мы будем определять множество B[riy т, к) всех автоматов Мили с п состояниями, к буквами входного алфавита и m выходного.

Степенью различимости состояний cji и q|2 автомата Мили называется величина q2), равная длине кратчайшего слова Wq,,q2 £ I* такого, что Ä(q1,"Wq])q2) ф A(q1? wq])q2), если оно существует, и бесконечности в противном случае. Величина h^ = maxh^q^ qj) называется степенью различимости автомата В, максимум берется по всем парам неэквивалентных состояний qi5 q^.

Аналогично оценке для диаметра автомата (отметим, что результат для диаметра распространяется на автоматы Мили без изменений), оценка сверху степени различимости также точна, составляет тг — 1 и описана Муром в [44].

Теорема 0.2 (Коршунов, 1967, [5])

При любых п > 2, m > 2, к>2ип + к—>оо среди всех попарно неизоморфных (по состояниям) автоматов из В[пу т, к) почти все автоматы имеют степень различимости удовлетворяющую неравенствам: lognlogm(k) <h&< [logn logm(k)] + 4.

Последний параметр, который мы рассмотрим, это длина кратчайшего однородного эксперимента по распознаванию заключительного состояния автомата Мили, т. е. длины заранее определенного слова, применение которого к автомату позволяет, исследуя выходную последовательность, определить его заключительное состояние. В современных источниках (например, [10]) эксперименты по распознаванию заключительного состояния часто называются установочными последовательностями. Обозначим эту длину через Однородные эксперименты рассматриваются на множестве #i(n,m,k) С В{n, т, к) приведенных автоматов, т.е. автоматов, все состояния которых попарно различимы.

Оценка длины эксперимента в экстремальном и среднем случаях получены соответственно Хиббардом [35] и Коршуновым [6]. Теорема 0.3 (Хиббард, 1961) Для любого автомата ЗВ Е В\ (тц т, к) u^ < n(n - 1 )/2.

Теорема 0.4 (Коршунов, 1969)

При любых т = const > 2 и n = const > 2 для почти всех автоматов ВВ € В] (п, тгц к) выполняется неравенство 5 logn к.

Отметим, что оценка Хиббарда является неулучшаемой для автоматов Мили5.

5 Результат Хиббарда может быть улучшен для автоматов Мура, отличающихся от автоматов Мили тем, что выходной буквой у них помечены не переходы, а состояния. Или, что эквивалентно, все стрелки, выходящие из одного состояния, помечены одной и той же буквой. Соответствующий результат был получен Карацубой в 1960 году [3]. Теорема 0.5 (Карацуба, 1960) Для любого приведенного автомата Мура Я? и® < (n- 1)(n- 1)/2+ 1.

Результат Коршунова справедлив как для автоматов Мили, так и для автоматов Мура.

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

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

Начиная исследования в новой области, мы поставили следующие вопросы:

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

2. Какой размер входного алфавита достаточен, чтобы почти все автоматы над алфавитом этого размера были синхронизируемы и удовлетворяли гипотезе Черни?

3. Какой размер входного алфавита достаточен, чтобы автомат над алфавитом этого размера был синхронизируем с конечной вероятностью6?

На первые два вопроса дает частичный ответ результат, полученный Хиггинсом в 1988 году [36]. Результат Хиггинса касается случайных отображений, но может быть интерпретирован в терминах конечных автоматов. Хиггинс показал, что композиция 2п случайных отображений

6Конечной мы называем вероятность, ограниченную снизу некоторой положительной константой при п —» оо. множества размера п в себя с высокой вероятностью имеет образ размерности 1. В терминах теории автоматов это означает, что случайный автомат с алфавитом размера больше 2п с высокой вероятностью синхронизируем словом длины 2тг (т. е. меньшим, чем устанавливается гипотезой Черни). В самом деле, если мы выберем автомат равномерно случайно из множества всех автоматов на п состояниях с алфавитом из 2п букв, то действие слова, составленного из всех букв алфавита, на этот автомат будет эквивалентно отображению, представляющему собой композицию 2п случайных отображений.

Мы показали, что верхняя оценка размера алфавита 2п может быть улучшена в контексте обоих вопросов. В главе 3 показано, что если размер алфавита больше 721пп, то автомат синхронизируем с высокой вероятностью (§3.2), а если алфавит состоит более чем из п1//2+е букв для некоторого положительного числа е, то с высокой вероятностью автомат удовлетворяет гипотезе Черни (§3.3). Кроме того, в главе 3 дан ответ и на третий вопрос: показано, что автомат над четырехбуквенным алфавитом синхронизируем с конечной вероятностью (§3.4).

В 2011 году Кэмерон, так же, как и Хиггинс, изучая случайные отображения, выдвинул гипотезу, что случайный автомат уже над двухбуквен-ным алфавитом синхронизируем с вероятностью 1 — о(1) при п —» оо [22]. Предположение Кэмерона полностью согласуется с результатами вычислительных экспериментов, однако остается недоказанным теоретически.

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

Основные результаты диссертации опубликованы в [67-72]. Совместные работы [69-71] с Е. С. Скворцовым выполнены в нераздельном соавторстве. Совместные работы [67,68] с Д. С. Ананичевым и М. В. Волковым содержат два независимых результата, один из которых получен автором самостоятельно, второй - в нераздельном соавторстве. Работы [67,68,70] опубликованы в изданиях, входящих в перечень утвержденных ВАК.

Ссылки на результаты диссертации присутствуют в работах других авторов: [13,21,25,53,57-60,65].

Основные результаты диссертации докладывались на следующих конференциях и семинарах:

Спутниковый семинар по словам и автоматам к международному симпозиуму "Компьютерные науки в России" \¥о\¥А'06 (Санкт-Петербург, 2006).

Международная конференция по теории формальных языков БЬТ'Об (Санта-Барбара, США, 2006).

Международная конференция "Автоматы: от математики к приложениям" Аи^МаЛА'ОЭ (Льеж, Бельгия, 2009).

Русско-финский симпозиум по дискретной математике НиРіБіМ (Санкт-Петербург, 2011).

Заседания семинара "Теоретические компьютерные науки" (УрФУ).

Заседание семинара математического факультета университета Турку (Турку, Финляндия, 2007).

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

1. Kari J. Synchronizing finite automata on eulerian digraphs // Theoret. Comput. Sci. 2003. - V. 295. - P. 223-232.

2. Kisielewicz A., Kowalski J., Szykula M. Fast algorithm finding the shortest reset words Электронная публикация] // http://arxiv.org/pdf/1203.2822.pdf

3. Martjugin P. V. A series of slowly synchronizing automata with a zero state over a small alphabet // Inform, and Comput. 2008. - V. 206. -P. 1197-1203.

4. Mateescu A., Salomaa A. Many-valued truth functions, Cerny's conjecture and road coloring // EATCS Bull. 1999. - V. 68. - P. 134-150.

5. Natarajan В. К. Some paradigms for the automated design of parts feeders I I Int. J. of Robotics Research. 1989. - V. 8. - №6. - P. 89-109.

6. Olschewski J., Ummels M. The complexity of finding reset words in finite automata // Mathematical Foundations of Computer Science, Lecture Notes in Comput. Sci. 2010. - V. 6281. - P. 568-579.

7. Papadimitriou С. H., Yannakakis M. The complexity of facets (and some facets of complexity) // J. Comput. System Sci. 1984. - V. 28(2). - P. 244-259.

8. Pin J.-E. Le probleme de la synchronisation et la conjecture de Cerny I I Non-commutative Structures in Algebra and Geometric Combinatorics Quaderni de la Ricerca Scientifica 109], CNR, Roma. 1981. - P. 37-48.

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

10. Rabin M. O., Scott D. Finite automata and their decision problems // IBM J. Res. Develop. 1959. - V. 918. - №3(2). - P.114-125.

11. Roman A. Synchronization of finite automaton. Computations for different alphabet sizes Электронная публикация] // Proc. WoWA'06, Saint-Petersburg. 2006.

12. Roman A. A note on Cerny Conjecture for automata over 3-letter alphabet // J. Automata, Languages and Combinatorics. 2008. - V. 13. - №. - R 141-143.

13. Roman A. Genetic algorithm for synchronization // Languages and Automata: Theory and Applications. LATA 2009, Lect. Notes Сотр. Sci. 2009. - V. 5457. - R 684-695.

14. Rystsov I. K. Reset words for commutative and solvable automata // Theoret. Comput. Sci. 1997. - V. 172. - R 273-279.

15. Samotij W. A note on the complexity of the problem of finding shortest synchronizing words Электронная публикация] // Proc. Int. Conf. AutoMathA'07, Palermo. 2007.

16. Sandberg S. Homing and synchronizing sequences // Model-Based Testing of Reactive Systems, Lect. Notes Comput. Sci. 2005. - V. 3472. - P. 5-33.

17. Skvortsov E., Tipikin E. Experimental study of the shortest reset word of random automata // Implementation and Application of Automata, Lect. Notes Comput. Sci. 2011. - V. 6807. - P. 290-298.

18. Steinberg B. Cerny's conjecture and group representation theory // J. Algebraic Combinatorics: An International Journal. 2010. - V. 31. -№1. - P. 83-109.

19. Steinberg B. The averaging trick and the Cerny conjecture // Int. J. of Foundations of Сотр. Sci. 2011. - V. 22. - №7. - P. 1697-1706.

20. Steinberg B. The Cerny conjecture for one-cluster automata with prime length cycle // Theoret. Comput. Sci. 2011. - V. 412(39). - P. 54875491.

21. Trahtman A. An efficient algorithm finds noticeable trends and examples concerning the Cerny conjecture // 31st Int. Symp. Math. Foundations of Comput. Sci., Lect. Notes in Comput. Sci. 2006. - V. 4162. - P. 789-800.

22. Trahtman A. The Cerny conjecture for aperiodic automata // Discrete Math. Theoret. Comput. Sci. 2007. - V.9. - №2. - P. 3-10.

23. Trahtman A. Modifying the upper bound on the length of minimal synchronizing word // Fundamentals of Computation Theory, Lect. Notes Comput. Sci. 2011. - V. 6914. - P. 173-180.

24. Volkov M. V. Synchronizing automata preserving a chain of partial ordersImplementation and Application of Automata. Proc. 12th Int. Conf. CIAA 2007, Lect. Notes Comput. Sci. 2007. - V.4783. - P.27-37.

25. Volkov M. V. Synchronizing automata and the Cerny conjecture // Languages and Automata: Theory and Applications. LATA 2008, Lect. Notes Comput. Sci. 2008. - V. 5196. - P. 11-27.

26. Wormald N. C. Differential equations for random processes and random graphs // Ann. Appl. Probab. 1995. - V. 5(4). - P. 1217-1235.Работы автора по теме диссертации

27. Ananichev D. S., Volkov М. V., Zaks Yu.I. Synchronizing automata with a letter of deficiency 2 // Developments in Language Theory, Lect. Notes Comput. Sci. 2006. - V. 4036. - P. 433-442.

28. Ananichev D. S., Volkov M. V., Zaks Yu.I. Synchronizing automata with a letter of deficiency 2 // Theoret. Comput. Sci. 2007. - V. 376. - P. 30-41.

29. Skvortsov E., Zaks Yu. Synchronizing random automata // AutoMathA'09, Proceedings; Liege. 2009. - P. 39-46].

30. Skvortsov E., Zaks Yu. Synchronizing random automata // Discr. Math. Theoret. Comput. Sci. 2010. - V. 12:4. - P. 95-108.

31. Skvortsov E., Zaks Yu. Synchronizing random automata on ^-letter alphabet // First Russian-Finnish Symposium on Discrete Mathematics, Abstracts. 2011. - P. 62-63.

32. Закс Ю. И. Синхронизация конечных автоматов с буквой большого дефекта Гуманитарный ун-т. - Екатеринбург, 2012. - Деп. в ВИНИТИ 17.04.2012, М54-В2012.