Методы синтеза установочных и различающих экспериментов с недетерминированными автоматами тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат физико-математических наук Кушик, Наталья Геннадьевна

• Кушик, Наталья Геннадьевна
• кандидат физико-математических наук
• 2013

Оглавление диссертации кандидат физико-математических наук Кушик, Наталья Геннадьевна

Оглавление

ВВЕДЕНИЕ

1. ОБЗОР СУЩЕСТВУЮЩИХ МЕТОДОВ СИНТЕЗА «УМОЗРИТЕЛЬНЫХ» ЭКСПЕРИМЕНТОВ С КОНЕЧНЫМИ АВТОМАТАМИ

1.1 Основные определения и обозначения

1.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 Выводы по главе 1

2. РАЗЛИЧАЮЩИЕ ЭКСПЕРИМЕНТЫ С НЕДЕТЕРМИНИРОВАННЫМИ АВТОМАТАМИ

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

автоматами

2.1.1 Метод синтеза безусловного различающего эксперимента для

недетерминированного автомата

2

2.1.2 Оценка сложности безусловного различающего эксперимента

2.1.3 Достижимость оценки сложности безусловного различающего эксперимента

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

2.2.1 Пересечение неинициальных недетерминированных автоматов

2.2.2 Различающий тестовый пример

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

недетерминированными автоматами

2.2.4 Оценка сложности условного различающего эксперимента

2.2.5 Результаты главы 2

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 Результаты главы 3

106

ГЛАВА 4. ИСПОЛЬЗОВАНИЕ ЭКСПЕРИМЕНТОВ С НЕДЕТЕРМИНИРОВАННЫМИ АВТОМАТАМИ В АНАЛИЗЕ И СИНТЕЗЕ

СЛОЖНЫХ СИСТЕМ

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

4.1.1 Сокращение длины проверяющих тестов за счет использования разделимых и условно различимых множеств состояний

4.1.2 Синтез проверяющих тестов для протокола IRC

4.2 Синтез экспериментов для компоненты автоматной сети

4.2.1 Синтез установочных экспериментов для компоненты автоматной сети

4.2.2 Синтез экспериментов для упрощения компоненты автоматной сети

4.3 Выводы по главе 4

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ А

Введение диссертации (часть автореферата) на тему «Методы синтеза установочных и различающих экспериментов с недетерминированными автоматами»

Введение

Актуальность проблемы. Задача синтеза различных «умозрительных экспериментов» с конечными автоматами была и остается актуальной. Данная задача была поставлена Э. Муром в одноименной статье в 1956 году [1], когда началось стремительное развитие цифровой техники. В статье определялось понятие эксперимента с (детерминированным) автоматом, и была предложена классификация этих экспериментов. Под (умозрительным) экспериментом понимается процесс подачи заданной входной последовательности на автомат, наблюдение выходной реакции автомата и формирование заключения о свойствах автомата [1, 2, 3, 4]. Среди экспериментов с автоматами рассматривают установочные, синхронизирующие, различающие (диагностические), проверяющие и распознающие эксперименты. Первые три класса экспериментов относятся к экспериментам с автоматом, функция поведения которого известна, в то время как в случае проверяющих и распознающих экспериментов предполагается известным только множество, содержащее автомат, с которым проводится эксперимент. Установочные и синхронизирующие эксперименты дают возможность определить состояние автомата после эксперимента, в то время как различающий эксперимент позволяет определить состояние автомата до эксперимента. Проверяющие и распознающие эксперименты позволяют выявить некоторые свойства автомата, предъявленного для эксперимента, например, убедиться, что предъявленный автомат является эквивалентным эталонному автомату. Такие эксперименты достаточно часто базируются на установочных/синхронизирующих и различающих экспериментах и используются в задачах тестирования различных дискретных систем [5, 6, 7, 8, 9]. По способу проведения эксперименты делятся на безусловные и условные (адаптивные) [1, 2]. В безусловных экспериментах входная последовательность известна до начала эксперимента; при проведении условного (или адаптивного) эксперимента следующий входной символ зависит от реакции автомата, предъявленного к эксперименту, на предыдущие входные символы. Соответственно, сложность

5

безусловного эксперимента часто оценивается длиной входной последовательности, в то время как в случае адаптивного эксперимента сложность интерпретируется как высота дерева эксперимента. Для детерминированных автоматов все классы экспериментов исследованы достаточно хорошо, и, тем не менее, до сих пор появляются работы [10, 11], в которых предлагаются методы синтеза экспериментов меньшей сложности (чаще всего для автоматов определенных классов).

Для недетерминированных автоматов практически все классы экспериментов исследованы значительно слабее, в частности, в настоящий момент автору не известны результаты по синтезу установочных экспериментов для недетерминированных автоматов с произвольным множеством начальных состояний, в то время как в настоящее время все чаще в различных приложениях рассматриваются системы с недетерминированным поведением. Недетерминизм в системах появляется в силу различных причин, таких как уровень абстракции, частичность, упрощение системы при моделировании, не знание некоторых свойств системы и др. [12], и, соответственно, исследования по экспериментам с недетерминированными автоматами являются актуальными и необходимыми. Этим исследованиям посвящена кандидатская диссертация.

Цель работы. Целью данной работы является исследование и разработка методов синтеза установочных и различающих безусловных и условных экспериментов с неинциальными недетерминированными автоматами, а также исследование оценок сложности этих экспериментов.

Методы исследования. Для реализации поставленной цели в работе используются методы и средства дискретной математики, в частности, методы теории автоматов, комбинаторики, математической логики. Практическая применимость задач анализа и синтеза с использованием недетерминированных автоматов исследуется с помощью компьютерных экспериментов с техническими системами.

Научная новизна работы состоит в следующем.

Устанавливаются необходимые и достаточные условия существования безусловных и условных различающих и установочных экспериментов с недетерминированными автоматами, при этом условные эксперименты эффективно представляются в виде ациклического автомата, называемого тестовым примером.

Устанавливаются оценки сложности различающих и установочных экспериментов. В случае синтеза безусловных установочных экспериментов доказывается достижимость экспоненциальной оценки его сложности; на примере иллюстрируется достижимость экспоненциальной оценки для условного различающего эксперимента.

На основе сформулированных необходимых и достаточных условий предлагаются методы синтеза безусловных и условных различающих и установочных экспериментов для полностью определенных наблюдаемых недетерминированных автоматов.

Основные положения, выносимые на защиту.

Необходимые и достаточные условия существования безусловных и условных различающих и установочных экспериментов для полностью определенных наблюдаемых недетерминированных автоматов.

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

Оценки сложности безусловных и условных различающих и установочных экспериментов для полностью определенных наблюдаемых недетерминированных автоматов. Достижимость экспоненциальной оценки сложности безусловного установочного эксперимента относительно размерности предъявленного автомата.

Достоверность полученных результатов. Все положения, формулируемые в диссертации, доказываются с применением аппарата дискретной математики, в частности, элементов формальной логики, теории

7

автоматов и комбинаторики. Возможность эффективного использования недетерминированных автоматов (и экспериментов с ними) для анализа и синтеза реальных систем подтверждается посредством компьютерных экспериментов.

Практическая ценность. Различающие эксперименты с недетерминированными автоматами используются для построения проверяющих и диагностических тестов с гарантированной полнотой для технических систем. В случае, если тестируемая система не обладает сигналом «СБРОС» или использование этого сигнала оказывается слишком дорогим, перед началом проверяющего эксперимента используется установочный/синхронизирующий эксперимент. Соответственно, методы синтеза установочных (синхронизирующих) и различающих экспериментов могут быть использованы при синтезе проверяющих тестов для дискретных управляющих систем с недетерминированным поведением.

В четвертой главе диссертации исследуется возможность использования недетерминированных автоматов и экспериментов с ними для анализа и синтеза сложных систем. В частности, рассматривается задача тестирования дискретных систем, а именно, реализаций телекоммуникационных протоколов, а также задача оптимизации логических схем. Приводятся результаты компьютерных экспериментов с реальными дискретными системами, и результаты экспериментов подтверждают эффективность использования модели недетерминированного автомата при решении задач анализа и синтеза для технических систем.

Реализация полученных результатов. Исследования, результаты которых изложены в диссертации, проводились в рамках следующих проектов. Проект «Разработка гибридной распределенной информационной системы для широкополосного доступа к мультимедийным услугам» МинОбрНауки РФ по Соглашению № 14.В37.21.0622 от 16.08.2012 в рамках реализации ФЦП «Научные и научно-педагогические кадры инновационной России на 2009-2013 годы», 2012-2013 гг.

Грант РФФИ-Научное общество Тайваня «Оптимизация цифровых устройств посредством синтеза схем с ограничениями на структуру схемы», № 10-0892003, 2010-2012 гг.

НИР «Проведение прикладных и проблемно-ориентированных поисковых исследований в области информационно-телекоммуникационных систем с участием научных организаций Франции», госконтракт №02.514.12.4002 от 09.06.2009, 2009-2010 гг.

Конкурс межвузовских проектов Национального Исследовательского Томского политехнического университета «Контроль и диагностика программных и аппаратных модулей в автоматизированных управляющих системах», 2011 г. Грант РФФИ_офи «Оптимизация цифровых схем на основе решения уравнений для структурных автоматов» №07-08-12243-офи 2007-2008 гг. Грант У.М.Н.И.К. «Разработка математических и программных средств для оптимизации цифровых схем на основе решения автоматных уравнений», 20092010 гг.

Апробация работы. Все теоретические и практические результаты, составившие основу диссертационной работы, по мере их получения обсуждались на семинаре кафедры информационных технологий в исследовании дискретных структур радиофизического факультета ТГУ. Кроме того, результаты работы докладывались на научных конференциях и семинарах: VIII и IX Российские конференции с международным участием «Новые информационные технологии в исследовании дискретных структур», Томск, 2010 г. и пос. Катунь Алтайского края, 2012 г.; Российской конференции «V Всесибирский конгресс женщин-математиков», Красноярск, 2008 г.; Международной научно-практической конференции «Актуальные проблемы радиофизики», Томск, 2012 г.; Международных Школах по тестированию и верификации программного обеспечения TAROT, Лейбниц, Австрия, 2010 г., Санкт-Петербург, Россия, 2011 г., Безансон, Франция, 2012 г.; VII международной конференции «Автоматизация проектирования дискретных систем» CAD DD'10, Минск, Беларусь, 2010 г.; на семинаре отдела

