Содержание к диссертации
Введение
1 Коммуникационное моделирование &-OBDD 11
1.1 Детерминированная модель 11
1.1.1 Нижние оценки 11
1.1.2 Доказательство теоремы 1.1.3 14
1.1.3 Иерархия классов сложности 23
1.2 Недетерминированная модель 31
1.2.1 Нижние оценки 31
1.2.2 Доказательство теоремы 1.2.1 32
1.2.3 Иерархия классов сложности 39
1.3 Вероятностная модель 40
1.3.1 Нижние оценки 40
1.3.2 Доказательство теоремы 1.3.1 42
1.3.3 Иерархия классов сложности 56
1.4 к раз читающие забывающие ветвящиеся программы 58
1.4.1 Определения 58
1.4.2 Детерминированная модель "малой" ширины 60
1.4.3 Недетерминированная модель "малой" ширины 68
1.4.4 Вероятностная модель "малой" ширины 72
2 Иерархия по ширине для 1-OBDD и &-OBDD 77
2.1 Иерархия для OBDD "малой" ширины 77
2.1.1 Доказательство теоремы 2.1.1 78
2.1.2 Доказательство теоремы 2.1.4 79
2.2 Иерархия для OBDD "большой" ширины з
2.2.1 Доказательство теоремы 2.2.4 86
2.2.2 Сравнение результатов для "малой" и "большой" ширины 88
2.3 К раз читающие забывающие ветвящиеся программы. Иерархия по ширине 88
2.3.1 Детерминированная модель 88
2.3.2 Недетерминированная модель 89
2.3.3 Вероятностная модель 91
3 Двухсторонние автоматы с переменной структурой 94
3.1 Определения 94
3.2 Детерминированный двухсторонний автомат с переменной структурой 99
3.2.1 Нижняя оценка для 2DAn и 2DA 100
3.2.2 Иерархия классов сложности 102
3.3 Недетерминированный двухсторонний автомат с переменной структурой 111
3.3.1 Нижняя оценка для 2NAn и 2NA 111
3.3.2 Иерархия классов сложности 113
4 Функциональное представление &-OBDD 116
4.1 Теорема об иерархии 116
4.2 Эмуляция k-OBDD с помощью NOBDD 119
4.3 Доказательство теоремы 4.1.1 121
4.4 Ограничения метода 125
Заключение 126
Список литературы 1
- Иерархия классов сложности
- Доказательство теоремы 2.1.4
- К раз читающие забывающие ветвящиеся программы. Иерархия по ширине
- Эмуляция k-OBDD с помощью NOBDD
Введение к работе
Актуальность темы исследования. Анализ и классификация алгоритмов с точки зрения вычислительной сложности является одним из основных аспектов для понимания внутренней природы задачи и алгоритма ее решения. Центральным аппаратом такого анализа алгоритмов являются нижние оценки сложности.
Важной известной проблемой является соотношение классов Р и NP. При этом остается много открытых вопросов о структуре класса P. И, в частности, известных классов LSPACE и NC, входящих в класс P. Во второй половине прошлого века были введены различные модели вычислений с разными вариантами ограничений, которые позволяли решать ряд вопросов для классификации сложности, к таким моделям относятся ветвящиеся программы. Для них было доказано, что LSPACE /poly = ВР, где LSPACE /poly — это неоднородный класс сложности для машины Тю-ринга, использующей логарифмическую память и подсказку не более, чем полиномиального размера, а ВР — класс булевых функций, вычислимых ветвящимися программами полиномиальной сложности. Кроме того, было доказано, что NC1 = BPconst, где класс NC1 — это класс булевых функций, вычислимых схемами из функциональных элементов логарифмической глубины (NC1 С NC), а BPconst — класс булевых функций, вычислимых ветвящимися программами полиномиальной сложности константной ширины.
Начиная с 90-х годов интенсивно исследовалась сложность реализации булевых функций, входящих в класс BPconst. Для целого ряда моделей ветвящихся программ были доказаны нижние оценки сложности реализации в них булевых функций, и на основе этих оценок построены иерархии сложности.
Большие усилия были направлены на исследования моделей ветвящихся программ с ограничением на количество считываний переменных. Для модели к раз читающих недетерминированных ветвящихся программ (&-NBP)
в 1993 году Бородиным и соавторами [3] были получены нижние оценки для явно заданной функции, показывающие необходимость экспоненциального размера программы для малых к. Авторы рассмотрели “синтаксическую” модель, для которой ограничение на количество считывания вводится для любого пути от начальной вершины до финальных, и “семантическую”, для которой ограничения вводились только на вычислительных путях. Оценка была получена для “синтаксической” модели.
Техника, использованная в [3], основывалась на представлении функ
ции в виде булевой формулы специального вида. Таким образом про
цесс вычислений был описан функционально.
В недетерминированном случае рассматривалась более общая модель к-BP, для которой были доказаны нижние оценки в работах Окольнишнико-вой [5]. В 1997 году она доказала нижнюю оценку сложности для недетерминированной к-BP для явно заданной булевой функции fkink/2+c, показав, что эта функция требует экспоненциального размера для вычисления в &-BP. На основе этой оценки была доказана иерархия классов булевых функций, вычислимых недетерминированными &-BP полиномиального размера: NP-&BP С NP-(&ln&/2 + С)BP. Данная иерархия справедлива для к = о(л/1пп/1п1пп).
Техника, использованная Окольнишниковой, схожа с техникой, кото
рую использовали Бородин и соавторы в работе [3]. Она основывалась
на представлении функции в виде булевой формулы специального вида
и анализе этой формулы.
Оценку Окольнишниковой улучшил Татачар [6] в 1998 году, доказав нижнюю оценку для функции HSPq+l. Он показал, что недетерминированная &-BP, вычисляющая эту функцию, должна иметь ширину не менее ехр{п1'к+12~2кк~4}, используя этот результат доказал иерархию классов сложности: NP-(& — 1)BP С NP-&BP. Таким образом, была доказана более
строгая иерархия по сравнению с результатами Окольнишниковой. Данная иерархия справедлива для к = o(loglogn).
Автор в своей работе использовал модификацию метода, основанного
на коммуникационных протоколах.
Позже Айтаи [1] в 2005 году доказал нижнюю оценку для более общей модели: ветвящихся программ без ограничений, показав, что функция N+(XV) не может быть вычислена ветвящейся программой длины кп, для к = const и размера менее, чем 2ПЄ, где є > 0.
Автор в своей работе использовал как модификацию метода, основан
ного на коммуникационных протоколах, так и функциональный под
ход.
В вероятностном случае для к-BP Хромкович и Заурхов [4] в 2003 году, доказали нижнюю оценку для функции т — Masked — PJk,n. Таким образом, они показали, что вероятностная к-BP с (0.5 — ^-изолированной точкой сечения, вычисляющая эту функцию, должна иметь размер не менее 2^{Na/k ), где а _ \j(\ _|_ 21одЗ). На основе полученного результата авторы доказали иерархию классов сложности: BPP-(& —1)BP С BPP-&BP. Данная иерархия справедлива для к < logn/3.
Авторы в своей работе использовали метод, аналогичный тому, кото
рый использовал Татачар в работе [6].
Наиболее исследованной моделью ветвящихся программ является один раз читающая ветвящаяся программа — ветвящаяся программа с тем ограничением, что на каждом вычислительном пути каждая переменная встречается не более одного раза. Другое естественное ограничение — “забывание”, которое требует, чтобы считывание переменных происходило в соответствии с фиксированным порядком. Забывающие один раз читающие ветвящиеся программы (используемые при тестировании сверхбольших интегральных схем) называются упорядоченными бинарными диаграммами
решений (Ordered Binary Decision Diagrams, сокращенно OBDD). Обобщением OBDD является к раз читающие OBDD (k-OBDD). Модели &-OBDD (к > 1) имеют широкое практическое применение в тестировании СБИС, а также при построении ^-проходных потоковых алгоритмов, используемых при обработке больших объемов данных, поэтому важным вопросом является построение иерархий классов сложности булевых функций, реализуемых в этих моделях по параметру к. Неформально можно сказать, что построение иерархий отвечает на вопрос: “сможет ли модель &-OBDD решить задачу, если ей дать больше времени?”.
Заметим, что &-OBDD является “синтаксической”.
Для &-OBDD Боллинг и соавторы [2] в 1998 доказали нижнюю оценку для булевой функции PJk (Pointer Jumping): для (к — l)-OBDD, вычисляющей функцию PJk, требуется размер не менее 2^п 'к>. На основе этой оценки была доказана иерархия классов булевых функций, вычислимых к-OBDD полиномиального размера (или, что в данном случае тоже самое, полиномиальной ширины): P-(к — l)OBDD С P-;OBDD. Данная иерархия справедлива для к = o{nl'2log^'2n).
Авторы в своей работе применили метод моделирования работы к-OBDD в коммуникационных протоколах.
Исследования диссертационной работы посвящены уточнению иерархии классов сложности &-OBDD.
Цель работы. Развитие техники доказательства нижних оценок сложности для классов булевых функций, вычислимых моделями ветвящихся программ и двухсторонними автоматами с переменной структурой. На основании разработанных нижних оценок построение иерархий классов сложности &-OBDD, уточняющих уже существующие иерархии.
Методы исследований. В работе используются методы дискретной математики, математической кибернетики, теории вероятностей и теории чисел.
Научная новизна. В диссертации рассмотрены две техники доказательства нижних оценок: “Коммуникационное моделирование &-OBDD” и “Функциональное описание &-OBDD”. Эти две техники взаимно дополняют друг -друга. Получены следующие новые результаты:
1. “Коммуникационное моделирование &-OBDD” — это подход, использующий представление &-OBDD в виде специального коммуникационного вычислителя. Этот подход позволил уточнить оценки числа подфункций N(f) для булевых функций /, реализуемых в &-OBDD.
Это уточнение позволяет доказать новые оценки сложности вычисления булевых функций в детерминированной, недетерминированной и вероятностной &-OBDD (&-OBDD, &-NOBDD, &-POBDD).
На основе установленных нижних оценок для N(f) доказаны следующие уточнения иерархий для детерминированной, недетерминированной и вероятностной &-OBDD для константной, полилогарифмической и сублинейной ширины.
На основе анализа числа N(f) для некоторых явно заданных функций / получены нижние оценки сложности детерминированной и недетерминированной OBDD, вычисляющей /. Это позволило построить иерархии по ширине для классов булевых функций, вычислимых OBDD и NOBDD, а также отношения между классами для разных моделей.
В частности, предложен подход, позволяющий получить новые результаты для детерминированных и недетерминированных двухсторонних автоматов с переменной структурой.
Доказаны нижние оценки для характеристических функций языков, вычислимых детерминированными и недетерминированными двухсторонними автоматами с переменной структурой.
Построены иерархии классов булевых функций, которые являются характеристическими для языков, вычислимых детерминированными и недетерминированными двухсторонними автоматами с переменной структурой. Иерархии базируются на доказанных нижних оценках.
Ограничение подхода “коммуникационного моделирования &-OBDD” состоит в следующем: kw log w < п для детерминированного случая и kw2 < п для недетерминированного и вероятностного случаев, где w — ширина &-OBDD. То есть, он подходит только для моделей менее, чем линейной ширины.
2. “Функциональное описание &-OBDD” — это функциональный подход для анализа вычислительных процессов в &-OBDD и &-NOBDD. Этот подход, во-первых, позволяет моделировать процесс вычисления в к-OBDD с помощью недетерминированной OBDD. Во-вторых, он позволяет описать функцию /, вычислимую &-OBDD (недетерминированной &-OBDD) в виде булевой формулы специального вида.
На основе функционального представления процесса вычисления получена нижняя оценка для некоторых явно заданных функций /, вычислимых в детерминированной и недетерминированной к-OBDD.
На основе этого подхода доказаны уточнения иерархий для детерминированной и недетерминированной &-OBDD полиномиальной, суперполиномиальной и субэкспоненциальной ширины.
Техника “Коммуникационного моделирования &-OBDD” является обобщением идей, представленных в работах [2], [4], [6]. Техника “Функциональ-
ное описание k-OBDD” является обобщением идей, представленных в работах [3], [5].
Теоретическая и практическая значимость. Диссертация носит теоретический характер и посвящена исследованиям в области сложности детерминированных, недетерминированных и вероятностных моделей вычислений. Предложенные подходы и разработанные методы могут найти применение при анализе сложности задач и алгоритмов в различных моделях.
Апробация работы. Результаты диссертации были представлены на российских и международных конференциях и семинарах: X международном семинаре “Дискретная математика и ее приложения” (Москва, 2010 г.), XI международном семинаре “Дискретная математика и ее приложения”, посвященный 80-летию со дня рождения академика О. Б. Лупанова (Москва, 2012 г.), на XVII международной конференции “Проблемы теоретической кибернетики”. (Казань, 2014 г.), на конференции “6th Workshop on Non-Classical Models of Automata and Applications NCMA 2014” (Германия, Кас-сель, 2014 г.), на конференции “16th International Workshop on Descriptional Complexity of Formal Systems” (Финляндия, Турку 2014), на итоговых конференциях Казанского федерального университета и на семинарах по классическим и квантовым вычислениям Казанского федерального университета.
Публикации. По теме диссертации опубликовано 10 работ, в том числе 3 – в журналах, входящих в перечень ВАК.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы из 45 наименований, включая работы автора. Объем диссертации составляет 135 страниц машинописного
Иерархия классов сложности
Наиболее исследованной моделью ветвящейся программы является один раз читающая ветвящаяся программа - это ветвящаяся программа с тем ограничением, что на каждом вычислительном пути каждая переменная встречается не более одного раза. Другое естественное ограничение — "забывание", которое требует чтобы считывание переменных происходило в соответствии с фиксированным порядком. Забывающие один раз читающие ветвящиеся программы называются упорядоченными бинарными диаграммами решений (Ordered Binary Decision Diagrams, сокращенно OBDD). Обобщением OBDD является к раз читающие OBDD (&-OBDD). Поскольку модели &-OBDD (к 1) имеют широкое практическое применение в тестировании СБИС, то важным вопросом является построение иерархий классов сложности булевых функций, реализуемых в этих моделях по параметру к. Неформально можно сказать, что построение иерархий отвечает на вопрос: "сможет ли модель OBDD решить задачу если ей дать больше времени?". Заметим что &-OBDD является "синтаксической". Для &-OBDD Боллинг и соавторы [14] в 1998 доказали нижнюю оценку для булевой функции PJk {Pointer Jumping): (к — l)-OBDD вычисляет функцию Р Jk используя 2п уП / состояний. На основе этой оценки была доказана иерар хия классов булевых функций, вычислимых &-OBDD полиномиального размера (или что в данном случае тоже самое полиномиальной ширины): В-(к — l)OBDD С P-;OBDD. Данная иерархия справедлива для к = о(п п).
Авторы в своей работе использовали метод моделирования работы к OBDD в коммуникационных протоколах. В работе определяются коммуникационные вычисления булевых функций с автоматной памятью. На основе развитой в работе матричной техники представления вычисления в автоматных протоколах доказывается нижняя оценка сложности вычисления булевых функций в автоматных протоколах. Классический вариант коммуникационного вычисления булевой функции с участием двух игроков Alice и Bob (two-party computation) в 1979 году определил Яо [44]. Подробная информация о различных аспектах коммуникационных вычислений булевых функций представлена в книгах [22,34].
В работе показывается, что вычисление функции в (2к — 1)-раундовом в автоматном коммуникационном протоколе соответствует вычислению в &-OBDD моделе ветвящейся программы. Благодаря коммуникационной технике получены иерархии классов булевых функций, распознаваемых &-OBDD, &-NOBDD и &-POBDD "малой" ширины (менее чем линейная) по параметру к. С помощью второй группы нижних оценок, основанной на методе функционального представления &-NOBDD большей ширины, удалось получить иерархию для &-OBDD, &-NOBDD "большой" ширины(полиномиальной, суперполиномиальной, субэкспоненциальной).
Кроме того используя коммуникационный подход для &-OBDD, &-NOBDD и &-POBDD "малой" ширины получены, иерархии по ширине. А также получены иерархии для OBDD и NOBDD по ширине для случаев "большой" и "малой" ширины. Коммуникационный подход применен также и для двухсторонних автоматов с переменной структурой, детерминированного и недетерминированного случая.
Основные результаты диссертации в области получения нижних оценок и построения иерархий ветвящихся программ и двухсторонних автоматов с переменной структурой:
В главе 1 рассмотрен метод "коммуникационного моделирования &-OBDD", Это подход представления &-OBDD в виде специального коммуникационного вычислителя. В данной главе рассматриваются детерминированная, недетерминированная и вероятностные модели. В данной главе для коммуникационных протоколов построены иерархии классов сложности по количеству раундов.
Далее нижние оценки коммуникационной модели переложены на модели к-OBDD и для детерминированная, недетерминированная и вероятностные "малой" ширины получены, иерархии по параметру к.
В главе 2 полученные нижние оценки для OBDD основанные на анализе количества подфункций. Что позволило построить иерархию для OBDD и недетерминированной OBDD по ширине. Кроме того установлено как соотносятся различные модели.
С помощью коммуникационного подхода для &-OBDD, &-NOBDD и к-POBDD "малой" ширины получены, иерархии по ширине. В главе 3 нижние оценки полученные для коммуникационных протоколов применяются к двухсторонним автоматам с переменной структурой, в результате чего получены иерархии по количеству состояний для детерминированного и недетерминированного случая. В главе 4 предложен функциональный подход для анализа вычислительных процессов в &-OBDD и &-NOBDD. Подход позволяет моделировать процесс вычисления в &-OBDD с помощью недетерминированной OBDD большего размера. На основе этого подхода доказаны уточнения иерархий для детерминированной и недетерминированной &-OBDD полиномиальной, суперполиномиальной и субэкспоненциальной ширины.
Результаты диссертации представлены в работах [1], [2], [3], [5], [4], [10], [9], [31], [32] а также на X международном семинаре "Дискретная математика и ее приложения" (Москва, 2010 г.), XI международном семинаре "Дискретная математика и ее приложения" посвященный 80-летию со дня рождения академика О. Б. Лупанов(Москва, 2012 г.), на XVII международной конференции Проблемы теоретической кибернетики. (Казань, 2014 г.), на 6th Workshop on Non-Classical Models of Automata and Applications NCMA 2014 (Германия, Кассель, 2014 г.), на 16th International Workshop on Descriptional Complexity of Formal Systems
Доказательство теоремы 2.1.4
Введем определения моделей, которые будут рассматриваться в этой главе. Мы рассматриваем модель ветвящейся программы (ВР — branching program). Определения в этом разделе даны в соответствии с книгой Инго Ве-генера [42]. Ветвящаяся программа над множеством переменных X = {xi,... ,жп} - это ориентированный ациклический граф, который в том числе имеет две различные вершины s (начальная вершина) и t (финальная вершина). Мы будем обозначать ее Psj или просто Р. С каждой внутренней вершиной связана булева переменная х Є X и из нее исходят два ребра, помеченных х = 0 и х = 1 соответственно.
Программа Р над множеством переменных X представляет (вычисляет) булеву функцию f(X) (/ : {0,1}п — {0,1}) следующим образом. Вычисление значения f(y) для входного набора v Є {0,1}п начинается из вершины s. Для каждой внутренней вершины -и, связанной с переменной Xj: осуществляется переход из этой вершины либо по 0-ребру (XJ = 0), либо по 1-ребру (Xj = 1) в соответствии со значением ZA,-, которое принимает переменная Xj во входном наборе. Будем говорить, что в вершине v считывается значение переменной Xj.
При этом f(y) = 1 тогда и только тогда когда существует путь из s в t: по которому можно двигаться описанным выше образом. Такой путь называется принимающим для v. Результат вычислений обозначаются следующим образом: Р{у) = 1 если существует принимающий путь для v и Р{у) = 0 в противном случае.
Ветвящаяся программа называется уровневой, если ее вершины могут быть разбиты на уровни 1 ,..., и V +i, где Vi+\ содержит только вершины без исходящих ребер. Причем из вершин уровня Vj: где j исходящие ребра идет только в вершины уровня Vj+\. Для ветвящейся программы Psj вершина s находится на первом уровне Vi, а вершина t на последнем уровне Vi+\. Ширина w(P) уровневой ветвящейся программы Р - это максимум от количества вершин на уровне, взятый по всем уровням программы Р.
Уровневая ветвящаяся программа Р называется забывающей, если на любом уровне Р тестируется только одна переменная.
Уровневая ветвящаяся программа Р называется один раз читающей, если на любом пути вычисления каждая переменная читается один раз.
В англоязычной литературе уровневая забывающая один раз читающая программа называется Ordered Binary Desision Diagram (сокращенно OBDD).
Говорят, что OBDD Р читает переменные в некотором порядке 0(Р) = (ji,... Jn). Будем говорить, что 0(Р) — порядок Р.
Ветвящаяся программа Р называется недетерминированной OBDD (NOBDD), если она является OBDD, при этом из любой вершины может выходить более одного ребра с одинаковой меткой. При этом Р{у) = 1, если для набора v существует хотя бы один путь из начальной вершины в принимающую.
Ветвящаяся программа Р называется вероятностной OBDD (POBDD), если она является OBDD, при этом из любой вершины может выходить более одного ребра с одинаковой меткой, с каждом из которых ассоциируется некоторая вероятность. Нужное ребро для переходя выбирается с помощью вероятностного механизма. При этом для любой вершины сумма вероятностей, ассоциированных с исходящими ребрами с одинаковой меткой всегда равна 1. Для є 0 говорят, что POBDD Р принимает набор v Є {0,1}п с е изолированной точкой сечения, если для него вероятность попасть в принимающую вершину Рг(Р(у) = 1) 0.5 + е, и отвергает, если Рг(Р(у) = 1) 0.5 — є .
Ветвящаяся программа Р называется к —OBDD, если состоит из к слоев, где г-ый слой (1 Рг программы Р является OBDD. Причем порядок чтения переменных у всех Рг одинаковый, обозначим его 0(Р), будем называть порядком к —OBDD Р.
Ветвящаяся программа Р называется недетерминированная к—OBDD (к — NOBDD), если состоит из к слоев, где г-ый слой (1 г к) Рг программы Р является NOBDD. Причем порядок чтения переменных у всех Рг одинаковый, обозначим его 0(Р), будем называть порядком k — NOBDD Р.
Ветвящаяся программа Р называется вероятностной к — OBDD (к — POBDD), если состоит из к слоев, где г-ый слой (1 і к) Рг программы Р является POBDD. Причем порядок чтения переменных у всех Рг одинаковый, обозначим его 0(Р), будем называть порядком k — POBDD Р.
Размером S(P) ветвящейся программы Р будем называть число вершин программы Р. Заметим, что для k—OBDD (k—NOBDD, k—POBDD) справедлива следующая оценка для размера:
Длинной 1{Р) ветвящейся программы Р будем называть длину самого длинного пусти от начальной вершины до финальной. Очевидно что для k—OBDD, k-NOBDD и k-POBDD длинна 1{Р) равна к.
Рассмотрим разбиение 7Г = (ХА,ХВ) Є Щ0). Построим протокол Рт, для которого алгоритм А получает на вход Хд, алгоритм В получает на вход Хв Раунд 1. Алгоритм А выполняет работу Р на 1-ом слое, пройдя по вершинам, соответствующим ХА-, И отправляет алгоритму В номер вершины в слое, на которой он остановился. В т\ записано двоичное представление номера вершины.
Доказательство. Построим ветвящуюсь программу Р, удовлетворяющую условиям леммы. Рассмотрим естественный порядок 7Г = (1,... ,п). Программа Р на слое (2/:-1) будет вычислять Stepi(X,t — l), а на слое (2t) будет вычислять Step2(X,t — 1), для t Є {1,..., к}. Будем считать, что вычисления проводятся на входном наборе v Є {0,1}п.
Рассмотрим слой 2/:-1. Первый уровень состоит из w вершин, каждая из которых соответствует одному из значений функции Step2(v,t — 2), вычисленного на предыдущем слое. Рассмотрим г-ую вершину первого уровня. В этом случае программа Р проверяет каждый блок на выполнение условий AdrK(isJ) = t — 1 и AdrW(iyJ) = і. Если для некоторого блока j выполняется указанное условие, т.е. найден блок, по которому должно быть вычислено значение функции Stepi(v,t — 1), то тогда программа Р вычисляет Val(v,i,t — 1) по блоку j. В результате будет получено значение Stepi(v,t — 1). Если для блока j условие AdrK(vJ) = t — 1 и AdrW(vJ) = і не выполнилось, то программа переходит к следующему блоку.
Отметим, что вычисление значения УаІ(іУ,і,і—1) не зависит от і в том случае, если уже известно j, поэтому часть программы, которая вычисляет это значение мы можем сделать общей для всех вершин і.
К раз читающие забывающие ветвящиеся программы. Иерархия по ширине
Теория автоматов развита достаточно хорошо. Для автоматов часто рассматриваю различные расширенные модели, в частности модель OBDD можно рассматривать как расширение детерминированного автомата, а модель k—OBDD как расширение двухстороннего автомата. Такого типа расширенные автоматы относят к неоднородным моделям, в англоязычной литературе часто используется термин "non-uniform". Есть различные способы определения неоднородных автоматов, которые рассматривались в работах [13], [17], [21], [27], [12,30], [33,43] и более ранние. В данной работе же будет рассмотрена отличная от предвиденных модель неоднородного автомата, определение которой будет дано в следующем разделе.
Определение двухстороннего автомата, которое будет рассмотрено основывается на классическом определении двухстороннего автомата.
Опишем работу автомата Dn на наборе v Є Sn. Первоначально автомат обозревает первую ячейку и находится в состоянии S\. Далее применяется функция переходов 6i(si,X\) = (s ,di), где s Є S, di Є Читающая головка перемещается в соответствии с направлением di, при этом автомат переходит в состояние s .
В случае, если на некотором шаге читающая головка обозревает позицию номер і и автомат находиться в состоянии номер s, то применяется функция переходов 5{(s,V{) = (s ,di) и автомат переходи в состояние s , передвигает читающую головку в соответствие с направлением di.
Автомат Dn принимает входной набор (выдает результат 1), если попадает в состояние sa. Причем, если автомат обозревает ячейку і, и находиться в состоянии sa, то автомат переводит читающую головку в конец слова без изменения состояния и завершает работу.
Автомат Dn отвергает входной набор (выдает результат 0), если попадает в состояние sr или попадает в бесконечный цикл. Причем, если автомат обозревает ячейку і, и находиться в состоянии sr, то автомат переводит читающую головку в конец слова без изменения состояния и завершает работу.
Также определим недетерминированный вариант для 2DAn. Определение 3.1.2. Двухсторонний неоднородный недетерминированный автомат с переменной структурой, работающий на входном наборе X = (#1,... ,хп) (2NAn) Dn — это шестерка
Опишем работу автомата Dn на наборе v Є Sn. Первоначально автомат обозревает первую ячейку и находится в состоянии S\. Далее применяется функция переходов 6i(si,xi) = (S ,di), где S Є V{S), di Є {—) , \.}. Читающая головка перемещается в соответствии с направлением di, при этом автомат недетерминированно переходит в одно из состояний s Є S . В случае, если на некотором шаге читающая головка обозревает позицию номер і и автомат находиться в состоянии номер s, то применяется функция переходов 5{(s,V{) = (S ,di) и автомат недетерминированно переходит в одно из состояний s Є S , передвигает читающую головку в соответствие с направлением di.
Автомат Dn принимает входной набор(выдает результат 1), если при недетерминированном выборе состояний существует такая ситуация, что автомат попадает в состояние sa. Причем, если автомат обозревает ячейку г, и находиться в состоянии sa, то переводит читающую головку в конец слова без изменения состояния и завершает работу.
Автомат Dn отвергает входной набор(выдает результат 0), если при всех недетерминированных исходах попадает в состояние sr или попадает в бесконечный цикл. Причем, если автомат обозревает ячейку і, и находиться в состоянии sr, то автомат переводит читающую головку в конец слова без изменения состояния и завершает работу.
Множество входных наборов X, которое принимает 2DAn(2NAn) Dn образует язьж Ln. С другой стороны мы можем говорить о функции fn : Sn — {0,1} такой, что fn{X) = 1 тогда и только тога, когда Dn принимает набор X, тогда можно говорить, что автомат Dn вычисляет функцию fn. Отметим, что функция fn является характеристической функцией для языка Ln.
Далее будет рассматриваться случай Е = {0,1}, если это не будет оговорено специально. В этом случае функция fn является булевой.
Обозначим множество функций, которое вычисляет 2DAn следующим образом:
2DSIZE(d(n)) = {fn : fn вычислима некоторым 2DAn Dn размера d(n)}. Аналогичным образом можно определить множество функций, которое вычисляет 2NA„: 2NSIZE(d(n)) = {fn : fn вычислима некоторым 2NAn Dn размера d(n)}. В случае, когда мы говорим о булевых функция, то изменение порядка переменных не изменяет саму булеву функцию (что нельзя сказать о языке). В связи с этим рассмотрена обобщенная модель 2DAn и 2NAn:
Определение 3.1.3. Двухсторонний неоднородный детерминированный 9-автомат с переменной структурой, работающий на входном наборе X = (#1,... ,хп) (2DA) Den — это семерка
Эмуляция k-OBDD с помощью NOBDD
Доказательство. Построим искомую Р. Рассмотрим входной набор v Є {0,1}п. Пусть Р читает переменные в естественном порядке.
На г-ом слое будет сравниваться г-ый бит наборов a{v) и (3(ІУ). ЕСЛИ ОНИ равны то переходим к сравнению следующего бита на (г + 1)-м слое, если не равны, то Р отвергает набор. Если на последнем слое все еще равны, значит a{v) и (3(ІУ) равны полностью и Р может принять набор. Слой і устроен следующим образом. На уровне будет четыре группы вершин. Первая группа состоит из і2 вершин, каждой из них соответствует пара (j,r), где j,r Є {0,... ,г — 1} и она соответствует ситуации, когда на данный момент прочитано j значащих битов из a(v) и г значащих битов из /3(ь ). Каждая из этих вершин соответствует ситуации когда еще не прочитаны ни г-ый бит a(v): ни г-ый бит (3(ІУ)
Вторая группа переменных состоит из Зг вершин каждой из которых соответствует пара (qj), где q Є {—1,0,1}, j Є {1,... ,г}. Вершина, соответствующая паре (qj), означает, что г-ый значащий бит из f3{v) равен q и при этом считан j значащих бит из а{у). Случай, когда q = —1 может быть только на уровнях
123
которые читают значимые биты. И это означает, что следующий бит является г-м из f3(iy) и его надо запомнить.
Третья группа переменных состоит из Зі вершин каждой из которых соответствует пара (q,r), где q Є { — 1,0,1},г Є {1,...,}. Вершина, соответствующая паре (q,r), означает, что г-ый значащий бит из a(v) равен q и при этом считан г значащих бит из (3(ІУ). Случай, когда q = — 1 может быть только на уровнях которые читают значимые биты. И это означает, что следующий бит является г-м из a{v) и его надо запомнить.
Четвертая группа состоит из двух вершин: equals, которая означает, что г-ые биты OL{U) И (З(ІУ) равны, reject означающая, что строки cv{v) и (3(ІУ) не равны.
Первая группа вершин работает следующим образом. На уровнях, которые считывают маркерные переменные, из вершины соответствующей паре (j,r), где j,r Є {1,... ,г — 2} идут два ребра: ведущее в вершину соответствующую (j + 1,г) по значению 1, т.к. это означает что далее бит из OL{U)\ И В вершину соответствующую (j,r + 1) по значению 0, т.к. это означает что далее бит из (3(и).
Из вершины соответствующей паре (г — 1,г), где г Є {1,...,г — 2} идут два ребра: ведущее в вершину из третей группы, соответствующую (—1,г) по значению 1, т.к. это означает что далее нужный нам г-ый бит из oi{y); и в вершину соответствующую (г — 1,г + 1) по значению 0, т.к. это означает что далее бит из j3(v).
Из вершины соответствующей паре (j,i — 1), где г Є {1,... ,г — 2} идут два ребра: ведущее в вершину соответствующую (j + 1,г — 1) по значению 1, т.к. это означает что далее бит из OL{U)\ ведущее в вершину из второй группы, соответствующую (—l,j) по значению 0, т.к. это означает что далее нужный нам г-ый бит из (3{у).
Из вершин первой группы, на уровнях читающих значимые биты идут оба ребра в соответствующие вершины следующего уровня.
Рассмотрим теперь вершины второй группы. Обсудим уровни читающие маркерные биты. Из вершины соответствующие паре (qj), где q Є {0,1}, j Є {1,..., г}, исходит ребро помеченные 0 в вершину соответствующую (qj + 1), т.к. прочитан очередной бит из СЇ(ІУ); И ребро помеченное 1 в вершину соответствующую (q,j), т.к. биты из f3(v) нас больше не интересуют.
Опишем уровни читающие значимые биты. Из вершины соответствующие паре (q,j), где q Є {0,1}, j Є {1,..., г — 1}, исходят ребра помеченные 0 и 1 в вершину соответствующую (q,j).
Из вершины соответствующие паре (—l,j), где j Є {1,г — 1}, исходит ребро помеченное q, где q Є {0,1} в соответствующую (q,j), таким образом мы запоминаем г-ый бит строки (3(ІУ).
Из вершины соответствующие паре (q,i), где q Є {0,1}, исходит ребро помеченное q, в вершину equals, а по ребру, помеченному 1 — q в вершину reject, т.к. эта вершина соответствует ситуации когда q — значение г-го бита из (3(ІУ) И мы читаем г-ый бит из а{у).
Рассмотрим вершины третей группы. Обсудим уровни читающие маркерные биты. Из вершины соответствующие паре (q,r), где q Є {0,1}, г Є {1,..., і}, исходит ребро помеченное 1 в вершину соответствующую (g,r + l), т.к. прочитан очередной бит из f3(iy); и ребро помеченное 0 в вершину соответствующую (q,r), т.к. биты из cv{v) нас больше не интересуют.
Опишем уровни читающие значимые биты. Из вершины соответствующие паре (q,r), где q Є {0,1},г Є {1,г — 1}, исходят ребра помеченное 0 и 1 в вершину соответствующую (q,r).
Из вершины соответствующие паре (—1,г), где г Є {1,г — 1}, исходит ребро помеченное q, где q Є {0,1} в соответствующую (q,r), таким образом мы запоминаем г-ый бит строки а{у). Из вершины соответствующие паре (q,i), где q Є {0,1}, исходит ребро помеченное q, в вершину equals, а по ребру, помеченному 1 — q в вершину reject, т.к. эта вершина соответствует ситуации когда q — значение г-го бита из cv{v) и мы читаем г-ый бит из (3(ІУ). Из вершин четвертой группы ребра идут в соответствующие вершины следующего уровня. На последнем уровне каждого слоя из всех вершин идут ребра в вершину reject кроме вершины equals из нее ребра идут в вершину первой группы соот 125 ветствующую (0,0), а также в эту вершину ведут ребра помеченные q из вершин второй и третей группы соответствующие (q,i).
На последнем уровне последнего слоя из всех вершин идут ребра в вершину reject, отвергающую входной набор кроме вершины equals из нее ребра идут в вершину accept, принимающую набор, а также в эту вершину ведут ребра помеченные q из вершин второй и третей группы соответствующие (q,i).