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

Па правах рукописи

Кушик Наталья Геннадьевна

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

05.13.01 - Системный анализ, управление и обработка информации (в отраслях информатики, вычислительной техники и автоматизации)

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

2 8 МАР 2013

Томск 2013

005050959

005050959

Работа выполнена в федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Национальный исследовательский Томский государственный университет», на кафедре информационных технологий в исследовании дискретных структур.

Научный руководитель: доктор технических наук, профессор,

Евтушенко Нина Владимировна

Официальные оппоненты:

Бурдонов Игорь Борисович, доктор физико-математических наук, старший научный сотрудник, федеральное государственное бюджетное учреждение науки Институт системного программирования Российской академии наук, отдел «Технологии программирования», ведущий научный сотрудник

Колесникова Светлана Ивановна, кандидат физико-математических наук, доктор технических наук, федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Национальный исследовательский Томский государственный университет», кафедра высшей математики и математического моделирования, профессор

Ведущая организация: Федеральное государственное автономное обра-

зовательное учреждение высшего профессионального образования «Уральский федеральный университет имени первого Президента России Б.Н. Ельцина» (г. Екатеринбург)

Защита состоится 10 апреля 2013 г. в 10:30 на заседании диссертационного совета Д 212.267.12, созданного на базе федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Национальный исследовательский Томский государственный университет», по адресу: 634050, г. Томск, пр. Ленина, 36 (учебный корпус № 2, аудитория 212Б).

С диссертацией можно ознакомиться в Научной библиотеке Томского государственного университета.

Автореферат разослан 01 марта 2013 г.

Ученый секретарь Тарасенко

диссертационного совета Петр Феликсович

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

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

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

Реализация и внедрение результатов работы.

Список НИР, в рамках которых проводились исследования, включает 6 проектов, наименования трех из которых приведены ниже.

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

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

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

Соответственно, диссертационная работа выполнена при частичной финансовой поддержке выше описанных проектов и грантов.

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

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

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

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

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

4

граммирования» ИСП РАН, Москва, 2012 г., коллоквиумах молодых ученых «Spring/Summer Young Researchers' Colloquium on Software Engineering», Москва, 2009 г. и Нижний Новгород, 2010 г.; международной конференции по конечным автоматам и их приложениям CIAA'2011, Блуа, Франция, 2011 г.

Публикации. По результатам проведенных исследований опубликовано 13 статей в научных журналах, докладах и материалах конференций различного уровня, в том числе три ([1-3]) в рецензируемых журналах из Перечня ВАК.

Личный вклад диссертанта. Постановка изложенных в диссертации задач была сделана совместно с научным руководителем. Совместно с руководителем проведены теоретические исследования по синтезу безусловных и условных различающих (обзор известных результатов частично выполнен M.JL Громовым) и установочных (обзор известных результатов частично выполнен профессором К. Эль-Факи) экспериментов для полностью определенных наблюдаемых недетерминированных автоматов. Соискателем самостоятельно сформулированы и доказаны необходимые и достаточные условия существования безусловных и условных различающих и установочных экспериментов, и предложены методы их синтеза; получены оценки сложности установочных и различающих экспериментов. Для проведения компьютерных экспериментов, результаты которых представлены в главе 4, соискателем (совместно с M.J1. Громовым) разработано программное обеспечение по оптимизации логических схем на основе решения автоматных уравнений. Исследования по полноте синтезированных проверяющих тестов для проверки реализаций протокола IRC были проведены совместно с М.В. Жигулиным, A.B. Шабалдиным и A.B. Коломейцем.

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

Под конечным автоматом (автоматом) понимается пятерка 5 = (S, /, О, hs, S'), где S — конечное непустое множество состояний с выделенным непустым множеством начальных состояний S', / и О — конечные непустые входной и выходной алфавиты, такие, что /пО = 0, и hs ci'x/x OxS - отношение или множество переходов. Автомат называется инициальным, если |5" | = 1, в противном случае автомат называется неинициальным. Четверка (s, i, о, s') е hs называется переходом в автомате из состояния s в состояние и состояние s'

