Методы синтеза установочных и различающих экспериментов с недетерминированными автоматами

• Автор: Кушик, Наталья Геннадьевна
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Томск
• Количество страниц: 137 с. : ил.

Оглавление
ВВЕДЕНИЕ
1. ОБЗОР СУЩЕСТВУЮЩИХ МЕТОДОВ СИНТЕЗА «УМОЗРИТЕЛЬНЫХ» ЭКСПЕРИМЕНТОВ С КОНЕЧНЫМИ АВТОМАТАМИ
1Л Основные определения и обозначения
1ЛЛ Конечные автоматы и отношения между ними
1Л .2 Полуавтоматы. Отношения между ними. Детерминизация
1.2 Эксперименты с полностью определенными автоматами
1.2.1 Краткая классификация экспериментов
1.2.2 Различающие (диагностические) эксперименты с детерминированными автоматами
1.2.3 Установочные эксперименты с детерминированными автоматами
1.2.4 Синхронизирующие эксперименты с детерминированными автоматами
1.2.5 Проверяющие и распознающие эксперименты
1.3 Известные результаты по экспериментам с недетерминированными автоматами
1.3.1 Различающие эксперименты с недетерминированными автоматами
1.3.2 Установочные и синхронизирующие эксперименты с недетерминированными автоматами
1.3.3 Проверяющие эксперименты с недетерминированными автоматами..
1.4 Выводы по главе
2. РАЗЛИЧАЮЩИЕ ЭКСПЕРИМЕНТЫ С НЕДЕТЕРМИНИРОВАННЫМИ АВТОМАТАМИ
2.1 Безусловные различающие эксперименты с недетерминированными
автоматами
2.1.1 Метод синтеза безусловного различающего эксперимента для
недетерминированного автомата

2.1.2 Оценка сложности безусловного различающего эксперимента
2.1.3 Достижимость оценки сложности безусловного различающего эксперимента
2.2 Условные различающие эксперименты с недетерминированными автоматами
2.2.1 Пересечение неинициальных недетерминированных автоматов
2.2.2 Различающий тестовый пример
2.2.3 Синтез условных различающих экспериментов с
недетерминированными автоматами
2.2.4 Оценка сложности условного различающего эксперимента
2.2.5 Результаты главы
3. УСТАНОВОЧНЫЕ ЭКСПЕРИМЕНТЫ С НЕДЕТЕРМИНИРОВАННЫМИ АВТОМАТАМИ
3.1 Безусловные установочные эксперименты с неинициальными недетерминированными автоматами
3.1.1 Синтез установочных последовательностей при безусловном эксперименте с недетерминированным автоматом
3.1.2 Оценка сложности безусловного установочного эксперимента
3.1.2.1 Отношение выводимости на множестве непустых подмножеств конечного множества
3.1.2.2 Описание класса недетерминированных автоматов, для которых установочная последовательность имеет экспоненциальную длину
3.2 Условные установочные эксперименты с недетерминированными автоматами
3.2.1 Установочный тестовый пример
3.2.2 Синтез условных установочных экспериментов с
недетерминированными автоматами
3.2.3 Оценка сложности условного установочного эксперимента

3.3 Синтез синхронизирующих экспериментов для
недетерминированных автоматов
3.4 Результаты главы
ГЛАВА 4. ИСПОЛЬЗОВАНИЕ ЭКСПЕРИМЕНТОВ С НЕДЕТЕРМИНИРОВАННЫМИ АВТОМАТАМИ В АНАЛИЗЕ И СИНТЕЗЕ СЛОЖНЫХ СИСТЕМ
4.1 Применение экспериментов с недетерминированными автоматами к синтезу проверяющих тестов для дискретных систем
4.1.1 Сокращение длины проверяющих тестов за счет использования разделимых и условно различимых множеств состояний
4.1.2 Синтез проверяющих тестов для протокола IRC
4.2 Синтез экспериментов для компоненты автоматной сети
4.2.1 Синтез установочных экспериментов для компоненты автоматной сети
4.2.2 Синтез экспериментов для упрощения компоненты автоматной сети
4.3 Выводы по главе
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЕ А

Существует большое количество работ по построению проверяющих экспериментов с детерминированными автоматами, в случае, когда известна верхняя оценка т на число состояний проверяемого автомата. Соответствующая входная последовательность (или множество входных последовательностей в кратном эксперименте с инициальным автоматом) называются проверяющей последовательностью (или проверяющим тестом) для эталонного автомата. При этом основным критерием оценки качества проверяющей последовательности или проверяющего теста является его полнота. Полнота гарантирует, что любой автомат из заданного класса (число состояний которого не превышает числа т), который не эквивалентен эталонному автомату, будет выявлен при подаче проверяющей последовательности (последовательностей проверяющего теста). Иными словами, выходная реакция этого автомата на проверяющую последовательность (семейство последовательностей) не будет совпадать с реакцией (множеством реакций) эталонного автомата на эту последовательность (последовательности проверяющего теста).
Для синтеза проверяющей последовательности (простого проверяющего эксперимента) установочные и синхронизирующие последовательности используются следующим образом [7]. Если автомат обладает синхронизирующей последовательностью, то определяется состояние эталонного автомата, в которое автомат переводится этой последовательностью. Если синхронизирующая последовательность не существует, то для эталонного автомата строится установочная последовательность, которая и подается на тестируемый автомат6. После того как определено состояние эталонного автомата после подачи установочной последовательности, проверяемый автомат переводится в нужное начальное состояние, для которого и строилась собственно проверяющая последовательность. При построении проверяющей последовательности обычно предполагается, что эталонный автомат является сильно связным и приведенным, и проверяемый автомат имеет не больше
6 Таким образом, такой проверяющий эксперимент, вообще говоря, не является «чисто» безусловным.