Введение
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