9

«Технологии программирования» ИСП РАН, Москва, 2012 г., на семинаре лаборатории логического проектирования ОИПИ НАН Беларуси, Минск, Беларусь, 2010 г.; на международных конференциях «East-West Design & Test Symposium», Львов, Украина, 2008 г., Москва, Россия, 2009 г.; коллоквиуме молодых ученых «Spring/Summer Young Researchers' Colloquium on Software Engineering», Москва, 2009 г. и Нижний Новгород, 2010 г.; международной конференции по конечным автоматам и их приложениям CIAA, Блуа, Франция, 2011 г.

По результатам проведенных исследований опубликовано 13 статей в научных журналах, докладах и материалах конференций различного уровня, в том числе три в рецензируемых журналах из перечня ВАК: Kushik N. Minimizing path length in digital circuits based on equation solving / N. Kushik, G. Sapunkov, S. Prokopenko, N. Yevtushenko // Proceedings of IEEE East-West Design & Test Symposium / Kharkov National University of Radioelectronics. - Kharkov, 2008. - P. 365-370.

Кушик Н.Г. Оптимизация комбинационных схем на основе решения уравнений / Н.Г. Кушик, М.В. Рекун // Журнал Сибирского федерального университета «Математика и физика». - 2008. - Т. 1, № 3. - С. 290-295.

Eliseeva N. Symmetrization in Digital Circuit Optimization / N. Eliseeva, J.-H. R. Jiang, N. Kushik, N. Yevtushenko // Proceedings of IEEE East-West Design & Test Symposium / Kharkov National University of Radioelectronics. - Kharkov, 2009. -P. 103-106.

Gromov M. Software package for optimizing digital circuits / M. Gromov, N. Kushik // Proceedings of the Third Spring Young Researchers' Colloquium on Software Engineering / The Institute for System Programming of the Russian Academy of Sciences. - M., 2009. - P. 68-70.

Nikitin A. On EFSM based test generation strategies / A. Nikitin, N. Kushik // Proceedings of the 4th Spring/Summer Young Researchers' Colloquium on Software Engineering / The Institute for System Programming of the Russian Academy of Sciences. - Nizhniy Novgorod, 2010. - P. 116-119.

10

Lin H.-P. Using Boolean relation determinization in digital circuit optimization / H.-P. Lin, W.-L. Hung, M. Gromov, N. Kushik // Новые информационные технологии в исследовании сложных структур : восьмая российская конференция с международным участием : тезисы докладов. - Томск, 2010. - С. 71.

Кушик Н.Г. Локальная оптимизация логических схем с использованием характеристических функций / Н.Г. Кушик, Н.В. Евтушенко // Автоматизация проектирования дискретных систем» (CAD DD'10) : Седьмая Международная конференция : труды. - Минск, 2010. - С. 163-170.

Kushik N. Preset and Adaptive Homing Experiments for Nondeterministic Finite State Machines / N. Kushik, K. El-Fakih, N. Yevtushenko // Lecture Notes in Computer Science. - 2011. - № 6807. - P. 215-224.

Жигулин M.B. Тестирование программной реализации протокола IRC на основе модели расширенного автомата / М.В. Жигулин, A.B. Коломеец, Н.Г. Кушик, A.B. Шабалдин // Известия Томского политехнического университета. - 2011. - Т. 318, № 5. - С. 81-84.

Громов M.JI. Различающие эксперименты с неинициальными недетерминированными автоматами / M.JI. Громов, Н.Г. Кушик, Н.В. Евтушенко // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. - 2011. - № 4. - С. 93-101.

Кушик Н.Г. К синтезу условных установочных экспериментов для недетерминированных автоматов / Н.Г. Кушик, Н.В. Евтушенко // Новые информационные технологии в исследовании сложных структур : девятая российская конференция с международным участием : тезисы докладов. -Томск, 2012.-С. 63.

Кушик Н.Г. Синтез условных синхронизирующих экспериментов для недетерминированных автоматов / Н.Г. Кушик, Н.В. Евтушенко // Известия высших учебных заведений. Физика. - 2012. - Т. 55, № 9/2. - С. 315-316.

Kushik N.G. Homing sequences for nondeterministic finite state machines / N.G. Kushik // Известия высших учебных заведений. Физика. - 2012. - Т. 55, № 8/3. -С. 242-243.

Структура и объем работы. Диссертация состоит из введения, 4 глав, заключения и списка используемой литературы. Диссертация содержит 12 рисунков. Объем диссертации составляет 137 страниц, в том числе: титульный лист - одна страница, оглавление - 3 страницы, основной текст - 124 страницы, библиография из 76 наименований - 8 страниц, приложение - одна страница.

Краткое содержание работы

Первая глава содержит основные определения и обозначения, используемые в диссертационной работе, а также краткий обзор существующих методов синтеза экспериментов с конечными, в том числе недетерминированными, автоматами. Под конечным автоматом понимается система с конечным непустым множеством состояний, конечными алфавитами входных и выходных символов, которая переходит из состояния в состояние при подаче входных воздействий и производит при этом выходные реакции. Автомат называется недетерминированным, если в одном и том же состоянии при подаче одного и того же входного воздействия, автомат может выполнить не один, а несколько различных переходов. В работе рассматриваются неинициальные автоматы, то есть автоматы с выделенным множеством начальных состояний, которое может совпадать со всем множеством состояний. Для детерминированных автоматов кратко излагаются известные результаты по методам синтеза безусловных и условных различающих, установочных и синхронизирующих экспериментов.

Для различающих и установочных экспериментов рассматриваются методы их синтеза на основе усеченного дерева преемников [3, 4]. Сложность установочного эксперимента является полиномиальной относительно числа состояний автомата и, более того, показано [13], что переход от безусловного к условному эксперименту не понижает его сложности. Принципиальное отличие синхронизирующих экспериментов от установочных состоит в том, что в

случае установочных экспериментов выходная реакция автомата позволяет сделать заключение о финальном состоянии. При этом для различных выходных последовательностей финальные состояния могут быть различными. В случае синхронизирующих экспериментов финальное состояние является одним и тем же для всех начальных состояний автомата, т.е. выходная реакция автомата никак не учитывается при выводе заключения. Именно поэтому, во-первых, в основном, рассматриваются безусловные синхронизирующие эксперименты, а, во-вторых, часто вместо модели конечного автомата рассматривается модель полуавтомата, в которой действия не разделены на входные и выходные. Безусловные синхронизирующие эксперименты для полуавтоматов исследовались в работах [14, 15, 16], и в настоящее время такими исследованиями активно занимается научная группа М. В. Волкова [17, 18, 19]. Сложность таких экспериментов оценивается полиномом третьей степени от числа состояний в случае детерминированных полуавтоматов [15], и экспонентой с основанием 2 в случае недетерминированных полуавтоматов [20]. Кроме того, в главе 1 кратко обсуждаются методы синтеза проверяющих и распознающих экспериментов для детерминированных автоматов, которые, как правило, базируются на установочных (синхронизирующих) и различающих экспериментах [8, 21].

Отдельный раздел первой главы посвящен известным результатам по синтезу экспериментов с недетерминированными автоматами. Отмечается, что такие эксперименты изучены значительно хуже. Можно отметить работы [22, 23, 24], в которых рассматриваются различающие эксперименты для двух инициальных автоматов, что в некотором смысле соответствует неинициальному автомату с двумя начальными состояниями. Показано, что в случае безусловного эксперимента длина разделяющей последовательности экспоненциально зависит от числа состояний предъявленных автоматов, в то время как высота условного эксперимента, эффективно представляемого различающим автоматом, полиномиально зависит от числа состояний автоматов [25]. Показана достижимость оценки длины разделяющей

13

последовательности для двух инициальных автоматов [24], тем не менее, число входных символов проверяемых автоматов в данном случае также экспоненциально зависит от числа состояний автоматов. Таким образом, сложность эксперимента по распознаванию двух инициальных автоматов может быть понижена с экспоненциальной до полиномиальной относительно числа состояний автомата за счет перехода от безусловного различающего эксперимента к условному различающему эксперименту. В последнем случае используется эффективное автоматное представление эксперимента [26] и «быстрая» операция пересечения автоматов. Для недетерминированных и частичных полуавтоматов предложены методы синтеза, и установлены оценки сложности синхронизирующих экспериментов [17, 20]; известные результаты также обсуждаются в первой главе.

Во второй главе диссертации исследуются различающие эксперименты с (неинициальными) недетерминированными автоматами [27]. Предлагается метод синтеза безусловного различающего эксперимента для недетерминированного автомата с разделимым множеством начальных состояний. Показывается, что для недетерминированного автомата существует безусловный различающий эксперимент, если и только если множество начальных состояний автомата является разделимым.

Кроме того, подобно работам [25, 26], предлагается представлять условный различающий эксперимент посредством специального автомата, называемого тестовым примером. Тестовый пример является ациклическим автоматом, в каждом не тупиковом состоянии которого определены переходы по единственному входному символу со всеми выходными символами. Вводится понятие различающего тестового примера, показывается, что условный различающий эксперимент с неинициальным недетерминированным автоматом существует, если и только если существует различающий тестовый пример, и предлагается алгоритм построения такого тестового примера (если последний существует). Приводятся оценки сложности условного и

безусловного различающих экспериментов для (неинициальных) недетерминированных автоматов.

Отметим, что различающие эксперименты с автоматами активно используются в задачах тестирования, в частности, при синтезе проверяющих экспериментов. Таким образом, полученные результаты по синтезу различающих экспериментов с недетерминированными автоматами могут быть использованы в методах синтеза тестов в случае, когда поведение проверяемой системы описано недетерминированным автоматом. Кроме того, различающие эксперименты с неинициальными недетерминированными автоматами могут быть использованы в задачах распознавания инициальных автоматов в некотором классе.