называется i/о-преемником состояния s е. S. Говорят, что поведение автомата S определено в состоянии s для входного символа /', если существует пара (о, s') g Ох S такая, что (5, /', о, s') б hs. Если в автомате 5 для любой пары (.ç, i) е Sx / существует пара (о, s') е О у. S такая, что (s, i, о, s') е hs, то автомат называется полностью определенным, в противном случае автомат называется частичным. Автомат S называется детерминированным, если для любой пары (j, /) е S х / существует не более одной пары (о, s') е О х S такой, что (i, /', о, î') s /î.v, иначе автомат называется недетерминированным. Если в недетерминированном автомате 5 для любой тройки (s, i, о) е S х / х О существует не более одного состояния s' е S такого, что (s, /', о, s') е hs, то автомат называется наблюдаемым, в противном случае автомат называется ненаблюдаемым.

Параллельно с отношением переходов часто используют две функции: функцию переходов next states и функцию выходов outs, которые распространяются на последовательности (слова) в алфавитах / и О. Множество nextstateds, et) включает те и только те состояния, которые достижимы в автомате S из состояния s по входной последовательности а. Множество outs(s, а) включает все возможные выходные реакции автомата 5 в состоянии s на входную последовательность а. Пара а/р для входной последовательности а и (3 е out sis, а) называется входо-выходной последовательностью автомата 5 в состоянии s. Объединение множеств всех входо-выходных последовательностей в начальных состояниях автомата образует язык автомата.

Состояния î] и s2 полностью определенного автомата S- (S, I, О, hs, S') называются эквивалентными, если V а е Г (outs(su а) = out^s2, а)), и автомат 5 называется приведенным, если все его состояния являются попарно не эквивалентными. Аналогичным образом определяется эквивалентность состояний двух различных полностью определенных автоматов. Понятие автомата очень близко к понятию полуавтомата, в котором действия не делятся на входные и выходные, и поэтому конечные автоматы иногда называются «автоматами с выходом», а полуавтоматы - «автоматами без выхода».

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

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

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

Различающие эксперименты с детерминированными автоматами хорошо изучены, особенно в случае, когда автомат, предъявленный к эксперименту, является полностью определенным и приведенным. Входная последовательность а называется различающей последовательностью для состояний Л[ и s2 автомата S = (S, I, О, hs, S'), если outsÇsi, а) * oiits(s2, а). Входная последовательность, различающая любую пару состояний в детерминированном автомате, называется диагностической последовательностью. Простой безусловный различающий эксперимент существует для детерминированного автомата, в котором S = S, если и только если автомат обладает диагностической последовательностью. Диагностическая последовательность существует не для всякого приведенного детерминированного автомата; необходимые и достаточные условия существования диагностической последовательности формулируются на основе анализа дерева преемников автомата, усеченного по специальным правилам и называемого диагностическим деревом. Отметим, что для любого (полностью определенного) приведенного автомата, в котором S = S", существует кратный различающий эксперимент, причем для автомата с п состояниями длина каждой входной последовательности не превышает (п - 1), и число последовательностей не превышает С„2. Условные различающие эксперименты практически не исследовались для детерминированных автоматов, в силу полиномиальной оценки сложности кратных безусловных различающих экспериментов. Для недетерминированного автомата при различимости состояний необходимо предположение о всех погодных условиях (ail weather conditions), которое «предполагает» возможность пронаблюдать все выходные реакции автомата на входную последовательность.

Показано, что для всякого детерминированного сильно связного приведенного автомата с п состояниями существует простой установочный эксперимент. В этом случае используется одна входная последовательность, которая довольно часто называется установочной (homing) последовательностью. Последовательность а е I называется установочной для детерминированного автомата 5= (S, I, О, Ts, S*), если

next_state(su а) * next_state{si, а) => out(S], а) ф ou/(s2,a).

Синтез установочной последовательности проводится на основе специального усеченного установочного дерева преемников. Для детерминированного связного приведенного автомата с п состояниями длина кратчайшей установочной последовательности не превосходит величины п{п - 1)/2, и эта оценка является достижимой. Т. Хиббард показал, что сложность установочного эксперимента в общем случае нельзя понизить при переходе к условному эксперименту. В ряде литературных источников рассматривается возможность использования параллельных и вероятностных алгоритмов синтеза установочных экспериментов для детерминированных автоматов, с использованием которых установочная последовательность может быть найдена быстрее.

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

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

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

как правило, рассматривают отношения разделимости и /--различимости. Заметим, однако, что в известных работах (Н.В. Евтушенко, К. Эль-факи, Н.В. Ша-балдина, А. Петренко, М.Л. Громов и др.) речь идет о различимости двух инициальных автоматов. Говорят, что состояния ^ и ^ полностью определенного автомата 5= (5,1, О, У) разделимы, если существует входная последовательность а такая, что ош&Оь а) п 2, а) = 0- Состояния автомата .у, и 52 г-различимы, если любое состояние любого полностью определенного автомата не может быть редукцией одновременно состояний 5) и л- Во втором случае для этих состояний существует так называемый различающий автомат, который вводится в работах А. Петренко и Н.В. Евтушенко. Разделяющая последовательность используется для синтеза безусловного различающего эксперимента, в то время как различающий автомат представляет условный различающий эксперимент. Длина разделяющей последовательности для двух инициальных автоматов с т и п состояниями ограничивается величиной 2тп'х, и эта оценка является точной, однако достижимость этой оценки показана только для автоматов с входным алфавитом мощности 2тп~Сложность условного эксперимента, оцениваемая длиной самой длинной входо-выходной последовательности в различающем автомате, равна величине тп, и соответственно, переход от безусловного эксперимента к условному для двух инициальных автоматов позволяет существенно понизить сложность эксперимента.

