WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

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

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

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

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

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

Челябинск 2012

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

Научный ВОЛКОВ Михаил Владимирович руководитель: доктор физ.-мат. наук, профессор зав. кафедрой алгебры и дискретной математики, ФГАОУ ВПО Уральский федеральный университет имени первого Президента России Б. Н. Ельцина Официальные РОЖКОВ Александр Викторович оппоненты: доктор физ.-мат. наук, профессор профессор кафедры цифровых радиотехнических систем, ФГБОУ ВПО Южно-Уральский государственный университет (национальный исследовательский университет) РАЙГОРОДСКИЙ Андрей Михайлович доктор физ.-мат. наук, профессор профессор кафедры математической статистики и случайных процессов, ФГБОУ ВПО Московский государственный университет имени М. В. Ломоносова Ведущая Федеральное государственное бюджетное учреждение науки организация: Институт математики имени С. Л. Соболева Сибирского отделения Российской академии наук (ИМ СО РАН) (г. Новосибирск)

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

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

Автореферат разослан “ ” мая 2012 года.

Ученый секретарь диссертационного совета М. Л. Цымблер

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

Актуальность темы. Работа посвящена исследованиям в бурно развивающейся области теоретической информатики – теории синхронизируемых конечных детерминированных автоматов. Детерминированным конечным автоматом или просто автоматом называется тройка объектов A = (Q, , ), где Q – конечное множество состояний, – конечный входной алфавит, : Q Q – всюду определенная функция переходов автомата. Функция переходов естественным образом продолжается до отображения (также обозначаемого через ) из Q в Q, где через , как обычно, обозначается множество всех слов над алфавитом .

Автомат A = (Q, , ) называется синхронизируемым, если существует слово w , переводящее его в состояние, зависящее только от слова w и не зависящее от того состояния автомата, в котором w было применено. В символах это свойство выражается равенством (p, w) = (q, w) для всех p, q Q. Любое слово с таким свойством называется синхронизирующим для автомата A.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Семинар по словам и автоматам в составе международного симпозиума “Компьютерные науки в России” WoWA’06 (8 июня 2011 г., г. СанктПетербург).

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

• Международная конференция “Автоматы: от математики к приложениям” AutoMathA’09 (8–12 июня 2009 г., г. Льеж, Бельгия).

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

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

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

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

Библиографический список содержит 72 наименования.

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

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

Пусть A = (Q, , ) – автомат с |Q| 3. Если буква a такова, что преобразование множества состояний Q, порождаемое действием a, имеет дефект 2, то возможны в точности две следующие ситуации.

1. Существует четыре различных состояния q1, q2, q3, q4 Q такие, что (q1, a) = (q2, a) = (q3, a) = (q4, a).

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

2. Существует три различных состояния q1, q2, q3 Q такие, что (q1, a) = (q2, a) = (q3, a).

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

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

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

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

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

b b a a 1 a b b 2 b a a Рис. 2: Автомат BОтметим, что в теореме 1.1 ограничение на четность существенно.

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

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

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

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

n-a, b a, b Рис. 3: Автомат Dn результаты численных экспериментов, в которых были найдены автоматы с 5 и 6 состояниями и буквой-дромадером, у которых длины кратчайших синхронизирующих слов на единицу больше чем длины кратчайших синхронизирующих слов у соответствующих автоматов из серии Dn.

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

Пусть A = (Q, , ) – автомат с |Q| 3. Если буква a такова, что существуют число k 3 и состояния q1, q2,..., qk Q такие, что (q1, a) = (q2, a) =... = (qk, a), то будем называть эту букву k-веерной, или, без указания k, просто веерной. Коэффициент k будем называть веерностью буквы a. Дефект k-веерной буквы превосходит k.

Заметим, что определенная выше буква-дромадер является 3-веерной.

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

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

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

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

a b b b b...

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

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

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

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

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

