Содержание 1
Введение 3
Глава 1. Определения 5
Модели двусторонних автоматов 5
Подфункции булевой функции 9
Глава 2. Матричное представление двусторонних автоматов 11
Представление детерминированного двустороннего автомата 12
Представление недетерминированного двустороннего автомата 13
Представление вероятностного двустороннего автомата 15
Мера близости матриц 17
Глава 3. Необходимые условия вычислимости булевой функции автоматом 18
Необходимые условия для детерминированной и недетерминированной моделей 18
Необходимое условие для вероятностной модели 19
Глава 4. Булевы функции 2-SAFwи 2-USAFw, их свойства 21
Глава 5. Иерархии двусторонних автоматов 28
Иерархия для двусторонних детерминированных автоматов 28
Иерархия для двусторонних недетерминированных автоматов 29
Иерархия для двусторонних вероятностных автоматов 30
Заключение
Список литературы
Модель двусторонних автоматов была введена Рабином М. О. и Скоттом Д. в работах [1, 2]. Для этой модели известно, что она распознает в точности регулярные языки [2]. Вопрос об отношении классов языков, распознаваемых авто-матами разного размера, также рассматривался уже давно. К примеру, Sakoda и Sipser в работе [3] показали, что любой 2КНА может быть смоделирован 2КДА экспоненциального размера. В работе [4] приводится обзор результатов, полученных для отношения классов языков, распознаваемых вероятностными авто-матами за полиномиальное и экспоненциальное время.
Кроме того, двусторонние автоматы моделировались односторонними и лучшие варианты был в работах [5, 6]. Исследователи улучшали оценки только для модифицированных моделей [7, 8, 9, 10].
В данной работе будет рассмотрена иерархия двусторонних автоматов по ширине (количеству состояний), таким образом, для входных слов разной длины наши модели могут иметь различное количество состояний. Поэтому мы определяем автомат для фиксированного положительного n(длина входа).
Будем рассматривать двоичный алфавит S = {0,1g и использовать терминологию ветвящихся программ: вместо распознавания языков решается задача вычисления булевой функции. Таким образом, автомат вычисляет некоторую функцию и должен принимать входные слова, на которых функция принимает значение "истина" и отвергать входы, для которых значение функции "ложь".
В работе используется и модифицируется матричная техника представления вычисления булевых функций в автоматных протоколах, представленная в [11]. Используя коммуникационный подход, классический вариант которого определен Яо в 1979 году [12], получены иерархии как для классических двусторонних автоматов (детерминированных и недетерминированных), так и для неоднородной модели вероятностного двустороннего автомата. С одной стороны, такая модель является близкой к модели OBDD,а с другой — вбирает специфику автоматов. Детальная информация о коммуникационных вычислениях может быть найдена в работах [13, 14].
В первой главе данной работы представлены определения рассматриваемых моделей. Во второй главе описана матричная техника представления двусторонних автоматов. В третьей главе приведены необходимые условия вычислимости булевых функций двусторонними автоматами. В четвертой главе построены булевы функции, при помощи которых получены иерархии в пятой главе.
Результаты работы были представлены на IX Международной конференции "Дискретные модели в теории управляющих систем" (Москва, 2015 г.), X молодежной научной школе по дискретной математике и ее приложениям (Москва, 2015 г.). Так же доклад принят на Двенадцатый Международный научный семинар "Дискретная математика и ее приложения" (Москва, 20-25 июня 2016 г.). Тезисы вошли в сборники [15, 16].
В данной работе исследованы известные модели — двусторонние детерминированные и недетерминированные автоматы. Также была введена модель двусторонних вероятностных автоматов с переменной структурой. Полученные результаты являются естественным продолжением и дополнением предыдущих работ, посвященных иерархиям двусторонних автоматов с переменной структурой.
В главе 2 рассмотрена техника матричного представления работы двусторонних автоматов, основанная на идеях коммуникационных вычислений. Также в этой главе введена мера близости матриц, которая позволяет перейти от бесконечного множества матриц с вещественными элементами к конечному множеству классов эквивалентности матриц.
В главе 3 получены необходимые условия вычислимости булевых функций двусторонними автоматами, основанные на оценке числа подфункций для булевой функции. Для получения необходимого условия для вероятностной модели, была развита специальная техника, которая позволяет разделить множество матриц на классы эквивалентности, оценить количество полученных классов.
В главе 4 построена булева функция, отличительной особенностью которой является относительно большое количество подфункций. При этом построен двусторонний детерминированный автомат с небольшим числом состояний, вычисляющий построенную функцию. Таким образом, получен элемент, который служит разделителем для построения иерархии двусторонних автоматов.
В главе 5 при помощи коммуникационного подхода и результатов, полученных в предыдущих главах, построены иерархии классов сложности по количеству состояний для двусторонних детерминированных и недетерминированных автоматов. Кроме того, построена иерархия для двусторонних вероятностных автоматов с переменной структурой. Заметим, что ранее иерархии по количеству состояний для этих моделей не были известны.
Развитием полученных результатов могут стать исследования в следующих направлениях:
- получение иерархии классов языков, распознаваемых двусторонними вероятностными автоматами с переменной структурой;
- получение иерархии классов унарных языков, распознаваемых двусторонними автоматами с переменной структурой.