Третья глава посвящена исследованию и разработке методов синтеза установочных экспериментов для неинициальных недетерминированных автоматов [28, 29, 30, 31]. Аналогично второй главе, данная глава разделена на две части: в первой части предлагается метод синтеза безусловного установочного эксперимента, и оценивается его сложность, в то время как во второй части предлагаются методы синтеза условного установочного эксперимента. Кроме того, аналогично методам синтеза различающих экспериментов, в главе 3 устанавливаются необходимые и достаточные условия существования безусловных и условных установочных экспериментов для недетерминированных автоматов. Безусловный установочный эксперимент существует, если и только если существует установочная последовательность. Такой эксперимент может быть синтезирован с использованием усеченного дерева преемников. Более того, в третьей главе показывается достижимость экспоненциальной оценки сложности установочного эксперимента, а именно, в разделе 3.2. предлагается класс автоматов с числом состояний п, числом входных символов (п - 1) и числом выходных символов, не превышающем п , для которых длина кратчайшей установочной последовательности равна 2пЛ- 1, т.е. для автоматов этого класса длина установочной последовательности экспоненциально зависит от размера автомата.

В главе 3 вводится понятие установочного тестового примера, показывается, что условный установочный эксперимент существует, если и только если существует установочный тестовый пример, и предлагается метод синтеза такого тестового примера. Кроме того, в главе 3 обсуждается, каким образом полученные в диссертации результаты по синтезу установочных экспериментов могут быть использованы при синтезе синхронизирующих экспериментов для недетерминированных автоматов.

В четвертой главе рассматриваются приложения экспериментов с недетерминированными автоматами для анализа и синтеза дискретных управляющих систем. В частности, обсуждается, каким образом эксперименты, различающие не два, а несколько состояний недетерминированного автомата могут быть использованы для сокращения длины проверяющих тестов. В качестве примера эффективного использования недетерминированных автоматов и других конечно автоматных моделей для синтеза проверяющих тестов для реальных систем рассматривается тестирование доступной реализации протокола IRC [32, 33]. Во второй части главы рассматриваются эксперименты с компонентой автоматной сети, в частности, рассматривается возможность использования установочных экспериментов с недетерминированными автоматами для установки компоненты сети в известное состояние. Кроме того, исследуется задача оптимизации автоматной сети через упрощение одной из ее компонент. Эксперименты по такому упрощению проводятся для контрольных примеров из сети Интернет (бенчмарок) и схем аппаратного шифрования [34, 35, 36, 37, 38, 39].

В заключении подводится итог результатам, полученным в диссертации, формулируются основные положения, выносимые на защиту, а также освещаются перспективы дальнейших научных исследований.

1. Обзор существующих методов синтеза «умозрительных» экспериментов с конечными автоматами

Диссертация посвящена исследованию и разработке методов синтеза установочных и различающих экспериментов с недетерминированными автоматами. В первой главе вводятся основные определения и обозначения, используемые в диссертации. Кроме того, в данной главе предлагается обзор известных результатов по «умозрительным» экспериментам с детерминированными и недетерминированными автоматами.

1.1 Основные определения и обозначения

1.1.1 Конечные автоматы и отношения между ними

Поведение ряда технических систем, в том числе с частичным и/или недетерминированным поведением может быть описано при помощи модели конечного автомата. Конечные автоматы, как правило, моделируют так называемые реактивные системы, которые работают в режиме «запрос/отклик». Запросы интерпретируются как входные действия (входные символы) моделируемой системы, а отклики как выходные реакции (выходные символы). Последовательности пар «входной_символ/выходной_символ» образуют входо-выходные последовательности конечной длины (более формальное определение будет введено ниже), и в этом случае автомат можно рассматривать как преобразователь, реализующий отображение бесконечного множества входных последовательностей в множество подмножеств выходных последовательностей. Преимущество конечных автоматов отчасти заключается в возможности конечного представления такого в общем случае бесконечного отображения. В диссертации рассматриваются неинициальные системы, т.е. системы, начальное состояние которых является неизвестным. Более того, мы рассматриваем системы с недетерминированным поведением для их дальнейшего анализа и синтеза на основе автоматных моделей. Соответственно, в данном разделе приводятся основные определения и обозначения из теории автоматов, которые будут далее использованы в кандидатской диссертации.

17

Под конечным автоматом (или просто автоматом) [40] понимается пятерка 5= (£, I, О, £'), где конечное непустое множество состояний с выделенным непустым множеством начальных состояний , / и О - конечные непустые входной и выходной алфавиты соответственно, такие, что /пО = 0и с: 5 х I х О х £ - отношение или множество переходов. Автомат называется инициальным, если |5"| = 1, в противном случае автомат называется неинициальным. Четверка (.?,/, о, я') е /называется переходом в автомате в состоянии 5 или переходом из состояния 5 в состояние я'. Состояние я' называется г/о-преемником состояния 5 е 5 для е I, о е О, если четверка (5, /, о, содержится в Соответственно можно определить множество всех г/о-преемников состояния 5 е £ как множество {з'е Я | (.у, ¿, о, я') е /г,?}. Говорят, что поведение автомата 5 определено в состоянии 5 для входного символа г, если существует пара (о, «') е О х 5 такая, что (5, г, о, л') е /г^. Достаточно часто для наглядности автомат представляется ориентированным графом (диаграммой переходов), в котором вершины суть состояния автомата, а дуги помечены парами «входной_символ/выходной_символ». Из вершины 5 есть дуга в вершину помеченная парой 1/0, если и только если 5' есть 1/0-преемник состояния Если не все состояния автомата являются начальными, то вершины, соответствующие начальным состояниям автомата, обводятся жирной линией. В некоторых случаях автомат удобно представлять таблицей переходов, строкам которой приписаны входные символы автомата, а столбцам - состояния автомата. В клетках таблицы расположены пары «следующее_состояние/выходной_символ» для каждой пары

«входной_символ/текущее_состояние», помечающей соответствующие строку и столбец. Возможны и другие способы представления автомата (например, явным перечислением переходов или каноническими уравнениями), тем не менее, далее в диссертации мы, в основном, будем пользоваться либо диаграммой переходов, либо таблицей переходов.

Если в автомате 5 для любой пары (я, /) е 5 х / существует, по крайней мере, одна пара (о, я') е Ох. £ такая, что (л, /, о, 5') е то автомат называется полностью определенным, в противном случае автомат называется частичным. В полностью определенном автомате из каждого состояния существует переход под действием любого входного символа. В частичном автомате из некоторого состояния может не быть ни одного перехода под действием некоторого входного символа. Автомат 5 называется детерминированным, если для любой пары (5, г) е £ х / существует не более одной пары (о, У) е О х 5 такой, что (5, /', о, 5') е В противном случае автомат называется

недетерминированным.

Если в недетерминированном автомате 5 для любой тройки (5, /,о)б5х/хО существует не более одного состояния б' е £ такого, что (5, 1, о, я') е то автомат называется наблюдаемым, в противном случае автомат называется ненаблюдаемым [41]. Пример. Рассмотрим автомат 5, приведенный на рисунке 1.1.

Заметим, что автомат 5 содержит два состояния 1 и 2, один входной символ / и три выходных символа 0\, о2 и о3. Ни одно из состояний не обведено жирной линией, т.к. начальными являются оба состояния. Автомат на рис. 1.1 является полностью определенным, поскольку в каждом состоянии определен, по крайней мере, один переход. Кроме того, автомат 5 является недетерминированным, в частности, в состоянии 1 под действием входного символа / определены два перехода в различные состояния и с различными выходными символами. Заметим также, что в данном примере автомат 5 является наблюдаемым, поскольку в каждом состоянии любая пара

Рисунок 1.1 - Автомат 5

«входной_символ/выходной_символ» однозначно определяет финальное состояние каждого перехода.

Параллельно с отношением переходов в автомате часто используют две функции: функцию переходов (функцию next_states) и функцию выходов (функцию outs), определенных следующим образом

next_states(s, i) э s', если 3 о е О, (s, i, о, s') е hs\ outs(s, i) э о, если 3ï'e5,(i, i, о, s') е hs.

Для детерминированных полностью определенных автоматов функции next_states и out $ полностью определяют поведение автомата, т.е. по функциям можно однозначно восстановить отношение переходов. Недетерминированные автоматы с различным поведением могут иметь одни и те же функции next_states и outs [40], но различные отношения переходов.

Отношение переходов обычным образом распространяется на последовательности (слова) в алфавитах I и О. Обозначим через Г множество всех последовательностей конечной длины в алфавите I, включая пустую последовательность s. Как обычно, через Г* мы обозначаем множество всех последовательностей из Г длины т, т.е. последовательностей, содержащих m символов. Соответственно, функции переходов next_states и выходов outs можно распространить на последовательности входных и выходных символов. В этом случае множество next_state^s, а) включает те и только те состояния, которые достижимы в автомате 5 из состояния s по входной последовательности а. Множество out^s, а), соответственно, включает все возможные выходные последовательности (реакции) автомата 5 в состоянии s на входную последовательность а.

В частичном автомате в состоянии s для некоторых входных последовательностей а е f множество out^s, а) может оказаться пустым; в этом случае говорят, что поведение автомата в состоянии s не определено на входной последовательности а. Входные последовательности, на которых поведение автомата в состоянии s определено, будем называть определенными

или допустимыми последовательностями в состоянии s. Множество таких последовательностей далее обозначается Q^s).

Пара (а, Р), а е Q^), Р е outs(s, а), называется входо-выходной последовательностью автомата 5 в состоянии s. Множество всех входо-выходных последовательностей в состоянии s обозначается Tr^s), т.е. Tr^s) = {(а, Р) | а е Q5(5) & р е outs(s, а)}. Объединение множества всех входо-выходных последовательностей в начальных состояниях автомата 5 обозначается Trs= у7>5(.у)и часто называется языком автомата 5. Функция outs

seS'

естественным образом распространяется на множество состояний. Для подмножества Мсостояний автомата 5,Мс5, и входной последовательности а е Q^s), s е М, outs{M, а)= \Jouts(s,a).

seM

Состояния si и s2 полностью определенного автомата 5= (S, I, О, hs> S') называются эквивалентными (обозначение: s\ = если V а е Г (out^s 1, а) = oui^S2, а)). Аналогичным образом определяется эквивалентность состояний двух различных полностью определенных автоматов. Будем говорить, что автомат 5 является приведенным или минимальным, если все его состояния являются попарно не эквивалентными. Автомат 5 называется связным, если каждое состояние этого автомата достижимо из некоторого начального состояния по некоторой входо-выходной последовательности. Автомат называется сильно связным, если каждое состояние достижимо из каждого состояния данного автомата по некоторой входо-выходной последовательности. Заметим, что автомат в рассмотренном примере (рисунок 1.1) является сильно связным и приведенным, поскольку состояния автомата 1 и 2 не являются эквивалентными.

Для полностью определенных автоматов можно ввести отношение эквивалентности на подмножествах состояний. Подмножества состояний М автомата 5 и В автомата Р называются эквивалентными, если для любой входной последовательности а имеет место out^M, а) = outJJB, а). Автоматы

