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

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

ОГЛАВЛЕНИЕ
Введение
1. Определения, обозначения, обзор литературы
1.1. Автоматы
1.2.Отношения между автоматами
1.3.Модель неисправности и проверяющие тесты для автоматов
1.4. Автоматные сети
1.5.Проверяющие тесты для компоненты автоматной сети
1.6.Методы построения тестов для изолированных автоматов
1.6.1. IV-метод
1.6.2. Построение проверяющего теста для недетерминированного автомата относительно эквивалентности
1.6.3. Построение проверяющего теста для недетерминированного автомата относительно редукции
1.7.Методы построения теста для компоненты сети
1.7.1. Методы построения теста для компоненты сети на основе сетевого автомата
1.7.2. Тесты для компоненты сети на основе сетевого
эквивалента
1.8.Выводы по главе
2. Минимизация проверяющих тестов для частичных автоматов
2.1. Основные понятия и определения
2.2. Оценка длины проверяющего теста
2.3.Критерий доопределения неопределенных переходов
2.4.Частичный автомат с одним входом
2.4.1. Вспомогательные определения
2.4.2. Частичный автомат с одним неопределенным переходом

2.4.3. Частичный автомат с несколькими
неопределенными переходами
2.5. Доопределение неопределенных переходов
2.6.Экспериментальные результаты
2.7. Выводы по главе
3. Минимизация проверяющих тестов для компоненты сети
из детерминированных автоматов
3.1. Модель неисправности
3.2.0бнаружимые входо-выходные последовательности компоненты
3.3.Минимизация проверяющего теста относительно эквивалентности
3.3.1. Обнаружимые входо-выходные пары компоненты
3.3.2. Построение характеристических множеств
3.3.3. Сведение задачи минимизации теста относительно эквивалентности к задаче покрытия булевой матрицы
3.4. Экспериментальные результаты
3.5.Сравнение предложенного метода с явным перебором неисправных компонент
3.6. Выводы по главе
4. Минимизация проверяющих тестов для компоненты сети
из недетерминированных автоматов
4.1.Модель неисправности
4.2.Минимизация проверяющего теста относительно редукции
4.2.1. Обнаружимые входо-выходные пары компоненты
4.2.2. Сведение задачи минимизации теста относительно
редукции к задаче покрытия булевой матрицы
4.3.Минимизация проверяющих тестов относительно
эквивалентности
4.3.1. Сохранение внешнего поведения

4.3.2. Построение множества С{а,(3)
4.3.3. Сведение задачи минимизации теста относительно эквивалентности к задаче покрытия булевой матрицы
4.4. Выводы по главе
Заключение
Литература
Приложение

Кроме того, компонента не имеет внешних входов и выходов, т.е. входной и выходной алфавиты автомата А*С суть {х} и {уьут}- Рассмотрим состояние 50 автомата С, состояние /0 автомата А и входной символ Х. Как видно, автомат С в состоянии нах] может выдать выходные символы иу и иУг в зависимости от того, какой выходной сигнал производит компонента А в состоянии *о. Поскольку компонента А является автоматом Мура, то выходной сигнал в состоянии /0 равен г независимо от того, какой входной сигнал поступает на вход компоненты А, т.е. пара (иЬ2]) является единственной сбалансированной парой внутренних сигналов. Поэтому в автомате композиции А*С существует единственный переход из состояния ЗАо ПОД действием Х В состояние с ВЫХОДНЫМ СИМВОЛОМ У. Автомат композиции А»С представлен на рисунке 1.5в.