Введение
1 Основные определения и обозначения 28
1.1 Конечные автоматы и отношения между ними 28
1.2 Полуавтоматы и отношения между ними 34
1.3 Эксперименты с конечными автоматами и полуавтоматами 37
2. Сложность задач проверки существования и синтеза безусловных «умозрительных» экспериментов с конечными автоматами 47
2.1 Известные результаты по оценкам сложности экспериментов с конечными автоматами 47
2.1.1 Сложность экспериментов с детерминированными автоматами 48
2.1.2 Сложность экспериментов с недетерминированными автоматами 51
2.2 Оригинальные результаты в области оценок сложности экспериментов с недетерминированными автоматами 53
2.2.1 Оценка длины установочной последовательности для полностью определенного недетерминированного автомата 53
2.2.1.1 Отношение выводимости на множестве непустых подмножеств конечного множества 53
2.2.1.2 Описание класса недетерминированных автоматов, для которых установочная последовательность имеет экспоненциальную длину 57
2.2.2 Оценка сложности проверки существования установочной последовательности для полностью определенного недетерминированного автомата 65
2.2.3 Оценка сложности проверки существования разделяющей последовательности для полностью определенного недетерминированного автомата 68
2.2.3.1 Синтез синхронизируемого полуавтомата для описания множества установочных последовательностей недетерминированного автомата 70
2.2.3.2 Синтез синхронизируемого полуавтомата для описания множества
разделяющих последовательностей недетерминированного автомата 74
2.3 Основные результаты главы 2 77
3 Переход к адаптивным экспериментам как способ понижения сложности задач проверки существования и синтеза «умозрительных» экспериментов для подклассов конечных автоматов 79
3.1 Известные результаты для конечных автоматов по эффективному переходу от безусловных экспериментов к адаптивным 80
3.2 Методы синтеза адаптивных установочных и различающих экспериментов с недетерминированными автоматами 82
3.3 Адаптация метода синтеза условных различающих экспериментов на случай ненаблюдаемых автоматов 99
3.4 Оценка высоты условных экспериментов для недетерминированных автоматов 102
3.5 Достижимость экспоненциальной оценки высоты условного различающего эксперимента для полностью определенных наблюдаемых автоматов 104
3.5.1 Отношение линейного порядка на множестве подмножеств состояний автомата 104
3.5.2 Описание класса недетерминированных автоматов, для которых условный различающий эксперимент имеет экспоненциальную высоту 112
3.6 Определение классов недетерминированных автоматов с пониженными оценками сложности задачи проверки существования и синтеза условных установочных и различающих экспериментов 123
3.6.1 Определение класса недетерминированных автоматов, для которых задача проверки существования условных установочных экспериментов решается за полиномиальное время 123
3.6.2 Обсуждение возможных эвристик для сокращения высоты установочных тестовых примеров для полностью определенных недетерминированных автоматов 135
3.6.3 Определение класса недетерминированных автоматов, для которых задача проверки существования условных различающих экспериментов решается за полиномиальное время 137
3.6.4 Определение класса недетерминированных автоматов, для которых задача проверки существования условных синхронизирующих экспериментов решается за полиномиальное время 146
3.7 Основные результаты главы 3 159
4 Определение классов недетерминированных автоматов с пониженными оценками сложности задач проверки существования и синтеза проверяющих экспериментов 161
4.1 Краткий обзор методов синтеза проверяющих экспериментов для конечных автоматов 163
4.1.1 Классификация проверяющих экспериментов с конечными автоматами 164
4.1.2 Проверяющие эксперименты с детерминированными автоматами 168
4.1.3 Проверяющие эксперименты с недетерминированными автоматами 173
4.2 Синтез проверяющих экспериментов для ненаблюдаемых автоматов 177
4.3 Синтез проверяющих экспериментов для древовидных спецификаций 198
4.4 Переход от безусловного эксперимента к условному для понижения сложности задачи синтеза кратных проверяющих экспериментов для недетерминированных автоматов 206
4.4.1 Синтез условного кратного проверяющего эксперимента для ненаблюдаемых автоматов 207
4.4.2 d-проекция недетерминированных автоматов 211
4.4.2.1 Использование d-проекции при синтезе различающих экспериментов для недетерминированных автоматов 212
4.4.2.2 Синтез кратных условных проверяющих экспериментов для недетерминированных автоматов на основе d-проекции 216
4.4.3 Merging-free-проекция недетерминированных автоматов 221
4.4.3.1 Использование merging-free-проекции при синтезе различающих экспериментов для недетерминированных автоматов 222
4.4.3.2 Синтез кратных условных проверяющих экспериментов для недетерминированных автоматов на основе merging-free-проекции 223
4.5 Основные результаты главы 4 226
5 Обсуждение технических приложений задач синтеза умозрительных экспериментов с конечными автоматами 228
5.1 Способы получения автоматных спецификаций технических систем при оценке качества программного обеспечения 229
5.1.1 Построение автоматной модели на основе требований к разрабатываемому программному продукту 229
5.2 Использование экспериментов с конечными автоматами для построения и уточнения автоматных спецификаций 237
5.3 Синтез проверяющих экспериментов для реализаций телекоммуникационных протоколов 243
5.4 Оценка качества интерактивных сервисов с использованием автоматов специальных классов 246
5.4.1 Оценка удовлетворенности конечного пользователя качеством обслуживания для интерактивных сервисов 246
5.4.2 Анализ поведения расширенных автоматов для предсказания удовлетворенности конечного пользователя интерактивным сервисом 249
5.4.3 Оценка качества интерактивных сервисов с использованием структурных автоматов 2 5.5 Синтез проверяющих экспериментов для спецификаций, заданных на языке логического проектирования 261
5.6 Основные результаты главы 5 268
Заключение 270
Список литературы