5 и Р эквивалентны (обозначение: 5= Р), если для каждого состояния множества 5" в множестве Р' существует эквивалентное состояние, и обратно.

Говорят, что состояние р автомата Р = (Р, /, О, Ьр, Р') есть редукция состояния 5 автомата 5= {Б, /, О, 5") (обозначение: р < 5), если ТГ[£р) с Тг^). Если Ря 5 полностью определенные автоматы, то состояния р и 5 эквивалентны, если и только если состояние р есть редукция СОСТОЯНИЯ и состояние ^ есть редукция состояния р. Для полностью определенных автоматов 5 и Р подмножество состояний М автомата 5 называется редукцией подмножества В автомата Р, если для любой входной последовательности а имеет место оШ^М, а) с= оШ^В, а), и подмножества состояний М и В эквивалентны, если и только если М есть редукция В и В есть редукция М. Аналогично отношение редукции вводится для двух (подмножеств) состояний одного автомата. Автомат 5есть редукция автомата /'(обозначение: 5< Р), если каждое состояние множества есть редукция некоторого состояния из множества Р'.

Пусть 5 = I, О, /г5, ) и Р - (Р, 1,0, , р0 ) суть полностью определенные инициальные недетерминированные автоматы, введем понятие пересечения 5п Рэтих автоматов. Пересечение 5п Р [40] есть наибольший связный подавтомат автомата 0, состояниями которого являются пары (я, р), где 5 е^ир еРс начальным состоянием (я0,р0). Для входо-выходной пары Но существует переход ((з,р), I, о, ($',/?')) из состояния р), если и только если (5, г, о, 5') е И (р, и о,р') € Ир.

1.1.2 Полуавтоматы. Отношения между ними. Детерминизация

Отметим, что понятие автомата очень близко к понятию полуавтомата, в котором действия не делятся на входные и выходные, и которые используются для конечного представления регулярных языков [42, 43] 1 . Конечный

1 Заметим, что в литературе 50-70-х годов прошлого века в большинстве публикаций не делается особого различия между автоматами и полуавтоматами, и обе модели называются просто автоматами (automata).