Теорема 3.3. Пусть A = (Q, , ) – случайный автомат такой, что |Q| = n, || 72 ln n. Тогда A синхронизируем с высокой вероятностью. Более того, длина кратчайшего синхронизирующего слова этого автомата с высокой вероятностью меньше чем 3n2 ln n.

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

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

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

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

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

Лемма 3.11. Пусть A = (Q, {a, b}, ) – случайный автомат над двухбуквенным алфавитом, x Q. Тогда существует константа r, 0 < r < < 1, такая, что для достаточно больших n вероятность того, что для каждого состояния q Q существует слово wqx {a, b}, удовлетворяющее условию qwqx = x, больше r.

Лемма 3.12. Пусть A = (Q, , ) – случайный автомат такой, что |Q| = n, || = n, > 0.5. Пусть 1, 2 – случайная пара множеств таких, что 1 2, 1 2 = , |1| = |2| = n для действительного числа такого, что 0.5 < < . Тогда с высокой вероятностью множество троек (a, b, q), a 1, b 2, для которых выполняется qa = qb = q, (1) содержит более n2-1/2 элементов.

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

В доказательстве леммы 3.11, также как и в доказательстве теоремы 3.3, используется некоторый алгоритм на графе. Мы рассматриваем алгоритм, который на каждом шаге либо находит новое состояние q Q, для которого существует слово wqx {a, b}, либо завершается неуспехом. Для данного алгоритма мы оцениваем вероятность того, что он проработает n - 1 шаг. Оценка данной вероятности разбивается на три этапа, на каждом из которых используется своя техника доказательства:

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

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

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

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

В §3.4 мы наоборот смягчаем условия и ставим следующий вопрос:

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

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

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

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

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

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

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

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

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

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

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

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

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

4. Adler R.L., Goodwyn L.W., Weiss B. Equivalence of topological Markov shifts // Israel 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 Foundations of Computer Science, Lect.

Notes Comput. Sci. – 2010. – V. 6281. – P. 55–64.

6. Biskup M.T., Plandowski W. Shortest synchronizing strings for 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. ern J. Poznmka k homognnym eksperimentom s konenmi automatami // Mat.-Fyz. as. 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. Frettlh D., 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, ern’s conjecture and road coloring // Bull. European Assoc. Theoret. Comput. Sci. – 1999. – V. 68. – P. 134–150.

16. Natarajan B. 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 B. 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, SaintPetersburg. – 2006.

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

20. Roman A. Genetic algorithm for synchronization // Languages and Automata: Theory and Applications. LATA 2009, Lect. Notes Comp. Sci. – 2009. – V. 5457. – P. 684–695.

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

5–33.

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

23. Steinberg B. Cerny’s conjecture and group representation theory // J. Algebraic Combinatorics. – 2010. – V. 31. – №1. – P. 83–109.

24. Steinberg B. The averaging trick and the ern conjecture // Int. J.

Foundations Comput. Sci. – 2011. – V. 22. – №7. – P. 1697–1706.

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

5487–5491.

26. Trahtman A. An efficient algorithm finds noticeable trends and examples concerning the ern conjecture // Mathematical Foundations of Computer Science. Lect. Notes Comput. Sci. – 2006. – V. 4162. – P. 789–800.

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

28. Volkov M. V. Synchronizing automata and the ern conjecture // Languages and Automata: Theory and Applications. Lect. Notes Comput. Sci.

– 2008. – V. 5196. – P. 11–27.

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

Работы автора по теме диссертации Статьи, опубликованные в журналах из списка ВАК 30. Ananichev D. S., Volkov M. 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.

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

32. Skvortsov E., Zaks Yu. Synchronizing random automata // Discr.

Math. Theoret. Comput. Sci. – 2010. – V. 12. – №4. – P. 95–108.

Другие публикации 33. Skvortsov E., Zaks Yu. Synchronizing random automata // AutoMathA’09, 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.






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.