Разработка методов синтеза условных тестов для автоматных моделей с недетерминированным поведением

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

Оглавление
Введение

Принятые обозначения

1 Основные понятия и определения

1.1 Введение.

1.2 Входовыходные полуавтоматы

1.3 Автоматы.

1.4 Временные автоматы.

1.5 Краткий обзор литературы но синтезу условных тестов для

автоматных моделей.

1.6 Выводы по главе 1

2 Различающие эксперименты с недетерминированными автоматами
2.1 Введение.
2.2 Отношения гсовместимости и гразличимости.
2.3 Алгоритм построения гразличающего автомата
2.4 Синтез проверяющих тестов при явно заданной области.неисправности и по мутационному автомату.
2.5 Локализация неисправной компоненты в композиции двух
конечных автоматов.
2.5.1 Модель неисправности и распознавание неисправной компоненты
2.5.2 Параллельная композиция автоматов
2.5.3 Модель неисправности и распознавание неисправной компоненты
2.5.4 Результаты компьютерных экспериментов
2.6 Основные результаты главы 2
3 Различающие эксперименты с входовыходными полуавтоматами
3.1 Введение.
3.2 Отношение юсоразличимости.
3.3 Алгоритм построения юсоразл и чающего полуавтомата .
3.4 Синтез проверяющих тестов на основе перебора элементов из
области неисправности.
3.5 Связь между юсо и к ваз иредукцией.
3.5.1 Построение конечного автомата по входовыходному полуавтомату
3.5.2 Построение полного проверяющего теста для входовыходных полуавтоматов на основе полного проверяющего теста для автоматов .
3.6 Основные результаты главы 3
4 Различающие эксперименты с временными автоматами
4.1 Введение
4.2 Отношение гсовместимости
4.3 Алгоритм построения гразличающего временного автомата
4.4 Синтез проверяющих тестов для явно заданной области неисправности
4.5 Основные результаты главы 4.
Заключение
Литература


Научные результаты, составившие основу данной работы, обсуждались на заседаниях объединенного научного семинара кафедры информационных технологий в исследовании дискретных структур радиофизического факультета ТГУ, кафедры программирования и кафедры защиты информации и криптографии факультета прикладной математики и кибернетики ТГУ. Результаты работы докладывались на российских и международных конференциях: «East-West Design and Test Workshop» (Одесса, и Львов, ); IX Международном семинаре «Дискретная математика и её приложения» (Москва, ); Всероссийской конференции с международным участием «Новые информационные технологии в исследовании сложных структур» (Иркутск, и Шушенское, ); TESTCOM- (Таллин, ); SYRCoSE (Санкт-Петербург, , Москва, ). Громову М. К синтезу условных тестов для недетерминированных автоматов / М. Громов, Н. Евтушенко, А. Коломеец // Программирование. С. 1-. Громов, M. JI. Синтез диагностических тестов для автоматных сетей / М. Л. Громов, A. B. Коломеец, Н. В. Евтушенко // Вестник ТГУ. Приложение. С. 4-9. Gromov, М. Testing and Model-Checking Techniques for Diagnosis / M. Gromov and T. Willemse // Vol. LNCS. Springer, . Pp. Громов, M. JI. О распознавании недетерминированного автомата в заданном классе / М. Л. Громов, Н. В. Шабалдииа // Материалы IX Международного семинара «Дискретная математика и её приложения» / Под ред. О.М. Касим-Заде. М.: ММФ МГУ, . С. 7-0. Громов, М. Метод построения полного проверяющего теста для входо-выходных полуавтоматов / М. Громов // Вестник ТГУ. Управление, вычислительная техника и информатика. С. -. Grom. M.L. On the synthesis of adaptive tests for nondcterministic finite state machines / M. L. Gromov, N. V. Evtushenko, A. V. Kolomcets // Program. Comput. Softw. Vol. Pp. Громов, М. Об одном классе автоматов с полиномиальной оценкой числа состояний в наблюдаемой форме / М. Громов, О. Журнал СФУ. Серия: Математика и физика — . Т.1, №3. С. 7-1. Gromov, М. A novel method for derivation of a test with guaranteed coverage for LTS / M. Gromov // Proceedings of SYRCoSE . St. Peterburg:S-PSU, . Pp. Gromov, M. Deriving test suites for timed Finite State Machines / M. Gromov, D. Popov, N. Yevtushenko // Proceedings of IEEE East-West Design & Test Symposium’. Kharkov, Ukraine: SPD FL Stepanov V. V., . Pp. Distinguing Non-deterministic Timed Finite State Machines / M. Gromov. K. El-Fakih, N. Shabaldina, N. Yevtushenko // Vol. LNCS. Springer. Pp. Структура и объём работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы; изложена на 2 страницах, включая 7 рисунков и список литературы из наименований. Во введении дается общая характеристика работы, обосновывается актуальность исследований, определяется тематика и формулируется цель работы, кратко излагаются основные задачи и результаты, выносимые на защиту. Постановка задачи. Требуется установить, какие отношения соответствия можно проверить на основе условного эксперимента с недетерминированными конечными и временными автоматами, как представить условный эксперимент по различению автоматных моделей и описать приложения, в которых используется такой условный эксперимент. В первой главе диссертации вводятся основные определения и понятия. В частности, даётся определение входо-выходного полуавтомата с молчанием, называемого далее в работе просто полуавтоматом. Так же вводится отношение юсо, которое затем рассматривается как отношение соответствия реализации системы своей спецификации. Суть отношения состоит в том, что поведение реализации в любом её состоянии определено на всех тех входных воздействиях, на которых определено поведение спецификации в соответствующем состоянии, а множество выходных реакций содержится в множестве выходных реакций спецификации. При этом предполагается, что молчание системы (то есть отсутствие какой-либо выходной реакции) можно отличить [, ] от ситуации, когда система готовится произвести выходную реакцию, а значит молчание тоже можно рассматривать как особый случай выходной реакции. В разделе 1. Даётся понятие отношения квазиредукции, которое, как и юсо, является классическим, и используется в работе как отношение соответствия между реализацией и спецификацией.