полуавтомат, далее часто называемый просто полуавтоматом, есть пятерка (5, V, 8г, /V, 5"), где конечное непустое множество состояний с выделенным непустым подмножеством начальных состояний 5" и непустым подмножеством Р/ финальных состояний, V - конечное непустое множество действий, И 5 X

Л

V х 51 есть отношение переходов . Финальные состояния можно рассматривать как состояния, в которых заканчиваются последовательности действий, соответствующих выполнению требуемого задания. Подобно автоматам, мы говорим, что существует переход ИЗ СОСТОЯНИЯ 5 в состояние под действием V, если и только если тройка (я, V, я') принадлежит отношению переходов 8Р. Состояние р, из которого нет переходов, называется тупиковым. Аналогичным образом определяется связность полуавтомата как возможность достижимости каждого состояния автомата по некоторой допустимой последовательности действий из некоторого начального состояния автомата.3

Полуавтомат / называется детерминированным, если для каждого состояния ,у е £ и действия V е V существует не более одного СОСТОЯНИЯ 5 ', такого что (я, V, 5 *) е 5р\ в противном случае / называется недетерминированным полуавтоматом.

Аналогично конечным автоматам отношение переходов распространяется на последовательности в алфавите V, и язык полуавтомата определяется как объединение множеств допустимых последовательностей действий в начальных состояниях. Пустая последовательность принадлежит языку если и только если хотя бы одно начальное состояние является финальным.

Полуавтомат £ называется редукцией полуавтомата /(обозначение: £< если язык полуавтомата £ содержится в языке полуавтомата X, т.е. Дф с: Ь{$). Полуавтоматы /и /Сназываются эквивалентными (обозначение: £= X), если их языки совпадают, т.е. £есть редукция /и /есть редукция £

2 В данной работе мы не рассматриваем в полуавтомате ненаблюдаемое действие т, тем не менее, отмечаем, что в

усложненной модели полуавтомата, предназначенной для описания систем с буферной памятью, такое действие может оказаться необходимым.

3 В общем случае действия в полуавтомате могут быть разделены на входные и выходные, однако в нашей работе мы такие

полуавтоматы не рассматриваем.

Отметим, что достаточно хорошо известны следующие основополагающие результаты из теории автоматов [43] о связи конечных полуавтоматов и их языков. Для каждого полуавтомата существует эквивалентный полуавтомат с одним начальным состоянием, и для каждого недетерминированного полуавтомата существует эквивалентный детерминированный полуавтомат. Требуемые полуавтоматы могут быть получены с применением так называемой процедуры детерминизации. Детерминированный полуавтомат, эквивалентный полуавтомату /= (S, V, 6 s, Fs, S'), получается на основе замены состояний недетерминированного полуавтомата подмножествами его состояний (в иностранной литературе используется термин subset construction) [43]. Таким образом, для получения эквивалентного детерминированного полуавтомата строится полуавтомат й —

(D, V, S в, Fb, d0), где D есть множество всех непустых подмножеств множества S, d0 соответствует подмножеству начальных состояний S', И Fa содержит каждое подмножество из S, которое включает хотя бы одно финальное состояние. Если d,d' е D суть состояния полуавтомата Z) и а е V, то тройка (d, a, d') е Sd , если и только если z ' = {d 3 s e d {{s, a, s}) e <3r)}. Наибольший связный подавтомат полуавтомата й будем называть детерминированной формой полуавтомата /(обозначение: £/(/)).

Пример. Рассмотрим полуавтомат S с таблицей переходов 1.1а.

Полуавтомат имеет три состояния, каждое из которых может быть его

начальным состоянием, т.е. S = S' = {1, 2, 3}. Множество Vдействий данного

полуавтомата есть V= {а, Ь}. Построим полуавтомат £с множеством состояний

D ~ (Ob (2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}. Непосредственной проверкой

можно убедиться, что состояния {1}, {2}, {1, 2} недостижимы из начального

состояния {1, 2, 3}. Таким образом, детерминированная форма £f{S) содержит

четыре состояния. Соответствующий полуавтомат (таблица переходов)

приведен в таблице 1.16. Заметим, что при записи подмножеств состояний, в

частности, для обозначения состояний эквивалентного автомата мы в

24

некоторых случаях опускаем фигурные скобки (для более компактной записи), используя надчеркивание.

Таблица 1.1- таблицы переходов полуавтоматов /и Д/%5) а б

/АУ 1 2 3

а 2,3 3 1,3

Ъ 2 3 3

1,2,3 2,3 й 3

1,2,3 и 1,2,3 и

2,3 3 2!> 3

Дерево преемников автомата

Дерево преемников хорошо известно в теории автоматов и достаточно широко применяется для решения задач анализа и синтеза [3, 4, 16]. Классическое дерево преемников было введено для детерминированного автомата и является бесконечным, т.к. представляет поведение автомата на всех входных последовательностях. При построении экспериментов с конечными автоматами используется так называемое усеченное дерево преемников, причем правила усечения являются различными при построении различных экспериментов. В настоящий момент предложен ряд алгоритмов с использованием усеченного дерева преемников для синтеза экспериментов с недетерминированными автоматами [27, 28], временными автоматами [44] и др.

Определим дерево преемников автомата формально. Пусть 5= (5, I, О, Из, 5"') - конечный автомат с множеством входных символов / = {/ь ¿2, ..., /„}, множеством выходных символов О = {<?!, о2, ..., от}, множеством состояний 5= {^ь 52> •••> и множеством начальных состояний 5" = , ...,

}. Вершины классического дерева преемников помечаются подмножествами

состояний из множества 5 автомата 5, дуги - входными символами или входо-

выходными парами. Корень дерева помечен некоторым фиксированным

состоянием 5 или подмножеством состояний, как правило, начальных, т.е. Я'. Из

вершины, помеченной множеством Я состояний, есть дуга, помеченная входо-

выходной парой Но, в вершину, помеченную множеством всех г'/о-преемников

25

состояний из Я. При построении дерева, дуги которого помечаются только входными символами, вершина, смежная с вершиной, помеченной подмножеством Я, помечается множеством, включающим все /-преемники состояний из Я (со всеми возможными выходными символами). Таким образом, последовательности, помечающие ветви дерева, описывают все входо-выходные (входные) последовательности в состоянии .у (множестве начальных состояний 5"), которое помечает корень дерева. Соответственно, дерево преемников высоты к описывает все входо-выходные (входные) последовательности длины к в состоянии £ (множестве начальных состояний £'). Как уже отмечалось, дерево преемников является бесконечным. Иными словами, дерево преемников представляет бесконечную развертку поведения автомата в заданном состоянии/множестве заданных, например, начальных, состояний.

С точки зрения экспериментов с конечными автоматами наибольший интерес представляет вопрос об усечении ветвей данного дерева. Кроме того, при построении экспериментов с автоматами классического дерева преемников обычно недостаточно, и авторы [2, 4, 16] предлагают различные модификации усеченного дерева преемников, такие как диагностическое дерево, установочное дерево, синхронизирующее дерево. При этом вершины дерева обычно помечаются не отдельными состояниями автомата, а совокупностью (списком) подмножеств состояний. В частности, если автомат неинициальный, как уже отмечалось, то корень дерева помечается множеством 5' = { ^ , , ..., } начальных состояний автомата.

Пример. Рассмотрим автомат 5, представленный на рисунке 1.2 с двумя начальными состояниями 1 и 2. Фрагмент дерева преемников, описывающий возможные переходы автомата на всех входных последовательностях длины два, приведен на рисунке 1.3.1а. На рисунке 1.3.16 приведена развертка автомата на всех входо-выходных последовательностях длины два.

Рисунок 1.2 - Автомат 5

Рисунок 1.3.1а- Фрагмент дерева преемников автомата 5 (рисунок 1.2)

Рисунок 1.3.16- Фрагмент дерева преемников автомата 5 (рисунок 1.2)

1.2 Эксперименты с полностью определенными автоматами

В ряде приложений, таких как тестирование дискретных систем [7, 8, 9,

10, 21, 45, 46], диагностика таких систем [47] и т.д. используются так

называемые (умозрительные) эксперименты с полностью определенными

автоматами [1]. Понятие таких «умозрительных экспериментов» было впервые

введено в одноименной статье Э. Муром [1], и для детерминированных

автоматов такие эксперименты хорошо изучены. Соответственно, в данном

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

автоматами, а также приводятся установленные ранее оценки их сложности.

Среди экспериментов рассматриваются синхронизирующие,

установочные и диагностические эксперименты. Далее кратко рассматриваются

проверяющие и распознающие эксперименты, которые, как правило,

базируются на синхронизирующих/установочных и диагностических

(различающих) экспериментах. В большинстве публикаций по экспериментам

27

рассматриваются только полностью определенные автоматы и полуавтоматы, поэтому в этом разделе по умолчанию рассматриваются эксперименты только с полностью определенными автоматами (если обратное явно не оговорено).

1.2.1 Краткая классификация экспериментов

Под экспериментом с автоматом [1] понимается подача некоторой входной (-ых) последовательности (-ей) на вход интересующего нас автомата, наблюдение выходной (-ых) реакции (-ий) на эту (эти) последовательность (-ти) и формирование заключения о некоторых свойствах автомата. Для детерминированных автоматов выходная последовательность автомата однозначно вычисляется по входной последовательности и начальному состоянию, поэтому сложность эксперимента обычно оценивается сложностью генерации необходимой входной последовательности и/или длиной такой последовательности.

В различающих (диагностических), установочных и синхронизирующих экспериментах предполагается [2], что известны входной и выходной алфавиты, множество состояний автомата, в том числе начальных, а также отношение переходов автомата, с которым проводится эксперимент. В различающем эксперименте требуется определить состояние автомата до эксперимента (начальное состояние), в установочном и синхронизирующем экспериментах -состояние после эксперимента (финальное состояние). Основное отличие установочных и синхронизирующих экспериментов заключается в следующем: в синхронизирующем эксперименте финальное состояние после эксперимента для всех начальных состояний автомата одно и то же; в установочном эксперименте финальное состояние автомата определяется однозначно по наблюдаемой выходной последовательности автомата.

В проверяющих и распознающих экспериментах [2, 48] рассматривается некоторый класс автоматов. Иными словами, предполагается, что имеется некоторое множество автоматов, и один из этих автоматов предъявлен к эксперименту (тестируемый автомат или реализация). В проверяющем

28

эксперименте требуется определить, находится ли тестируемый автомат в определенном отношении с некоторым другим автоматом, который называется эталонным автоматом или автоматом-спецификацией. В распознающих экспериментах требуется определить, какой именно автомат из заданного множества предъявлен к эксперименту.

Эксперименты также разделяют на безусловные и условные [1, 2]; последние в современной литературе часто называются адаптивными [9, 49]. В безусловных экспериментах входная (-ые) последовательность (-ти) генерируется (-ются) заранее (до эксперимента) и не изменяется (-ются) в процессе эксперимента. В условных экспериментах следующий входной символ последовательности зависит от реакции тестируемого автомата на предыдущие входные символы.

Заметим, что в ряде случаев сложность условного эксперимента может быть ниже сложности безусловного [25], тем не менее, условные эксперименты могут оказаться сложнее в их проведении, чем безусловные, поскольку требуют дополнительного аппаратного и/или программного обеспечения.

По способу проведения эксперимента эксперименты также разделяют на простые и кратные [2]. При проведении простого эксперимента, предполагается, что существует только одна копия тестируемого автомата. Этот факт можно также интерпретировать как наличие одной входной последовательности, подаваемой на автомат во время эксперимента. При проведении кратного эксперимента подразумевается наличие нескольких копий автомата. В этом случае можно считать, что в эксперименте участвуют несколько входных последовательностей. Кратные эксперименты активно используются для инициальных автоматов, которые описывают поведение систем, обладающих надежным сигналом сброса; такие эксперименты используются, в частности, в задачах тестирования систем, поведение которых описывается конечными автоматами, например, при синтезе тестов для проверки реализаций телекоммуникационных протоколов [8, 10, 21, 23].

1.2.2 Различающие (диагностические) эксперименты с детерминированными автоматами

Отметим, что различающие эксперименты с детерминированными автоматами хорошо изучены, особенно в случае, когда автомат, предъявленный

4

к эксперименту, является полностью определенным и приведенным Остановимся на этом классе автоматов более подробно.

Говорят, что состояния и 52 детерминированного автомата

5= (3,1, О, /гя, 5") различимы, если существует входная последовательность а такая, что ь а) Ф оШд(з2, а). В этом случае последовательность а

называется различающей последовательностью для состояний 51 и 52- Входная последовательность а, которая различает любую пару начальных состояний в автомате, называется диагностической последовательностью. Известно [2], что простой безусловный эксперимент с автоматом, позволяющий определить начальное состояние, существует, если и только если автомат обладает диагностической последовательностью. Поэтому такой эксперимент часто называют диагностическим экспериментом, и, соответственно, под построением такого эксперимента понимают синтез диагностической последовательности.

Известно также [3, 4, 7], что диагностическая последовательность существует не для всякого приведенного детерминированного автомата. Более того, необходимые и достаточные условия существования диагностической последовательности формулируются на основе анализа дерева преемников автомата, усеченного по специальным правилам и называемого диагностическим деревом [4].

Кратные безусловные различающие эксперименты в основном используются при построении проверяющих тестов для систем, поведение которых может быть описано конечными автоматами. Для любого (полностью определенного) приведенного инициального автомата существует кратный

4 Известно, что для не приведенного автомата, у которого каждое состояние может быть начальным, различающего эксперимента не существует.

диагностический эксперимент, причем для автомата с п состояниями длина каждой входной последовательности не превышает5 разности (п — 1), и число последовательностей не превышает С„2. Условные различающие эксперименты практически не исследовались для детерминированных автоматов, в силу полиномиальной оценки сложности безусловных различающих экспериментов. Тем не менее, в литературе отмечается, что такие эксперименты могут быть использованы при распознавании инициального автомата в так называемом исключительном классе, т.е. множестве автоматов, в котором все автоматы попарно не эквивалентны [50, 51].

Для недетерминированного автомата для различимости состояний необходимо предположение о всех погодных условиях (all weather conditions) [52, 53]. Такое предположение накладывает на автомат следующее требование: в каждом состоянии на каждый входной символ можно пронаблюдать всевозможные выходные реакции. Иными словами, в каждом состоянии мы имеем право подавать на автомат входную последовательность до тех пор, пока не пронаблюдаем каждую возможную выходную последовательность. Более подробно известные результаты по экспериментам с недетерминированными автоматами обсуждаются в разделе 1.3.

1.2.3 Установочные эксперименты с детерминированными автоматами

Установочные эксперименты с детерминированными автоматами, так же как и различающие эксперименты, достаточно хорошо изучены [3, 4, 16]. Показано, что для всякого детерминированного связного приведенного автомата с п состояниями существует простой установочный эксперимент, высота которого не превосходит величины Сп = п{п - 1)/2 [4]. Заметим, что в простом установочном эксперименте используется только одна входная последовательность, которая довольно часто называется установочной последовательностью (homing sequence) [4, 16]. Установочная

5 Для частичных детерминированных автоматов длина входной последовательности, различающей два состояния автомата с п состояниями, может достигать С„2 [40].

последовательность есть такая входная последовательность для заданного автомата, после подачи которой на автомат и наблюдения выходной реакции автомата финальное состояние автомата определяется однозначно. По определению, для детерминированного автомата 5 = (5,1, О, 5) последовательность а е / называется установочной последовательностью, если

а) Ф а) => а) ф оШ(з2,а)

Записанная выше импликация может быть интерпретирована следующим образом: как только следующие состояния автомата не совпадают для установочной последовательности а, выходные реакции автомата на эту последовательность также отличаются.

Заметим, что, как и для простого различающего эксперимента, синтез установочной последовательности было предложено производить на основании специального усеченного дерева преемников [4, 16], которое принято называть установочным деревом.

Оценка достижимости полинома второй степени как длины установочной последовательности приводится, в частности, в [4]. При доказательстве соответствующего утверждения авторы работы [4] предлагают еще один способ синтеза установочной последовательности для детерминированных автоматов. Этот способ основан на итеративном построении множеств попарно различимых состояний. Отмечается, что в худшем случае длина установочной последовательности для приведенного сильно связного автомата с п состояниями составляет п(п - 1 )/2, однако последовательность, построенная по установочному дереву преемников, может быть короче, чем последовательность, построенная на множествах попарно различимых состояний.

Хиббард [13] также показал, что сложность установочного эксперимента в общем случае нельзя понизить при переходе к условному эксперименту. В частности, высота условного установочного эксперимента также оценивается

полиномом второй степени от числа состояний автомата, предъявленного к эксперименту.

Заметим, что в литературе рассматривается разработка параллельных и вероятностных алгоритмов синтеза установочных экспериментов для детерминированных автоматов [см., например, 54], и с использованием этих алгоритмов установочная последовательность может быть найдена быстрее.

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

Синхронизирующие эксперименты активно рассматривались в работах [15, 14], и в настоящее время изучаются в научной группе М.В. Волкова (УФУ, Россия) [17, 18, 19]. В работе [16] приведен достаточно полный обзор известных результатов по синтезу синхронизирующих экспериментов для автоматных моделей.

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

терминологии. Соответственно, под детерминированным автоматом авторы соответствующих работ понимают детерминированный полуавтомат.

Для детерминированных полуавтоматов, в которых в каждом состоянии определен переход по любому действию, предложены методы синтеза синхронизирующих последовательностей, и установлен ряд оценок сложности. В частности, показано [15], что длина синхронизирующей последовательности ограничивается полиномом третьей степени относительно числа состояний автомата. Гипотеза Черни [14] предполагает понижение степени такого полинома на единицу, однако в настоящей момент известны лишь частные классы детерминированных полуавтоматов, для которых эта гипотеза имеет место.

В разделе 1.3 кратко обсуждаются известные результаты по синхронизирующим экспериментам с недетерминированными полуавтоматами и, в том числе, с частичными полуавтоматами, в которых в некоторых состояниях могут быть не определены переходы по некоторым действиям.

1.2.5 Проверяющие и распознающие эксперименты

В проверяющих и распознающих экспериментах эксперимент проводится с некоторым (неизвестным) автоматом из заданного класса. Такие эксперименты позволяют выявить некоторые свойства автомата, предъявленного для эксперимента, например, проверить, находится ли проверяемый автомат в некотором отношении соответствия (конформности) с эталонным автоматом, причем для детерминированных полностью определенных автоматов в качестве такого отношения конформности рассматривается отношение эквивалентности. Заметим, что проверяющие и распознающие эксперименты часто базируются на

установочных/синхронизирующих и различающих экспериментах и используются в задачах тестирования различных дискретных систем [см., например, 7, 48, 53].

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

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

6 Таким образом, такой проверяющий эксперимент, вообще говоря, не является «чисто» безусловным.

35

состояний, чем эталонный автомат. Соответственно, на первом шаге проверяется, что число состояний тестируемого автомата совпадает с числом состояний эталонного автомата, и устанавливается взаимно однозначное соответствие между состояниями эталонного и проверяемого автоматов с использованием диагностической последовательности, т.е. в соответствующих состояниях проверяемого и эталонного автоматов совпадают выходные реакции на диагностическую последовательность. На втором шаге проверяется, что установленное соответствие между состояниями выполняется для всех переходов тестируемого автомата. Ф. Хенни показал [7], что длина такой последовательности существенно зависит от длины диагностической последовательности, т.е. в общем случае длина проверяющей последовательности экспоненциально зависит от числа состояний автомата, однако для определенных классов автоматов показано, что длина проверяющей последовательности является полиномиальной относительно числа состояний автомата [48]. В случае, если эталонный автомат не обладает диагностической последовательностью, проверяющая последовательность также может быть построена, однако ее длина может оказаться значительно больше [7]. Если число состояний тестируемого автомата не ограничено, то проверяющей последовательности (полного проверяющего теста) не существует [2]. Более того, не известно, как в общем случае построить проверяющую последовательность, если число состояний т проверяемого автомата может быть больше числа п состояний эталонного автомата.

Существует достаточно много работ по синтезу кратного проверяющего эксперимента [см., например, 8, 11, 21]. В этом случае предполагается, что тестируемая система обладает надежным сигналом сброса, т.е. эталонный и тестируемый автоматы являются инициальными, и соответственно, можно использовать несколько копий тестируемого автомата. Если число состояний тестируемого автомата не ограничено и отсутствуют какие-либо другие ограничения на класс проверяемых автоматов, то в общем случае не существует и кратного проверяющего эксперимента. Однако если известно, что число

36

состояний тестируемого автомата не превышает некоторого числа т > п, то можно построить кратный проверяющий эксперимент, в том числе и в случае, когда эталонный автомат не обладает диагностической последовательностью. Впервые способ построения такого эксперимента был предложен М.П. Василевским [21]; в этой же статье приводятся оценки длины такого эксперимента. В частности, показано, что при т = п общая длина теста определяется полиномом третьей степени от числа состояний автомата-спецификации. При т > п длина соответствующей последовательности экспоненциально зависит от разности {т - п), и эта оценка не понижается. Заметим, что общая идея метода, предложенного М. П. Василевским, заключается в следующих двух положениях: 1) покрыть каждый переход в проверяемом автомате и 2) убедиться в правильности финального состояния для каждого перехода в проверяемом автомате. Для этого для эталонного автомата строятся так называемые множества достижимости и различимости, на основании которых далее строятся тестовые последовательности. Более простое изложение результатов работы М. П. Василевского было предложено в работе [8], после чего тесты, построенные по автоматным моделям, стали активно использоваться для тестирования реализаций различных протоколов