Автору не известны какие-либо результаты по синтезу установочных экспериментов для недетерминированных автоматов. Синтез синхронизирующих экспериментов рассматривается только для полуавтоматов. Оценка длины синхронизирующей последовательности для недетерминированного полуавтомата является экспоненциальной, а именно, длина минимальной синхронизирующей последовательности для недетерминированного полуавтомата с п состояниями оценивается величиной порядка 2". По-прежнему для исследователей представляют интерес точные оценки для специальных классов полуавтоматов, которые могут быть полиномиальными, и ряд таких оценок получен в работах Б. Имреша, М. Стенби. Методы синтеза проверяющих экспериментов для недетерминированных автоматов, в основном, используют идею М.П. Василевского, и доставляют кратный проверяющий эксперимент. Исключением является работа А. Петренко, А. Симао, Н.В. Евтушенко, в которой авторы предлагают метод синтеза проверяющей последовательности для недетерминированного автомата.

Таким образом, задачи, поставленные в диссертации, являются актуальными, и во второй главе предлагаются методы синтеза безусловного и условного различающих экспериментов для полностью определенных наблюдаемых недетерминированных автоматов, и устанавливаются необходимые и достаточные условия существования таких экспериментов. Подмножество состояний Мс,? автомата 5= {Б, 1, О, Л5, 5*) будем называть разделимьш, если существует входная последовательность а, которая является разделяющей последовательностью для любых двух различных состояний .у, и х2 множества А/, и такая последовательность а называется разделяющей последовательностью для множества М. Если М = У, то разделяющую последовательность для М (если таковая существует) можно считать диагностической (различающей) последовательностью автомата

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

Алгоритм синтеза безусловного различающего эксперимента для неинициального недетерминированного автомата обобщает алгоритм синтеза разделяющей последовательности для двух инициальных автоматов, изложенный в работе Н.В. Шабалдиной, К. Эль-Факи, Н.В. Евтушенко, и использует дерево преемников, вершины которого помечены множествами пар состояний автомата. Под парами состояний наблюдаемого автомата 5 мы понимаем неупорядоченные наборы состояний этого автомата длины 2, которые обозначаются как

sp,sq,sp,sq е S. Если sp = sq, то речь идет о синглетоне вида sp,s . Если Но - входо-выходная пара, то //»-преемником пары состояний sp,sq называется пара Ио-

преемников состояний s,, и sq (если такие преемники существуют для обоих состояний sp и s4). Если //с-преемником состояний sp и sq является одно и то же состояние sk, то //о-преемником пары состояний sp,s является синглетон sk,sk . Если / — входной символ, то множество /-преемников пары состояний sp,s есть множество //о-преемников этой пары по всем выходным символам о е О. Если для любого выходного символа о е О пара состояний sp,sg не имеет //о-преемника, то множество /-преемников этой пары пусто.

Алгоритм 2.1 Построение разделяющей последовательности для недетерминированного автомата

