Экстремальные конструкции в теории синхронизируемых автоматов

• Автор: Гусев, Владимир Валерьевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Екатеринбург
• Количество страниц: 91 с. : ил.

Содержание
Введение
0.1 Синхронизируемые автоматы и гипотеза Черни
0.2 Апробация результатов
0.3 Предварительные сведения
1 Примитивные орграфы с большими
экспонентами и медленно синхронизируемые автоматы
1.1 Постановка задачи и структура главы
1.2 Методика и некоторые результаты эксперимента
1.3 Примитивные орграфы и их экспоненты
1.4 Серии медленно синхронизируемых автоматов
1.5 Обсуждение и гипотезы
2 Медленно синхронизируемые
эйлеровы автоматы
2.1 Введение
2.2 Предварительные сведения
2.3 Основные результаты
3 Синхронизация автоматов
ограниченного ранга
3.1 Введение
3.2 Предварительные сведения
3.3 Основные результаты
3.4 Заключение и обсуждение
4 Непокрывающие множества и гипотеза
Рестиво
4.1 Введение
4.2 Множество 5*
4.3 Верхняя оценка на величину ти1(3к)
4.4 Нижняя оценка на величину ши1(3к)
4.5 Заключение
Список литературы

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

ра при чтении входного символа не только переходит в новое состояние д, но также выводит символ 7(д). Для Мура такой автомат служил прежде всего моделью некоторого дискретно работающего устройства. Поэтому естественный вопрос, который интересовал Мура, состоит в следующем. Если контроль над устройством потерян, то как вернуть контроль над ним? Иначе говоря, какую последовательность сигналов нужно подать на вход устройства, чтобы по наблюдаемым выходным сигналам однозначно определить его текущее состояние? В работе [31] такая последовательность называлась экспериментом. Отметим, что эксперименты Мура были адаптивными, т.е. всякая следующая буква, зависела от уже полученной выходной строки. В работе Мура уделяется большое внимание оценке длины кратчайшего эксперимента в терминах числа состояний. С практической точки зрения длина эксперимента определяет насколько быстро можно вернуть контроль над устройством. В своей работе [31] Мур показал, что длина кратчайшего эксперимента для автомата с п состояниями не превосходит п^п~1'>. Вскоре Карацуба [2], будучи еще
(п—1)(го—2) ,
студентом, улучшил этот результат, получив точную оценку 1^---------- + 1.
Следующим важным этапом стала работа Гинзбурга [22], написанная в 1958 году. Он рассмотрел особый вид экспериментов, которые были названы однородными. В таких экспериментах входная последовательность не зависит от порождаемой выходной строки, т.е. является фиксированной. Выходная последовательность в однородных экспериментах используется для определения заключительного состояния автомата после проведения эксперимента.
Заключительный шаг к главному понятию данной диссертации был сделан Черни [15] в 1964 году. Мы остановимся на его результатах подробнее. Черни исследовал следующий вопрос: если автомат не имеет выходной функции, то как определить его текущее состояние? Пусть некоторый автомат ,с/ имеет множество состояний С}, входной алфавит £ и функцию перехода 5. Через 6(д, т), или д ■ ю, если 6 ясна из контекста, обозначим состояние, в которое переходит автомат из состояния д после чтения слова м. Автомат ^ называется синхронизируемым, если найдется слово ги над алфавитом £, под действием которого все состояния переходят в одно: д ■ ъи = д' • и> для всех д, д' е <5- Всякое такое слово го называется синхронизирующим для ^. Таким образом, если исходное состояние автомата неизвестно, то после прочтения синхронизирующего слова состояние автомата будет однозначно определено. Минимум длин

Положим с = а2, тогда слово ги может быть переписано в слово V над алфавитом {Ь, с}. Действия Ъ и с на множестве {1,2,..., тг} определяют автомат, изображенный на рис. 13 справа. Поскольку слова ги и V действуют на множестве {1,2,... ,п} одинаково, слово у является синхронизирующим для этого автомата, а значит, и для его подавтомата с множеством состояний {1,3, ...,п} Легко видеть, что этот подавтомат изоморфен автомату с£п~. По теореме 1.3 длина V как слова над {Ь, с} не меньше (га — 2)2 и V содержит по меньшей мере п — 2 вхождения с. Поскольку каждое вхождение с в у отвечает вхождению фактора а2 в ги, мы можем заключить, что слово ги имеет длину не меньше (га — 2)2 + (га — 2) = га2 — Зга + 2. □
Доказательство теоремы 1.4 показывает, что автомат §п возникает из одной из той «тривиальных» модификаций автомата ггоп-, которые мы обсудили в п. 4.1. Последняя серия медленно синхронизируемых автоматов из семейства автоматов, связанных с орграфом №п, возникает из аналогичной модификации автомата . Она состоит из автоматов Жп =({1,2,.. , га}, {а, Ь}, 5), где буквы а и Ь действуют следующим образом:
если г = 1, I г + 1, если г < га — 1,
если 1 < г < п, 6(г, Ь) = < 1, если г — п — 1,
если г = га; {3, если г = га.
Автомат Жп изображен на рис. 14 слева.

Рис. 14: Автомат Жг и автомат, определяемый действиями слов 6 и с = аЬ