[5].

В настоящее время продолжаются исследования по сокращению общей

длины теста, построенного на основании множеств достижимости и

различимости. Достаточно серьезный обзор по синтезу таких проверяющих

экспериментов (проверяющих тестов) для детерминированных автоматов, а

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

систем приведены, в частности, в [10]. Более того, в 2009 году появилась статья

с новым способом построения проверяющего эксперимента [11]. Нам не

известно каких-либо результатов по построению условных проверяющих

экспериментов с детерминированными автоматами. Отсутствие таких

результатов обуславливается тем, что процесс тестирования реализации с

выводом о неэквивалентности тестируемого и эталонного автоматов делается

уже при появлении любой не эталонной реакции на подаваемую входную последовательность; соответственно, отсутствует необходимость подавать следующую тестовую последовательность (символ тестовой последовательности).

При проведении распознающего эксперимента, аналогично проверяющему, к эксперименту предъявлен автомат из известного класса. В результате эксперимента требуется установить, какой именно автомат из заданного класса предъявлен к эксперименту.

Распознающие эксперименты изучались, в основном, для случая детерминированных полностью определенных автоматов [4, 51]. Тем не менее, глубокие результаты в данной области не были получены даже для инициальных детерминированных автоматов. В основном все известные методы распознавания автоматов в заданном классе сводятся к построению прямой суммы автоматов из класса и построению различающего эксперимента для полученного неинициального автомата [4]. Поскольку задача распознавания автоматов в классе в целом сводится к задаче синтеза различающих экспериментов для неинициальных автоматов, сложность задачи распознавания существенно зависит от числа автоматов в классе. Данная задача не рассматривается в данной диссертации, поэтому мы не останавливаемся на ней более подробно, тем не менее, мы отмечаем, что полученные результаты по синтезу различающих экспериментов для недетерминированных автоматов могут быть напрямую использованы при распознавании конечного числа недетерминированных автоматов в заданном классе.

1.3 Известные результаты по экспериментам с недетерминированными автоматами

Диссертация посвящена исследованию и разработке методов синтеза установочных и различающих экспериментов для недетерминированных автоматов, а также примерам использования таких автоматов для анализа и синтеза реальных технических систем. Соответственно, в отдельный раздел

38

настоящей диссертации мы выделяем известные результаты по синтезу установочных и различающих экспериментов для недетерминированных автоматов. Мы отмечаем также, что такие эксперименты изучены значительно хуже, по сравнению с экспериментами с детерминированными автоматами.

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

Спектр отношений различимости для недетерминированных автоматов намного шире, чем для детерминированных [23, 25, 40], где в качестве отношения различимости для полностью определенных автоматов рассматривается только отношение неэквивалентности. В случае недетерминированных автоматов, в качестве таких отношений могут быть рассмотрены: отношение внешней различимости (неэквивалентности), отношение «не быть редукцией», отношение разделимости и отношение г-различимости.

Заметим, что для проверки отношения эквивалентности между недетерминированными автоматами в общем случае недостаточно простого эксперимента, поскольку необходимо проверить совпадение множеств выходных реакций. Соответственно, при тестировании относительно различимости приходится обращаться к рассмотренному выше предположению «о всех погодных условиях», что часто оказывается не реализуемым на практике. Тем не менее, построение простых различающих экспериментов возможно относительно отношений неразделимости и г-различимости. Такие эксперименты, в частности, рассматривались в работах [22, 23, 25, 55]. Заметим, однако, что в перечисленных работах речь идет о различимости двух инициальных автоматов, т.е. фактически о недетерминированном автомате с двумя начальными состояниями. В настоящей диссертации во второй главе предлагается метод построения различающего эксперимента для недетерминированного автомата с произвольным числом начальных состояний.

Остановимся на введенных отношениях более подробно. Говорят, что

состояния и полностью определенного автомата 5= (5, /, О, /5")

39

разделимы, если существует входная последовательность а такая, что а) п оМд(я2, а) = 0, т.е., если множества выходных последовательностей автомата в состояниях ^ и 52 на входную последовательность а не пересекаются. Состояния автомата и б2 г-различимы, если любое состояние любого полностью определенного автомата не может быть редукцией одновременно состояний 51 и 52- Во втором случае существует так называемый различающий автомат для этих состояний. Такой автомат вводится в работах [25, 26], и на основе свойств этого автомата устанавливаются необходимые и достаточные условия существования условного различающего эксперимента. Разделяющая последовательность используется для синтеза безусловного различающего эксперимента, в то время как различающий автомат представляет условный различающий эксперимент. Кроме того, показано [22, 24], что сложность безусловного эксперимента для двух инициальных автоматов в общем случае экспоненциально зависит от числа состояний автоматов, в то время как сложность условного эксперимента, оцениваемая как длина самой длинной входо-выходной последовательности в различающем автомате, полиномиально зависит от числа состояний автоматов. Соответственно, переход от безусловного различающего эксперимента к условному для двух инициальных автоматов позволяет существенно понизить сложность различающего эксперимента.

Пример. Рассмотрим автомат 5 с множеством начальных состояний {1, 3}, двумя входными и двумя выходными символами, представленный на рисунке 1.4.

Заметим, что входная последовательность 12н является разделяющей для состояний 1 и 3. Соответственно, она представляет собой безусловный различающий эксперимент для этого автомата, поскольку при подаче /2**1 и наблюдении выходной последовательности 0\0\ можно однозначно заключить, что перед началом эксперимента автомат находился в состоянии 1. Если же на последовательность автомат реагирует последовательностью 0\0г> то начальным было состояние 3. Других возможных выходных реакций в состояниях 1 и 3 на последовательность г'2г'ь кроме перечисленных выше, быть не может. Заметим, что безусловный различающий эксперимент строится по разделяющей последовательности длины 2. Поскольку состояния 1 и 3 автомата 5 не различимы одним входным символом, условный различающий эксперимент для данного автомата имеет такую же сложность.

Точная оценка сложности различающего безусловного эксперимента представлена в работах [23, 24]. В перечисленных работах показано, что для двух инициальных автоматов существует простой безусловный эксперимент, если и только если для этих автоматов существует разделяющая последовательность. В общем случае длина такой последовательности для двух

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Кушик, Наталья Геннадьевна

4.3 Выводы по главе 4

По данной главе можно сделать следующие краткие выводы.

