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

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

Введение

1. Основные понятия и краткий обзор литературы

1.1. Конечные автоматы

1.2. Конечные автоматы с временными задержками

1.3. Отношения между временными автоматами

1.4. Модели неисправности и проверяющие тесты с гарантированной полнотой

1.4.1. Полные проверяющие тесты

1.4.2. Построение теста перечислением неисправностей

1.4.3. Модель черного ящика для классических конечных автоматов

1.4.4. Синтез проверяющего теста для конечного автомата на основе обхода графа переходов

1.4.5. Модель серого ящика мутационный автомат для классических конечных автоматов

1.5. Синтез полных проверяющих тестов для временных автоматов
1.5.1. Автоматная модель Алюра и Дилла
1.5.2. Автоматная модель с задержками на переходах и выходах
1.6. Выводы по главе 1
2. Построение проверяющих тестов для временных автоматов на основе классического конечного автомата
2.1. Построение соответствующего конечного автомата
2.1.1. Метод построения конечного автомата для удаления переходов по задержке
2.1.2. Соответствие между временным автоматом и построенным конечным автоматом
2.2. Построение проверяющих тестов для временного автомата на основе соответствующего конечного автомата
2.2.1. Алгоритм построения проверяющего теста на основе соответствующего конечного автомата
2.2.2. Построение проверяющих тестов на основе явного перечисления неисправностей
2.2.3. Построение полных проверяющих тестов относительно выходных неисправностей
2.2.4. Построение проверяющих тестов для проверки переходов
временного автомата
2.3. Пример проверки доступных реализаций телекоммуникационного протокола ТТТР проверяющим тестом, построенным на основе обхода графа переходов временного автомата
2.3.1. Временной автомат, описывающий поведение протокола ТРТР, и построение проверяющего теста по временному автомату
2.3.2. Экспериментальные результаты
2.4. Экспериментальные результаты по построению полных проверяющих тестов для случайно сгенерированных автоматов
2.5. Результаты главы 2
3. Метод синтеза проверяющих тестов для временных автоматов относительно модели черного ящика
3.1. Модель черного ящика для временных автоматов
3.2. Необходимые и достаточные условия эквивалентности временных автоматов
3.3. Синтез полного проверяющего теста для временных автоматов относительно модели черного ящика
3.3.1. Множества различимости и достижимости для временного автомата
3.3.2. Построение проверяющего теста при тп
3.3.3. Построение полного проверяющего теста при т п
3.4. Оценка сложности проверяющих тестов относительно модели черного ящика
3.5. Экспериментальные результаты построения полных проверяющих тестов относительно модели черного ящика
3.6. Результаты главы 3
4. Адаптация метода синтеза тестов для различных моделей неисправности
4.1. Построение проверяющего теста для временных автоматов с фиксированным набором задержек
4.2. Построение проверяющего теста для временных автоматов в случае, когда неисправность может только увеличить длину задержки
4.3. Отношения между временными автоматами в зависимости от времени обработки входных воздействий
4.4. Синтез тестов для проверки времени обработки входных воздействий
4.5. Результаты главы 4
Заключение
Литература


Кроме того, результаты работы докладывались на научных конференциях VI VII, VIII Российской конференции с международным участием Новые информационные технологии в исследовании дискретных структур, с. Шушенское, г. Томск, г. Российской конференции VI Всесибирский конгресс женщинматематиков, Красноярск, г. Международной научнопрактической конференции Актуальные проблемы радиофизики, Томск, г. Международной конференции по качеству программного обеспечения, I, Мадрид, Испания, г. Жигулин М. В. Преобразование спецификации при пассивном тестировании телекоммуникационных протоколов М. В. Жигулин, С. А. Прокопенко, Н. В. Евтушенко Вестник Томского государственного университета. Приложение. Доклады VI Всероссийской конференции с международным участием Новые информационные технологии в исследовании сложных структур. Томск, . С. . Жигулин М. В. Оценка полноты проверки при пассивном тестировании на основе автоматной модели Новые информационные технологии в исследовании сложных структур тезисы докладов седьмой Российской конференции с международным участием. Томск, . С. . Жигулин М. В. Оценка полноты проверки при пассивном тестировании на основе автоматной модели М. Коломеец Известия Томского политехнического университета. Т. 4, 5. С. . Жигулин М. В. Необходимое и достаточное условие эквивалентности временных автоматов М. В. Жигулин, И. М. Дмитриев VI Всесибирский конгресс женщинматематиков материалы Всероссийской конференции. Красноярск, . С. . Жигулин М. В. Синтез тестов с гарантированной полнотой для временных автоматов М. В. Жигулин, И. М. Дмитриев, Н. В. Евтушенко Известия Томского политехнического университета. Т. 6, 5. С. . Жигулин М. В. Алгоритм синтеза проверяющего теста с гарантированной полнотой для конечных временных автоматов с фиксированным набором задержек для модели черного ящика М. В. Жигулин, И. М. Дмитриев, Д. Томск, . С. . Дмитриев И. М. Синтез проверяющих тестов с гарантированной полнотой для временных автоматов с конечными задержками И. М. Дмитриев, М. В. Жигулин II Известия высших учебных заведений Физика. Томск, . Т. , . С. . М.В. Жигулин Тестирование программной реализации протокола I на основе модели расширенного автомата М. Н.Г. Кушик, Шабалдин Известия Томского политехнического университета. Томск, . Т. 8, 5. С. . М. ivi i i i . II Ii i i, . Структура и объем работы. Диссертация состоит из введения, 4 глав, заключения и списка используемой литературы. Диссертация содержит рисунков. Краткое содержание работы. Первая глава посвящена основным понятиям и обозначениям, относящимся к конечным и временным автоматам. Под конечным автоматом или просто автоматом понимается система с конечным множеством состояний, входных и выходных символов, которая переходит из состояния в состояние при подаче входных воздействий и производит при этом выходные реакции. В данной работе мы рассматриваем инициальные автоматы, то есть автоматы с фиксированным начальным состоянием 3. Можно сказать, что инициальный автомат описывает отображение входных слов слов во входном алфавите в выходные слова . Временной автомат получается из конечного автомата добавлением целочисленных таймаутов, т. Если в течение определенного промежутка времени на вход автомата не поступает никакого входного воздействия, то автомат может спонтанно перейти в другое состояние. Кроме того, каждый выходной символ может быть выдан с некоторой целочисленной задержкой после поступления входного символа. Соответственно, поведение такого автомата зависит не только от входного символа, но и от момента времени, в который подается входной символ. Поэтому вводится понятие временного входного символа и временного выходного символа. Временной входной символ есть пара входной символ, целочисленное значение промежутка времени, через который подается входной символ после реакции на предыдущее входное воздействие. Временной выходной символ также есть пара выходная реакция автомата на некоторое входное воздействие, целочисленное значение единиц времени, которое необходимо для обработки этого входного воздействия.