Вход: Полностью определенный наблюдаемый недетерминированный автомат 5 = (S, I, О, hs, S')

Выход: Входная последовательность, разделяющая состояния множества S', если S' - разделимое подмножество, или ответ «Не существует простого безусловного различающего эксперимента для автомата 5»

Шаг 1. Строим усеченное дерево преемников для автомата S. Вершина дерева, которая находится на нулевом уровне (корень дерева), помечается множеством, которое состоит из всех пар различных начальных состояний, т.е. пар вида

sp,sq,sp,sq е S',sp Ф sq ; вершины дерева помечаются множествами пар множества S или пустым множеством. Пусть уже построены j уровней дерева, j > 0. Из нетерминальной вершины у'-го уровня, помеченной множеством Р пар состояний, есть ребро, помеченное входным символом г, в вершину, которая помечена множеством пар Q: пара sp,s(eg, если sp,xq является /-преемником некоторой

пары множества Р. Если входной символ / разделяет каждую пару состояний множества Р, то из вершины, помеченной множеством Р, есть ребро, помеченное входным символом /, в вершину, помеченную пустым множеством. Вершина Current на к-м уровне, к > 0, помеченная множеством Р пар состояний, является листом дерева, если для нее выполняется одно из следующих условий. Правило 1: Множество Р пусто.

Правило 2: На j-u уровне, j < к, существует вершина, помеченная множеством RçP.

Правило 3: Множество Р содержит синглетон.

Шаг 2. Если все пути на шаге 1 заканчиваются с использованием правил 2 и 3, то множество У не является разделимым множеством, т.е. его состояния не различимы простым безусловным экспериментом. Соответственно, на ВЫХОДе выдается ответ «Не существует простого безусловного различающего эксперимента для автомата 5». Если некоторый путь на шаге 2 заканчивается применением правила 1, то на ВЫХОДе выдается последовательность а, где а помечает искомый путь и разделяет состояния множества 5'.

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

1. Пусть последовательность а помечает путь в усеченном дереве преемников в вершину с множеством пар состояний Р Ф 0. Пара е Р (синглетон

хр,.ур е Р), если и только если существуют состояния ль ^ е 5', 5] ф з2, и выходная последовательность р такие что яр и суть а/р-преемники состояний з, и л2

есть а/р-преемник состоянийи .52).

2. Если автомат 5 обладает разделяющей последовательностью, то каждая кратчайшая разделяющая последовательность помечает некоторый путь в усеченном дереве преемников, построенном по алгоритму 2.1.

3. Последовательность а, помечающая путь в дереве преемников, является разделяющей для множества 5" начальных состояний автомата 5, если и только если путь, помеченный последовательностью а, заканчивается вершиной с пустым множеством.

4. Последовательность а, помечающая путь в вершину, усеченную по правилу 3, не является префиксом последовательности, разделяющей состояния множества 5'.

5. Пусть а - последовательность, разделяющая состояния множества 5' и проходящая через вершину, помеченную множеством Р на к-м ярусе, и в усеченном дереве преемников имеется вершина, помеченная множеством Я на >м ярусе, причем Я с Р и } < к. Тогда существует последовательность, разделяющая состояния множества 5", длина которой меньше [а|.

Теорема 2.1. Для автомата 5 существует разделяющая последовательность, если и только если усеченное дерево преемников, построенное по алгоритму 2.1, содержит вершину, помеченную пустым множеством. Если все ветви в дереве преемников в алгоритме 2.1 усечены с применением правил 2 и 3, то не существует последовательности, разделяющей состояния множества Б'.

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

Теорема 2.2. Длина кратчайшей разделяющей последовательности для наблюдаемого полностью определенного автомата 5= (5, /, О, И, У). = п, |5"] = т,

т > 2, не превосходит величины 2е" -2С"~С™ .

Достижимость экспоненциальной сложности длины разделяющей последовательности для двух инициальных автоматов доказывается в работе Н.В. Шабал-диной, К. Эль-Факи, Н.В. Евтушенко. В диссертации показывается достижимость экспоненциальной оценки длины разделяющей последовательности для сильно связных автоматов с произвольным числом начальных состояний.

Если множество начальных состояний недетерминированного автомата не является разделимым, то, тем не менее, в ряде случаев состояния этого множества можно различить посредством условного эксперимента. Условный различающий эксперимент для недетерминированного автомата может быть построен и проведен на основании так называемого различающего тестового примера, который представляется частичным ациклическим недетерминированным автоматом. Тестовый пример есть связный наблюдаемый инициальный автомат Р= (Р, /, О, Ир, р0), граф переходов которого ациклический и в каждом не тупиковым состоянии определены переходы только по одному входному символу со всеми возможными выходными символами, и таким образом, тестовый пример представляет условный эксперимент для любого автомата с входным алфавитом / и выходным алфавитом О. Различающий тестовый пример определяется на основе пересечения неинициальных автоматов, которое обобщает понятие пересечения для инициальных автоматов. Пусть 5= (5,I, О, У) и Р = (Р, I, О, ИР, Р') суть полностью определенные недетерминированные автоматы. Пересечение 5 п Р есть наибольший связный подавтомат автомата О, состояниями которого являются пары (Ь, с), где 6с5иссРс начальным состоянием (У, Р'). Для входо-выходной пары Но существует переход ((Ь, с), /, о , (Ь\ с')), если и только если в каждом из подмножеств Ь и с существует состояние, в котором есть переход по паре Но, и Ъ' и с' суть г'/о-преемники подмножеств Ъ и с. В диссертации устанавливаются ряд свойств автомата-пересечения.

Тестовый пример Р=(Р,1,О,кР,р0) называется различающим для автомата 5= (5,1, О, к%, У), если каждое тупиковое состояние (Ъ, с) пересечения Рсл 5 состоит из одно элементных подмножеств Ь и с и для любого перехода ((6, с), /, о, (Ь', с')) пересечения Р п 5 в подмножестве с не существует двух различных состояний, из которых есть переходы в одно и то же состояние по вход-выходной паре Но, т. е.

\/5Ь «¡ЕС (($], /, О , Л') € Иъ & («2, 7, О , 5') € => .51 = £2)-

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

Лемма 2.3. Тестовый пример Р является различающим тестовым примером для автомата Я, если и только если каждая входо-выходная последовательность, ведущая в тупиковое состояние автомата Р, допустима только в одном начальном состоянии автомата 5.

Теорема 2.4. Для наблюдаемого полностью определенного недетерминированного автомата 5= (5,1, О, Иъ, существует условный различающий эксперимент, если и только если для автомата 5 =(5,/, О, /¡5, существует различающий тестовый пример.

Метод синтеза условного различающего эксперимента основывается на понятии условной различимости. Это понятие вводится в разделе 2.2 главы 2. Подмножество т состояний автомата 5, разделимое одним входным символом, называется \-условно-различимьш множеством. Пусть определены все максимальные в смысле отношения включения (к - 1)-условно-различимые подмножества, к > 1. Будем говорить, что т есть к-условно-различимое множество состояний, к > 1, если т есть (к - 1)-условно-различимое множество или существует входной сим-

вол / е /, такой что для любого о е О множество //о-преемников состояний из т пусто, содержит одно состояние или является {к — 1)-условно-различимым множеством, причем в последних двух случаях любые два различные состояния из т не могут обладать одним и тем же //о-преемником. Множество т называется ус-ловно-различимьш, если т есть ¿-условно-различимое множество для некоторого натурального к.

Мы предлагаем алгоритм синтеза различающего тестового примера для автомата 5= (8,1, О, А, без ограничения общности предполагая, что 5'= {,уь т>2.

Алгоритм 2.2 Построение различающего тестового примера в случае, когда множество начальных состояний является условно-различимым множеством

Вход: Полностью определенный наблюдаемый автомат 5 = (5, /, О, к, 5"), = т, для которого 5" есть А--условно-различимое множество; множество всех 1, 2, ..., ¿-условно-различимых множеств

Выход: Автомат Р, представляющий условный различающий эксперимент для автомата 5

Шаг 1. Определить множество Р состояний автомата Р, в которое включаются состояния Б', р\, р2, ■ -., рт, а также 1, 2, ..., ¿-условно-различимые множества состояний автомата 5. Начальным состоянием автомата Р объявить состояние Б'. Состояние р, совпадает с /-м начальным состоянием автомата 5. Множество переходов автомата Я объявить пустым, т.е. кр = 0.

Шаг 2. Дляу-условно-различимого подмножества Я, у = 2; к

2.1. Определить входной символ / е I, такой, что для любого о е О множество //о-преемников состояний из Я пусто, содержит одно состояние или является (/- 1)-условно-различимым множеством Я', \Я'\ > 1, причем любые два различные состояния из Я не обладают одним и тем же /'/о-преемником.

2.2. Если множество //о-преемников состояний из Я пусто или содержит одно состояние, добавить в множество 1гр переход (/?, /, о, р'),

Иначе добавить в Ир каждый переход (Я, /, о, Я').

Шаг 3. Удалить из Р все состояния, недостижимые из начального состояния, и итеративно удалить все переходы в и из этих состояний.

Для тупикового состояния р' найти множество входо-выходных последовательностей, переводящих автомат Я из начального состояния в состояние р'.

Для каждой входо-выходной последовательности а е найти начальное состояние Sj е Б' автомата 5, в котором реализуется данная входо-выходная последовательность и заменить переход (Я, /, о, р') в автомате Р на переход (Я, ¡, о, р/} для всех подмножеств Я, соответствующих состояниям автомата Р.

Если последовательность а не реализуется ни в одном из начальных состояний автомата 5, то заменить переход (Я, /', о, р') в автомате Р на любой переход (Я, г, о, р,), Xj е 5', и ВЫХОД.

Теорема 2.5. Автомат Р, доставляемый алгоритмом 2.2, является различающим тестовым примером для автомата 5.

В диссертации показывается, что начальные состояния наблюдаемого автомата 5 = (Б. I, О, И& Б') различимы условным экспериментом, если и только если множество Б' является условно-различимым множеством.

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

Утверждение 2.6. Сложность условного различающего эксперимента для наблюдаемого недетерминированного автомата 5= (5,1, О, 5') не превосходит *

величины .

¡=2

При к = п сложность условного различающего эксперимента оказывается не более 2" — п — 1. Требуются дополнительные исследования, чтобы выяснить, является ли такая оценка точной. Тем не менее, в диссертации приводится пример автомата с п = 4 состояниями, для которого кратчайший условный различающий эксперимент имеет высоту 11, что совпадает с величиной 2" — п - 1 при п = 4.

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

Пусть 5 = (5,1, О, 5'), |5'| = т > 2, - полностью определенный недетерминированный автомат. Последовательность а е / называется установочной последовательностью для 5, если для каждого подмножества } с 5' имеет

место следующее свойство:

Ур е ои1( ^ ,а) п ои!( ,а) п ... п оШ{ ^ ,а)

\next_siatei , а/р) = пгх1_Ма1е{ , а/р) = ... = пех1_хШ1е(, а/р)].

Установочная последовательность не всегда существует даже для сильно связного приведенного недетерминированного автомата. Тем не менее, достаточным условием существования установочной последовательности для автомата 5 = (5,1, О, И$, 5") является разделимость множества начальных состояний 5'. Устанавливаются следующие свойства установочных последовательностей.

1. Пусть 5 = (5, /, О, И5, 5"), |5"| = т > 2, наблюдаемый автомат и а е I есть входная последовательность, такая, что для каждой пары с 5' имеет место следующее свойство

УР е ош{ ^ , а) п оШ{ , а) [пех1_зШе( s,¡, а/р) = ^ , ос/р)].

Тогда последовательность а является установочной для 5.

2. Последовательность а, разделяющая каждую пару состояний множества 5', является установочной.

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

3. Пусть автомат 5 = (5,1, О, Иц, {.5Ь £г}) обладает следующим свойством:

V а е /* [ог//(л-], а) п а) ^ 0 => Эр е а) п а) (пех1_$1а1е($ь а/р) пехг_зШе(зг, а/р))].

Если для автомата Б существует установочная последовательность, то эта последовательность является разделяющей для автомата 5.

Алгоритм синтеза безусловного установочного эксперимента аналогичен алгоритму синтеза безусловного различающего эксперимента; он основывается на

построении дерева преемников, но изменяются правила 2 и 3 его усечения, а именно:

Правило 2: На у'-м уровне у, ] < к, существует вершина, помеченная множеством Я, такая, что множество Р содержит все пары из Я, которые не являются синглетонами.

Правило 3: Множество Р состоит из синглетонов.

Теорема 3.1. Для автомата 5 существует установочная последовательность, если и только если усеченное дерево преемников содержит вершину, объявленную листом по правилам 1 или 3. Если все ветви в дереве преемников усечены с применением правила 2, то не существует безусловного установочного эксперимента для автомата 5.

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

О ^ '/„ называется непосредственно выводимым из непустого подмножества Р —

{РъРг, ...,р,} ^ 2„, рх <р2 < ... <р, (обозначение: Р <а О), если выполняется одно из следующих условий.

1) Если Р1 = 0, то 0 = Р \ {0} = {рг,..., р,},

2) Если 0 ¡г Р, то 0= {0,1,...,/?! - 1 ,рг,...,/?,}.

Подмножество Q Я Zn выводимо из подмножества Р ^ 2„ (обозначение: Р < 0, если найдется такая последовательность множеств Р = Я2, ..., Я/ = Q, что каждое множество Яр; = 2, ...,/, непосредственно выводимо из множества Отношение выводимости есть линейный порядок на множестве непустых подмножеств

Рассмотрим недетерминированный автомат $„, п > 1, с множеством состояний 5"={0, 1,2, ..., и - 1}, множеством входных символов/= {/0, ¿,, ...,/„.2} имноже-ством выходных символов О = {(;,/): /,_/ = 0, ..., п — 1 & г <_/'}. Отношение переходов для автомата $„ определим следующим образом. В состоянии 0 под действием входного символа /0 определен единственный переход в состояние (п - 1) с выдачей выходного символа (0, п - 1). Далее в каждом состоянии j, 0 <j < п - I, определены петли по входо-выходной паре У(0, п - 1). Определим теперь переходы по каждому входному символу 0 <к<п- 1, в каждом из состояний автомата Ч„. Из состояния к под действием входного символа гк автомат переходит в состояние ц е {0, 1, ..., к - 1} с выдачей выходного символа (д, Г) для / е {0, 1, 1, А + 1 ..., и - 1} и 1> д, т.е. в автомате определен переход вида (к, ¡к, (д, Г), д) для всех д е {0, 1, ..., к - 1}, 1 е {0, 1, ..., к - 1, к+ 1 ..., п - 1} и 1> ц.

Определим переходы в автомате 5„ по входному символу 0 < к < п - 1, в состоянии р > к. В каждом состоянии р для р > к определены петли по входо-выходной паре /*/(/, р) для всех I < р, а также петли по паре У(р, Г) для р < I < п.

Кроме того, в состоянии р определены переходы в каждое состояние е {0, 1, ..., к - 1} по входо-выходной паре ;У(/, д) для всех / < д.

Для каждого состояния р, где р < к, под действием входного символа ¡к в автомате $„ определены переходы в состояние к с выдачей выходного символа (д, Г) для д, 1*ки0<д<1<п-\.

По построению, автомат п > 3, является полностью определенным сильно связным наблюдаемым автоматом.

Теорема 3.2. Длина кратчайшей установочной последовательности для автомата $„ с п начальными состояниями равна 2""1 - 1.

Доказательство теоремы основано на следующих леммах, в которых через 02

обозначено множество всех пар вида /, _/,/,_/е [/,/< } , и через иехг_^/аГе(и2, гч) обозначено объединение всех /^-преемников пар из множества 02 в автомате 5„.

Лемма 3.3. Пусть ¡7= {к,рир2, ...,р,}, 0<к<рх<р2<... <р„р, = п-\. Тогда множество пар из пех1_$1а1е(02, /*), не являющихся синглетонами, есть множество

]\т2, где N непосредственно выводимо из С/, т.е. и N.

Лемма 3.4. Пусть и = {к, рь р2, ..., р,}, к <р\ <р2 < ... < р„ р, = п - 1, к > 0. Для всех 0 <у" < & множество пех/_5Га/е(и2, (,) гз 02.

Лемма 3.5. Пусть £/ = {к,рър2, ...,р,}, 0 < к <р\ <рг < ... <рьр1= п-1. Для всех п>]> к, пехС_х1а1е(\]2, /}) з 02 или пех(_5Ш1е{ 02, г)) з "К2, где С/ выводимо из

/V, т.е. N < и.

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

Тестовый пример Р— (Р, 1, О, Ьр,р0) называется установочным для автомата 5 = (Б, /, О, Йб, 51), если каждое тупиковое состояние (Ь, с) пересечения Р п 5 состоит из одноэлементных подмножеств Ъ и с. По определению, всякий различающий тестовый пример является установочным.

Теорема 3.6. Для наблюдаемого полностью определенного недетерминированного автомата 5= (5,1, О, /¡б, У) существует условный установочный эксперимент, если и только если для автомата 5= (5,7, О, /н, 3) существует установочный тестовый пример.

Подобно понятию условной различимости в случае условных различающих экспериментов, мы вводим понятие условной установочности для множества состояний автомата. По определению, все одноэлементные подмножества состояний автомата 5 являются 1 -условно-установочными множествами. Пусть определены все (к— 1)-условно-установочные подмножества, к > 1. Будем говорить, что подмножество т есть к-условно-установочное множество состояний, к> 1, если т есть (к — 1)-условно-установочное множество или существует входной символ / б /, такой что для любого о е О множество /'/о-преемников состояний из т пусто, содержит одно состояние или является (А - ^-условно-установочным множеством. Множество т называется условно-установочным, если т есть ¿-условно-установочное множество для некоторого натурального к.

Алгоритм синтеза установочного тестового примера для автомата 5 = (S,1, О, hs, 5") аналогичен алгоритму синтеза различающего тестового примера и возвращает необходимый тестовый пример, если и только если множество S' является ус-

к

ловно-установочным. Сложность такого эксперимента оценивается суммой "У С'„

Ы2

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

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

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

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

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

2. Предложен метод синтеза условного различающего эксперимента для неде-

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

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

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

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

3. Громов МЛ. Различающие эксперименты с неинициальными недетерминированными автоматами / М.Л. Громов, Н.Г. Кушик, Н.В. Евтушенко //

18

Вестник Томского государственного университета. Управление, вычислительная техника и информатика. - 2011.-№ 4. — С. 93-101.

4. 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.

5. EliseevaN. 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.

6. 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.

7. 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.

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

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

10. 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.

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

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

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

/

Подписано в печать 27.02.2013 г. Формат А4/2. Ризография Печ. л. 1,0. Тираж 100 экз. Заказ № 07/02-13 Отпечатано в ООО «Позитив-НБ» 634050 г. Томск, пр. Ленина 34а

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ (ТГУ)

На правах рукописи

Кушик Наталья Геннадьевна

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

Специальность 05.13.01 - Системный анализ, управление и обработка

информации

Диссертация на соискание ученой степени кандидата физико-математических наук

(0

Научный руководитель

00 Д-Р тех- наук, профессор Н. В. Евтушенко

ю „ ю £

со 8

иб

О Р (N1 00

Томск 2013

Оглавление

ВВЕДЕНИЕ..................................................................................................................5

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

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

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

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

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

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

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

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

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

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

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

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

1.3.2 Установочные и синхронизирующие эксперименты с недетерминированными автоматами..................................................................42

1.3.3 Проверяющие эксперименты с недетерминированными автоматами.. 43

1.4 Выводы по главе 1............................................................................................43

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

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

автоматами..............................................................................................................46

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

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

2

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

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

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

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

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

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

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

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

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

3. УСТАНОВОЧНЫЕ ЭКСПЕРИМЕНТЫ С НЕДЕТЕРМИНИРОВАННЫМИ АВТОМАТАМИ........................................................................................................79

3.1 Безусловные установочные эксперименты с неинициальными недетерминированными автоматами...................................................................79

3.1.1 Синтез установочных последовательностей при безусловном эксперименте с недетерминированным автоматом...........................................84

3.1.2 Оценка сложности безусловного установочного эксперимента............88

3.1.2.1 Отношение выводимости на множестве непустых подмножеств конечного множества......................................................................................89

3.1.2.2 Описание класса недетерминированных автоматов, для которых установочная последовательность имеет экспоненциальную длину........92

3.2 Условные установочные эксперименты с недетерминированными автоматами............................................................................................................101

3.2.1 Установочный тестовый пример..............................................................101

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

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

3.2.3 Оценка сложности условного установочного эксперимента................105

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

3.4 Результаты главы 3...............................................

106 107

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ........................................................................................................127

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

ПРИЛОЖЕНИЕ А....................................................................................................137

Введение

Актуальность проблемы. Задача синтеза различных «умозрительных экспериментов» с конечными автоматами была и остается актуальной. Данная задача была поставлена Э. Муром в одноименной статье в 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.

Кушик Н.Г. Лока