1. В главе обсуждается ряд приложений задач синтеза экспериментов для недетерминированных автоматов; в частности, рассматривается задача синтеза проверяющих экспериментов для технических систем и задача синтеза экспериментов для компоненты автоматной сети. Показывается, что такие задачи решаются достаточно эффективно с использованием теории конечных автоматов.

2. Задачи синтеза «умозрительных» экспериментов для недетерминированных автоматов являются актуальными и имеют реальные технические приложения, что, в частности, подтверждается использованием методов синтеза тестов для анализа дискретных систем, которые основываются на различающих, установочных и синхронизирующих экспериментах.

3. В ряде случаев недетерминизм в технических системах не усложняет анализ таких систем, несмотря на тот факт, что в общем случае практически все

125 оценки сложности для задач анализа таких систем на основе автоматных моделей являются экспоненциальными (см. главы 2, 3). Тем не менее, недетерминизм может быть эффективно использован в ряде областей, например, в задачах перепроектирования систем. Последнее подтверждается экспериментальными результатами по синтезу экспериментов, представляющих оптимальные реализации компонент логических схем.

Заключение

Диссертация посвящена исследованию и разработке методов синтеза безусловных и условных различающих и установочных экспериментов для (неинициальных) недетерминированных автоматов. В первой главе диссертации приводится обзор известных методов синтеза экспериментов для конечных автоматов и отмечается, что такие эксперименты хорошо развиты только для детерминированных автоматов.

В работе получены следующие основные результаты.

1. Предложен метод синтеза безусловного различающего эксперимента для недетерминированного автомата с разделимым множеством начальных состояний. Показано, что для недетерминированного автомата существует безусловный различающий эксперимент, если и только если множество начальных состояний автомата является разделимым. Установлена экспоненциальная оценка сложности такого эксперимента, и показана достижимость этой оценки.

2. Предложен метод синтеза условного различающего эксперимента для недетерминированного автомата. Эксперимент в данном случае эффективно представляется специальным частичным ациклическим автоматом, называемым различающим тестовым примером. Показано, что для недетерминированного автомата существует условный различающий эксперимент, если и только если для этого автомата существует различающий тестовый пример. Установлена оценка сложности такого эксперимента.

3. Предложен метод синтеза безусловного установочного эксперимента для недетерминированного автомата. Показано, что для недетерминированного автомата существует безусловный установочный эксперимент, если и только если для этого автомата существует установочная последовательность. Установлена экспоненциальная оценка сложности такого эксперимента. Исследован класс автоматов с п состояниями {п — 1) входными символами, для которых кратчайшая установочная последовательность имеет длину 2""1 - 1.

4. Предложен метод синтеза условного установочного эксперимента для недетерминированного автомата, представляемого установочным тестовым примером. Показано, что для недетерминированного автомата существует условный установочный эксперимент, если и только если для этого автомата существует установочный тестовый пример. Установлена оценка сложности такого эксперимента.

5. В качестве примера практического использования результатов работы рассматриваются задачи анализа и синтеза сложных систем с использованием недетерминированных автоматов. В частности, рассматривается задача синтеза проверяющих экспериментов для технических систем и задача синтеза экспериментов для компоненты автоматной сети, в том числе с целью выбора оптимальной реализации компоненты. Эффективность использования недетерминированных автоматов в таких задачах подтверждается компьютерными экспериментами с реализациями телекоммуникационных протоколов и современными логическими схемами.

В заключение мы отмечаем ряд возможных направлений продолжения исследований в области «умозрительных» экспериментов для недетерминированных автоматов. В частности, в общем случае не доказана достижимость экспоненциальной оценки сложности условного различающего и установочного экспериментов; не исследованы методы синтеза «умозрительных» различающих и установочных экспериментов для ненаблюдаемых и частичных автоматов. Методы анализа и синтеза проверяющих и распознающих экспериментов для недетерминированных автоматов остались за пределами данной работы. Перечисленные задачи открывают перспективы для дальнейших научных исследований.

Список литературы диссертационного исследования кандидат физико-математических наук Кушик, Наталья Геннадьевна, 2013 год

Список литературы

1. Moore Е. F. Gedanken-experiments on sequential machines / E. F. Moore // In Automata Studies (Annals of Mathematical Studies no.l), Princeton University Press, 1956. P. 129-153.

2. Гилл А. Введение в теорию конечных автоматов / А. Гилл. - М. : Наука, 1966. - 272 с.

3. Kohavi Z. Switching and Finite Automata Theory / Z. Kohavi. - McGraw-Hill, New York, 1978.

4. Агибалов Г. П. Лекции по теории конечных автоматов. / Г. П. Агибалов, А. М. Оранов. - Томск : Издательство ТГУ, 1984. - 185 с.

5. Nondeterministic state machines in protocol conformance testing / A. Petrenko [et al.] // Proc. of the IFIP 6th International Workshop on Protocol Test Systems. - 1993. P. 363-378.

6. El-Fakih K. Fault Diagnosis in Extended Finite State Machines / K. El-Fakih, S. Prokopenko, N. Yevtushenko, G. Bochmann // Proc. of the TestCom 2003. - 2003. -P 197-210.

7. Hennie F. C. Fault-Detecting Experiments for Sequential Circuits // Proc. Fifth Ann. Symp. Switching Circuit Theory and Logical Design. - 1964 . - P. 95-110.

8. Chow T. S. Testing software Design Modelled by Finite State Machines // IEEE Trans. Software Eng. - 1978. - Vol. 4. - № 3. - P. 178-187.

9. Бурдонов И. Б. Тестирование и верификация систем на основе формальных моделей [Электронный ресурс] / И.Б. Бурдонов, А.С. Косачев // Лекции из электронной коллекции. URL: http://video.yandex.ru/users/uralcsclub/view/62/?cauthor=uralcsclub&cid= 12# (дата обращения: 11.12.2012).

10. FSM-based conformance testing methods: A survey annotated with experimental evaluation / R. Dorofeeva [et al.]// Information & Software Technology. - 2010. -Volume 52.-Issue 12.-P. 1286-1297.

11. Simao A. On reducing test length for FSMs with extra states / A. Simao, A. Petrenko, N. Yevtushenko // Softw. Test., Verif. Reliab. - 2012. - Volume 22. -Issue 6.-P. 435-454.

12. Milner. R. Communication and Concurrency / R. Milner. - Prentice-Hall, 1989.

13. Hibbard T. N. Lest upper bounds on minimal terminal state experiments of two classes of sequential machines // Journal of the ACM. - 1961. - Volume 8. - Issue 4. -P. 601-612.

14. Cern'y J. Pozn'amka к homog'ennym eksperimentom s konecn'ymiavtomatami // Mat.-Fyz. Cas. Slovensk. Akad. Vied. - 1964 - № 14. - P. 208-216 (in Slovak).

15. Клячко А. А. Об одной экстремальной комбинаторной задаче, связанной с оценкой длины возвратного слова в автомате / А. А. Клячко, И. К. Рысцов, М. А. Спивак // Кибернетика. - 1987. - № 2. - С. 16-21.

16. Sandberg S. Homing and Synchronization Sequences // Lecture Notes in Computer Science. - 2005. - № 3472. - P. 5-33.

17. Мартюгин П. В. Оценки длины и вычислительной сложности синхронизации конечных автоматов : дис. ... канд. физ.-мат. наук / П. В. Мартюгин. - Екатеринбург, 2008. - 123 с.

18. Ananichev D. S. Synchronizing generalized monotonic automata / D. S. Ananichev, M. V. Volkov // Theoretical Computer Science. - 2005. - Volume 330. -Issue l.-P. 3-13.

19. Ananichev D. S. Collapsing Words vs. Synchronizing Words / D. S. Ananichev, M. V. Volkov // Developments in Language Theory. - 2001. - P. 166-174.

20. Ito M. Some Results on Directable Automata / M. Ito, K. Shikishima-Tsuji // Theory Is Forever. - 2004. - P. 125-133.

21. Василевский M. П. О распознавании неисправности автоматов // Кибернетика. - 1973. - № 4. - С. 98-108.

22. Alur R. Distinguishing tests for nondeterministic and probabilistic machines / R. Alur, C. Courcoubetis, M. Yannakakis // Proceedings of the twenty-seventh annual ACM symposium on Theory of computing. - 1995. - P. 363-372.

23. Спицына Н. В. Синтез тестов для проверки взаимодействия дискретных управляющих систем методами теории автоматов : дис. ... канд. тех. наук / Н.В. Спицына. - Томск, 2005. - 156 с.

24. Spitsyna N. Studying the separability relation between finite state machines / N. Spitsyna, K. El-Fakih, N. Yevtushenko // Softw. Test., Verif. Reliab. - 2007. -Volume 17. - Issue 4. - P. 227-241.

25. Громов M. JI. Разработка методов синтеза условных тестов для автоматных моделей с недетерминированным поведением : дис. ... канд. физ.-мат. наук / М. Л. Громов. - Томск, 2009. - 154 с.

26. Petrenko A. Conformance Tests as Checking Experiments for Partial Nondeterministic FSM / A. Petrenko, N. Yevtushenko // Lecture Notes in Computer Science. - 2005. - № 3997. - P. 118-133.

27. Громов M.JI. Различающие эксперименты с неинициальными недетерминированными автоматами / M.JI. Громов, Н.Г. Кушик, Н.В. Евтушенко // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. - 2011. - № 4. - С. 93-101.

28. Kushik N. Preset and Adaptive Homing Experiments for Nondeterministic Finite State Machines / N. Kushik, K. El-Fakih, N. Yevtushenko // Lecture Notes in Computer Science. - 2011. - № 6807. - P. 215-224.

29. Кушик Н.Г. К синтезу условных установочных экспериментов для недетерминированных автоматов / Н.Г. Кушик, Н.В. Евтушенко // Новые информационные технологии в исследовании сложных структур : девятая российская конференция с международным участием : тезисы докладов. -Томск, 2012.-С. 63.

30. Кушик Н.Г. Синтез условных синхронизирующих экспериментов для недетерминированных автоматов / Н.Г. Кушик, Н.В. Евтушенко // Известия высших учебных заведений. Физика. - 2012. - Т. 55, № 9/2. - С. 315-316.

31. Kushik N.G. Homing sequences for nondeterministic finite state machines / N.G. Kushik // Известия высших учебных заведений. Физика. - 2012. - Т. 55, № 8/3. -С. 242-243.

32. Жигулин М.В. Тестирование программной реализации протокола IRC на основе модели расширенного автомата / М.В. Жигулин, А.В. Коломеец, Н.Г. Кушик, А.В. Шабалдин // Известия Томского политехнического университета. -2011. - Т. 318, № 5. - С. 81-84.

33. Nikitin A. On EFSM based test generation strategies / A. Nikitin, N. Kushik // Proceedings of the 4th Spring/Summer Young Researchers' Colloquium on Software Engineering / The Institute for System Programming of the Russian Academy of Sciences. - Nizhniy Novgorod, 2010. - P. 116-119.

34. Kushik N. Minimizing path length in digital circuits based on equation solving / N. Kushik, G. Sapunkov, S. Prokopenko, N. Yevtushenko // Proceedings of IEEE East-West Design & Test Symposium / Kharkov National University of Radioelectronics. - Kharkov, 2008. - P. 365-370.

35. Кушик Н.Г. Оптимизация комбинационных схем на основе решения уравнений / Н.Г. Кушик, М.В. Рекун // Журнал Сибирского федерального университета «Математика и физика». - 2008. - Т. 1, № 3. - С. 290-295.

36. Eliseeva N. Symmetrization in Digital Circuit Optimization / N. Eliseeva, J.-H. R. Jiang, N. Kushik, N. Yevtushenko // Proceedings of IEEE East-West Design & Test Symposium / Kharkov National University of Radioelectronics. - Kharkov, 2009. - P. 103-106.

37. Gromov M. Software package for optimizing digital circuits / M. Gromov, N. Kushik // Proceedings of the Third Spring Young Researchers' Colloquium on Software Engineering / The Institute for System Programming of the Russian Academy of Sciences. - M., 2009. - P. 68-70.

38. Lin H.-P. Using Boolean relation determinization in digital circuit optimization / H.-P. Lin, W.-L. Hung, M. Gromov, N. Kushik // Новые информационные технологии в исследовании сложных структур : восьмая российская конференция с международным участием : тезисы докладов. - Томск, 2010. - С. 71.

39. Кушик Н.Г. Локальная оптимизация логических схем с использованием характеристических функций / Н.Г. Кушик, Н.В. Евтушенко // Автоматизация

132

проектирования дискретных систем» (CAD DD'10) : Седьмая Международная конференция : труды. - Минск, 2010. - С. 163-170.

40. Евтушенко Н. В. Недетерминированные автоматы: анализ и синтез Ч. 1: Отношения и операции : учеб. пособие / Н. В. Евтушенко, А. Ф. Петренко, М. В. Ветрова. - Томск : Том. гос. ун-т, 2006. - 142 с.

41. Starke P. Abstract Automata / P. Starke. - American Elsevier, 1972. - 419 p.

42. Хопкрофт Д. Введение в теорию автоматов, языков и вычислений / Д. Хопкрофт, Р. Мотвани, Д. Ульман. - М.: Вильяме, 2002. - 528 с.

43. Трахтенброт Б. А. Конечные автоматы (поведение и синтез) / Б. А. Трахтенброт, Я. М. Барздинь. - М. : Наука, 1970. - 400 с.

44. Shabaldina N. On deriving test suites for nondeterministic finite state machines with time-outs / N. Shabaldina, R. Galimullin // Programming and Computer Software. - 2012. - Volume 38. - Issue 3. - P. 127-133.

45. Cavalli A. R. Testing Methods for SDL Systems / A. R. Cavalli, B.-M. Chin, K. Chon // Computer Networks and ISDN Systems. - 1996. - Volume 28. - Issue 12. -P. 1669-1683.

46. Maag S. Testing methodology for an ad hoc routing protocol / S. Maag, F. Zai'di // Proceedings of the ACM international workshop on Performance monitoring, measurement, and evaluation of heterogeneous wireless and wired networks. - 2006. -P. 48-55.

47. Wotawa F. Bridging the Gap Between Slicing and Model-based Diagnosis // Proceedings of SEKE. -2008. - P. 836-841.

48. Богомолов A. M. Эксперименты с автоматами / A. M. Богомолов, А. С. Барашко, И. С. Грунский. - Киев : Наукова думка. - 1973. - 144с.

49. Tretmans J. Model-Based Testing with Labelled Transition Systems: There is Nothing More Practical than a Good Theory [Электронный ресурс] / J. Tretmans // Slides from the lecture on TAROT Summer School, 2010. URL: http://logic.pdmi.ras.ru/csclub/?q=courses/modelbasedtesting (дата обращения: 19.12.2012).

50. Грунский И. С. Анализ поведения конечных автоматов. / И.С. Грунский. -Луганск : Изд-во Луганск, гос. пед. ун-та, 2003. - 318 с.

51. El-Fakih К. Diagnosing Multiple Faults in Communicating Finite State Machines / K. El-Fakih, N. Yevtushenko, G. Bochmann // Proceedings of FORTE. - 2001. - P. 85-100.

52. Luo G. Test Selection Based on Communicating Nondeterministic Finite-State Machines Using a Generalized WP-Method / G. Luo, G. Bochmann, A. Petrenko // IEEE Trans. Software Eng. - 1994. - Volume 20. - Issue 2. - P. 149-162.

53. Petrenko A. Generating Checking Sequences for Nondeterministic Finite State Machines / A. Petrenko, A. Simao, N. Yevtushenko // Proceedings of ICST. - 2012. -P. 310-319.

54. Ravikumar B. Parallel algorithms for finite automata problems // Lecture Notes in Computer Science. - 1998. - № 1388. - P. 373.

55. Petrenko A. Testing deterministic implementations from nondeterministic FSM specifications / A. Petrenko, N. Yevtushenko, G. Bochmann // Proceedings of 9th International Workshop on Testing of Communicating Systems. - 1996. - P. 125-141.

56. Imreh B. On Commutative Directable Nondeterministic Automata / B. Imreh, M. Ito, M. Steinby // Proceedings of Grammars and Automata for String Processing. -2003.-P. 141-150.

57. Дорофеева M. Ю. Исследование и разработка конечно-автоматных методов синтеза проверяющих тестов для управляющих систем : дис. ... канд. тех. наук / М. Ю. Дорофеева. - Томск, 2007. - 150 с.

58. Hierons R. М. Adaptive Testing of a Deterministic Implementation Against a Nondeterministic Finite State Machine // The Computer Journal. - 1998. - Volume 41.-Issue 5.-P. 349-355.

59. Коломеец А. В. Алгоритмы синтеза проверяющих тестов для управляющих систем на основе расширенных автоматов : дис. ... канд. тех. наук / А. В. Коломеец. - Томск, 2010.- 130 с.

60. Jia Y. An Analysis and Survey of the Development of Mutation Testing / Y. Jia, M. Harman // IEEE Trans. Software Eng. - 2011. - Volume 37. - Issue 5. - P. 649678.

61. Кнут Д. Искусство программирования / Д. Кнут. - 3-е изд. - Т. 2 - М. : Вильяме, 2000. - 832 с.

62. Громов М. Синтез условных различающих экспериментов для автоматов с недетерминированным поведением / М. Громов, Н. Евтушенко // Прикладная дискретная математика. - 2009. - № 4 (6). - С. 90-101.

63. Громов М. К синтезу условных тестов для недетерминированных автоматов / М. Громов, Н. Евтушенко, А. Коломеец // Программирование. - 2008. - №6. -С. 1-11.

64. Hwang I. Tight bound on the length of distinguishing sequences for non-observable nondeterministic Finite-State Machines with a polynomial number of inputs and outputs / I. Hwang, N. Yevtushenko, A. R. Cavalli // Inf. Process. Lett. -2012. - Volume 112. - Issue 7. - P. 298-301.

65. Petrenko A. Adaptive Testing of Deterministic Implementations Specified by Nondeterministic FSMs / A. Petrenko, N. Yevtushenko // Proceedings of ICTSS. -2011 .-P. 162-178.

66. Kalt C. RFC2812 - Internet Relay Chat: Client Protocol [Электронный ресурс] / С. Kalt // 2000. URL: http://www.faqs.org/rfcs/rfc2812.html (дата обращения: 10.09.2012).

67. Shabaldin A. Constructing a Tester for Checking Student Protocol Implementations / A. Shabaldin // Proceedings of Spring Young Researchers' Colloquium on Software Engineering / The Institute for System Programming of the Russian Academy of Sciences. - M., 2007. - P. 23-29.

68. Кудрявцев В. Б. Восстановление автоматов по фрагментам поведения / В. Б. Кудрявцев, И. С. Грунский, В. А. Козловский // Дискрет, матем. - 2009. - № 2 (21).-С. 3^2.

69. The Unknown Component Problem: Theory and Applications / T. Villa [et al.] . -Springer, 2012.-326 p.

70. Тихомирова С. В. Оптимизация многокомпонентных дискретных систем на основе решения автоматных уравнений : дис. ... канд. тех. наук / С. В. Тихомирова. - Томск, 2008. - 152 с.

71. Lee R.-R. Bi-decomposing large Boolean functions via interpolation and satisfiability solving / R.-R. Lee, J.-H. R. Jiang, W.-L. Hung // Proceedings of DAC. -2008.-P. 636-641.

72. Страуструп Б. Язык программирования Си ++ / Б. Страуструп. - Пер. с англ. М. Г. Пиголкина, В. Я. Яницкого. - М. : Радио и связь, 1991. - 349 с.

73. Somenzi F. CUDD: CU Decision Diagram Package [Электронный ресурс] / F. Somenzi // URL: http://vlsi.colorado.edu/~fabio/CUDD/ (дата обращения: 20.12.2012).

74. ISCAS89. Sequential Benchmark Circuits [Электронный ресурс] // Education: Virginia Tech: The Bradley Department of Electrical & Computer Engineering. College of Engineering. URL: http://www.ece.vt.edu/mhsiao/iscas89.html (дата обращения: 20.12.2012).

75. ABC. A System for Sequential Synthesis and Verification [Электронный ресурс] / Berkeley Logic Synthesis and Verification Group // URL: http://www.eecs.berkeley.edu/~alanmi/abc/ (дата обращения: 20.12.2012).

76. Шнайер Б. Прикладная криптография: протоколы, алгоритмы, исходные тексты на языке Си / Б. Шнайер. - М. : Триумф, 2002. - 815 с.

к