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

Томский государственный университет _ _ _

РРО од 2 2 ДЕК т

УДК 519.713.4, 519.718.7

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

к!п

Прокопенко Светлана Анатольевна

МИНИМИЗАЦИЯ ПРОВЕРЯЮЩИХ ТЕСТОВ ДЛЯ

СИСТЕМ ЛОГИЧЕСКОГО УПРАВЛЕНИЯ МЕТОДАМИ ТЕОРИИ КОНЕЧНЫХ АВТОМАТОВ

Специальность 05.13.01 «Управление в технических системах»

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

Томск 2000

Работа выполнена в Томском государственном университете.

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

профессор Евтушенко Н.В.

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

профессор Матросова А.Ю.

кандидат технических наук, ст. н.с. Захарова Г.Б.

Ведущая организация: Томский политехнический университет

Защита состоится « » декабря 2000 г. в 14.30 на заседанш диссертационного совета Д063.53.03 при Томском государственно)! университете по адресу: 634050, г. Томск, пр. Ленина 36.

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

Автореферат разослан « 2.3 » ноября 2000 г.

Ученый секретарь дисоерТгциоьик /р совета,

к. ф.-м. н., доцент / / _Б.Е. Тривоженко

ШТ. и .о

Общая характеристика работы

Актуальность проблемы. Сложность современных систем логического фавления, таких как протоколы вычислительных сетей, интегральные :емы и т.п., постоянно возрастает, технологии производства систем зстоянно меняются и совершенствуются, и, как результат, методы синтеза 1чественных проверяющих тестов не успевают за этими процессами, сполозование математических моделей при синтезе проверяющих тестов ззволяет автоматизировать процесс построения тестов с гарантированной )лнотой, т.е. тестов, обнаруживающих все наиболее вероятные ¡исправности для данной технологии производства. Однако, если описание ютемы произвольное, то может оказаться, что известные методы не могут >1ть использованы даже с применением средств вычислительной техники 1-за громадного объема необходимых вычислений. В этом случае ¡обходимо минимизировать тесты, доставляемые формальными методами, »хранив при этом возможность обнаружения наиболее вероятных ¡исправностей в системе.

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

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

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

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

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

Для достижения поставленной цели необходимо решить следуюши задачи.

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

2. Проверяющий тест можно сократить без потери его полноты, если дв> его последовательности обнаруживают одно и то же множеств! неисправностей. Таким образом, при сокращении проверяющих тестов дп: компонент автоматной сети необходимо полностью охарактеризоват множество неисправностей в компоненте, обнаружпмых каждой тестово1 последовательностью. Ввиду большого количества неисправностей данна; характеризация не должна основываться на явном переборе все: проверяемых компонент. На основе полученных результатов разработат: технологию минимизации полных проверяющих тестов для компоненть сети из детерминированных автоматов.

3. Исследовать возможности минимизации полных проверяющих тесто: для сетей из недетерминированных автоматов.

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

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

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

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

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

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

Достоверность полученных результатов. Все научные положения и лводы, содержащиеся в диссертации, основаны на утверждениях.

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

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

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

1. Грант МО РФ (МОПО) 1998-2000 гг., раздел "Автоматика и телемеханика. Вычислительная техника", научно-исследовательская работа "Разработка математических и программных средств для проектирования оптимальных контроллеров методами структурной теории автоматов"

2. Программа МО РФ " Научные исследования высшей школы в области производственных технологий", раздел "Интеллектуальные системы автоматизированного проектирования и управления производством", НИР "Разработка интеллектуальной системы автоматизированного проектирования и тестирования цифровых контроллеров" (2000).

3. Межвузовская научно-техническая программа "Конверсия и высокие технологии. 1997-2000 гг.", раздел "Информационные технологии, электроника и связь", проект 95-1-21 "Информационные компьютерные технологии дискретного математического моделирования, анализа, синтеза и тестирования сверхскоростных интегральных схем логического управления".

4. Госбюджетная тема "Диаконт" 1996-2000 гг., выполняемая на базе Гибирского физико-технического института при Томском госуниверситете, тучно-исследовательская работа "Исследование и разработка новых методов электромагнитного контроля и диагностики материалов, сред, >бъектов и технических систем", раздел "Разработка методик и аппаратуры ^следований".

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

Апробяцня работы. Результаты, вошедшие в работу, обсуждались на аседаниях совместного семинара кафедры математической логики и роектирования радиофизического факультета ТГУ, кафедры рограммирования факультета прикладной математики и кибернетики ТГУ лаборатории синтеза дискретных автоматов Сибирского фнзико-ехнического института при ТГУ. Кроме того, они докладывались на онференциях, в том числе и международных, в г г. Еври (Франция), Оттаве Канада), Минске, Екатеринбурге, Томске, что подтверждается убликациями докладов и тезисов докладов.

Структура и объем диссертации. Диссертация состоит из ведения, 4 глав, заключения и списка используемой литературы. ,иссертацня содержит 18 рисунков и 5 таблиц. Объем диссертации эставляет 99 стр., в том числе: титульный лист - 1 стр., оглавление - 4 стр., сновкой текст - 82 стр., библиография из 63 наименований - 7 стр., риложение - 5 стр.

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

Первая глава диссертации содержит необходимые понятия и пределения теории автоматов, а также краткий обзор публикаций по теме юсертацин. Конечные автоматы представляют специальный класс ункций, которые сопоставляют каждому слову во входном алфавите одно ти несколько слов той же длины в выходном алфавите. Формально под щечным, возможно недетерминированным, автоматом понимается ншиальный конечный автомат, т.е. пятерка /4=(5,Т,}7>Л). где конечное

множество состояний с выделенным начальным состоянием X и У -конечные непустые входной и выходной алфавиты, И - функция поведения, определенная на множестве ЗхХ со значениями в множестве 2ЛГ, где есть множество непустых подмножеств множества 5хГ, т.е. к. £хХ-»2Хх>. Функция И имеет две проекции: Л1 и !?, которые для любой аеЛ" определяются следующим образом: //'(■?,а)={/ ЬуеУ^^еИ^а))},

Недетерминированный автомат /1 называется наблюдаемым, если для любой пары ($,*)е5хX и любого увУ имеет место 1И(5»еЛ(л,х)} 1^1, т.е. из одного состояния не может быть более одного перехода, помеченного одним выходным символом. Автомат А называется детерминированным, если для любой пары справедливо |//(.1уг) (= 1. В детерминированном автомате вместо одной функции поведения И обычно используют две функции: функцию переходов 5. 5хЛ'—и функцию выходов Л: SxX—>У. Состояние 5 называется достижимым из л0, если существует входная последовательность а со свойством Л(%а)э5. Множество 1-{е,аь...,ап.1}оХ' называется множеством достижимости автомата А, если любое состояние автомата достижимо из начального состояния по некоторой последовательности из множества V, т.е. У^е53аеГ(Л(50,а)э5). Для последовательности ае(ХхУ)' мы далее обозначаем через а;Л-, х-проекцию последовательности а, т.е. последовательность, полученную из а путем удаления всех символов уе У.

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

Автомат В=(Т^,У^,(0) называется редукцией автомата А (обозначается ВйА), если УаеА'*(^2(/о,а:)сЛ2(5о,а))- Автомат В называется эквивалентным автомату А (обозначается В^А), если УОтношения редукции и эквивалентности для детерминированных автоматов совпадают.

В задачах тестирования так же используется отношение различимости 1ежду состояниями автомата. Состояния s, и s, являются различимыми в [втомате А, если существует входная последовательность Д такая, что г2(s„fi)#h2(sl,f]). Автомат А называется приведенным (минимальным), если ice состояния в нем попарно различимы. В приведенном автомате А шожество входных последовательностей W. по реакциям на которые -азличаются любые два состояния автомата, называется множеством Различимости, т.е. для любых двух различимых состояний s„s,eS в шожестве IV существует последовательность Д для которой h2{s,,fS)±h~(.s;,P). Множество W, входных последовательностей, по реакции на которые можно тличить данное состояние .у, от всех остальных, называется дентификатором этого состояния.

В параграфе 1.3 вводится понятпе модели неисправности в терминах онечных автоматов. На практике считается, что автомат исправен, если он аходится в некотором отношении с заданным автоматом, называемым талоном. Формально модель неисправности может рассматриваться как ройка <Л,~,5>, где А - эталонный автомат, ~ есть отношение, которому олжен удовлетворять проверяемый автомат по отношению к эталонному, и Г - класс неисправностей, т.е. класс автоматов, описывающий поведение сех, возможно неисправных, систем.

Конечное множество £c.V* конечных входных последовательностей азывается полным проверяющим тестом относительно модели <Л,<,Д> с/1,=,.3>), если для всякого ЯеД такого, что автомат В не является едукцией (эквивалентным) автомату А, найдется последовательность аеЕ, а которую автомат В производит выходную последовательность, которая не эдержится в множестве выходных последовательностей автомата А (на эторую множества выходных последовательностей автоматов А и В не эвпадают).

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

композиции, ставящего в соответствие двум наблюдаемым автоматам С=(адх2,Г,хЦЛ,ло) " автомат Л«С=(^х7'Д'|хА'2,}',хГ2,

//до'о) с входным алфавитом Л\-хХ2 и выходным алфавитом К|хК2.

Рассмотрим автоматную сеть (рис.1). В каждый такт система на рис. 1 в текущем состоянии л/ воспринимает пару внешних входных сигналов 0г1,лг2) и производит пару внешних выходных сигналов О'к^) " пару

2

соответствующих внутренних сигналов (н,г), таких, что (-М'!') и

(1,х2и). В работах Р. Брайтона, Н. Евтушенко, Т. Вилла функция Н

автомата сети А*С в состоянии х! под действием входного символа (л"1,дг2) определяется следующим образом:

Н(51, дг,х2)={ (.V 7 'гУ1Г2):3:ге23//е Ц[(х *,//>' |) е /?(л, д- ] г )&(А ',г»,2)е<17(л,дг2//)]). Такое определение автоматной сети есть, вообще говоря, расширение понятия автомата сети, которое было введено Хартманисом и Стирнсом для сети из автоматов Мура.

Рис. 1. Дпухкомпоиентная автоматная сеть

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

Пусть множество содержит все автоматы, которые описывают

поведение всех, возможно неисправных, реализаций компоненты А I тестируемой сети, Лг(Л) - множество автоматов В»С, ВеЗ(А). Известно, чте

годный проверяющий тест относительно есть полный

троверяющии тест для компоненты Л относительно <Л,=, 3(.4)>.

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

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

Частичным автоматом А называется детерминированный автомат, в отором неопределенные переходы, которые могут осуществляться с любым ыходным символом в любое состояние, не определяются. Таким образом, астичный автомат есть семерка объектов (Л1,.^>',где , Л' - конечное [ножество состояний, X и У - конечные множества входных и выходных имволов, 5: О^-^й и А: Д>}' - функции переходов и выходов, 1)АаХ<Х -тожество определенных переходов в А, \0- начальное состояние.

Последовательность ^....г^еЛ* называется допустимой в состоянии 5, ели существуют к состояний ль...л из Л', такие, что сХ5,Х))=5, и (>(л-,,.\'м)=Vь = \,...,к-\. Множество входных последовательностей, допустимых в □стоянии л автомата А, обозначается Л^*(.?). Множество входных оследовательностей, допустимых в состоянии % обозначается Х,\ .

Пусть у/, (р,/)д, г/о). Состояние ц автомата Б называется

зазижвивалентпым состоянию 5 автомата А, если (1) Хп'((])^}ХА'(.ч) и (2) 'аеЛл*(5) [<р(<7,а)=Л(5,а)]. Если состояние </ квазиэквивалентно состоянию 5, эстояние .V квазиэквивалентно £/, и ХА (л)-0, то состояния q и л называются

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

Состояния л, н л, называются различимыми, если существует входная последовательность ауеХ.| (л,)г\\'|'(л,), такая, что Л(л„а„)^Я(л/,«,/). Говорят, что последовательность а„ различает состояния .у, и л,. Состояния в, и .у, называются неотличимыми по входному символу г, если <5(^„г)=с5(л;,х) и /1(5„лг)=Л(.^,х). Множество .?,£.!>,/'*/!, где аи - входная

последовательность, различающая состояния .у, и s/ из называется идентификатором состояния 5,. Идентификатор IV, называется однородным, если 1У={а\, и а имеет вид х...х , для некоторого хеХ. Последовательность а, допустимая во всех состояниях автомата и обладающая свойством

называется диагностической

последовательностью. Диагностическая последовательность называется однородной, если она имеет видх...\", для некоторого геЛ'

Пусть Д,(А") - множество полностью определенных автоматов с входным алфавитом Хп числом состояний не более чем ;/, и Е - конечное множество допустимых входных последовательностей автомата А. Множество Е называется проверяющим тестом для автомата А в классе 3„(Х), если для любого автомата В из неквазиэквивалентного автомату А, существует

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

Большинство методов синтеза тестов относительно модели "черного ящика" основываются на методе, предложенным М П. Василевским. Метод Василевского строит полный проверяющий тест /'>ПГ^Г.№и...иГЛ*""' IV относительно модели <А,=,С1Щ(Х)>. Известно, что данный тест можно сократить за счет использования идентификатора состояния, в которое яереходит автомат под действием последовательности из множества ГА*""'1, т.е. множество . .иГА"'"*1IV, есть полный проверяющий тест

относительно данной модели неисправности. Более того, эксперименты, проведенные М. Косаревой п И.Б. Куфаревой, показали, что проверяющий тест, доставляемый данным методом с использованием идентификаторов состояний, по длине близок к минимально возможному относительно модели "четного ящика". Поэтому в данной главе решается задача

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

В параграфе 2.2 исследуются параметры автоматов, влияющие в большей степени на длину проверяющего теста.

Пусть множество достижимости У приведенного автомата с п состояниями является префиксзамкнутым, т.е. \/ахе1'—>аеГ. Если при построении проверяющего теста использовать суффиксзамкнутое множество различимости И7, т.е. \fxfie И7—>/?е IV, то проверяющий тест, построенный Ж-методом относительно модели <<4,= •Л'„(.А')>, есть I 'XIV. Если множество различимости состоит из идентификаторов состояний, то проверяющий тест относительно той же модели есть ПУиУХ1У,.

Утверждение 1. Общая длина полного проверяющего теста УХ\У не превышает величины 1.{УХ)\ И'1

Можно оценить, что ЦУХ)<п(т-\\ где п и т - число состояний и входов автомата, и где 1.ср есть средняя длина последовательности в IV,

1-ср<>и " \УХ\=р, где р - число определенных переходов автомата. Таким образом, ЦГС)<\Щп(т-\+р). Все параметры, кроме мощности множества IV, являются постоянными для данного автомата. По этой причине можно ожидать, что длина полного проверяющего теста для автомата будет короче, если автомат обладает однородной диагностической последовательностью, или каждое его состояние имеет однородный идентификатор.

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

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

В параграфе 2.4 рассматривается автономный частичный автомат А, т.е. автомат с одним входным символом, вводятся вспомогательные определения, формулируются условия доопределения частичного автомата до полностью определенного.

Пусть Л = (5, {.г},К,<5,Д,Д|) - автономный частичный автомат. Граф

переходов в автомате А имеет цикл (51—..—мД если /= 1.....к-

1, к>\ и Состояние у называется истоковым состоянием автомата

А, если не существует переходов, ведущих в это состояние.

Рассмотрим произвольную цепочку .т 1 ——>... —с истоковым состоянием Будем говорить, что цепочка заканчивается в состоянии л*, если (%дг) - неопределенный переход. Цепочка замыкается {циклическая), если А>/>1, т. е. (VI-»...—- цикл. Циклическая цепочка,

истоковое состояние которой не эквивалентно истоковым состояниям других циклических цепочек, называется доминантной циклической цепочкой в автомате/1.

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

Случай 1. Все цепочки заканчиваются в состоянии 5. Автомат/1 не имеет циклов. В этом случае выберем самую длинную цепочку Л|—»¿^-»...н« и определим переход из состояния 5 под действием входного символа дг следующим образом: <5(л,дг)=5| и *)=>', где выходной символ у такой, что последовательность /Цльлг).. .л(5ц,дф' не является циклической. Если |К|>1, то такой выходной символ всегда существует.

Случай 2. Автомат А имеет циклы, и все цепочки заканчиваются в состоянии В этом случае, выберем произвольный цикл (Л|—к..—и определим переход из состояния у в состояние 51, т.е. «5(а,дг)=Л1, с выходным символом Л(х^с)=у, таким, чтод^Л^,*).

Случай 3. В автомате А есть циклические цепочки, но ни одна из них не является доминантной. Для того чтобы доопределить неопределенный переход (5,х), выберем произвольную цепочку ».. .->%

заканчивающуюся циклом (VI-»...—>ч), где />1. Так как состояние 5| эквивалентно некоторому состоянию цепочки, то оно будет эквивалентно состоянию SJ из цикла, /+1 <]<к. Положим <5(5,дг)=л; с выходным символом

Случаи 4. В автомате А имеется доминантная циклическая цепочка (.?! —»...—>5-,4] —>5*), />1, такая, что состояние не эквивалентно никакому другому состоянию цепочки. В этом случае положим с любым

выходным симвом.

Теорема 2. Пусть А=(Ь',{х},У,8,А,Ол) - частичный автомат с одним неопределенным переходом (л,дг). Состояние 5 в полностью определенном автомате А\ полученном одним из описанных выше способов, различимо с любым другим состоянием и имеет однородный идентификатор длины не большей, чем число состояний.

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

Теорема 3. Пусть А={5,{х),У,5,Х,0^ - частичный автомат. Если автомат А доопределить согласно предложенной в разделе 2.4 технологии, то состояние л, в котором переход в автомате А не определен, в доопределении различимо с любым другим состоянием и имеет однородный идентификатор длины не большей, чем число состояний.

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

На основе теорем 2 и 3 разработана технология доопределения неопределенных переходов в произвольном частичном автомате таким образом, чтобы всякое состояние, из которого есть хотя бы один неопределенный переход, имело в доопределении однородный идентификатор. Технология описана в параграфе 2.5. Если в каждом состоянии есть хотя бы один неопределенный переход, то доопределенный автомат является минимальным с однородными идентификаторами состояний. Результаты экспериментов, проведенных нами и канадскими исследователями, представленные в параграфе 2.6, показывают, что почти

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

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

В параграфе 3.1 рассматривается модель неисправности <4*С,=,Д •(/!)>, где А»С - автомат, описывающий поведение эталонной сети, состоящей из контекста С, который описывает совместное поведение исправной части системы, и компоненты А, в которой возможны неисправности. Множество Лс(/4) состоит из детерминированных автоматов с входным алфавитом X и выходным алфавитом У, описывающих поведение сетей состоящих из контекста С, но, возможно, другой компоненты из множества ДЛ). Для простоты изложения нашего подхода в этой главе мы используем частный случай сети на рис. 1, когда тестируемая компонента не имеет внешних входов и выходов (рис.2). Известно, что результаты, полученные для этого случая, справедливы для сети общего вида. Показано, как избыточный проверяющий тест для компоненты сети может быть сокращен без потери полноты.

Рис. 2. Двухкомпонентная автоматная сеть

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

обнаружить неисправную сеть при подаче данной тестовой последовательности а.

В параграфе 3.3 приведены определения и сформулированы утверждения, позволяющие минимизировать проверяющие тесты.

Пусть а - входная последовательность сети. Построим регулярное множество С(а) входо-выходных пар в алфавитах V и 2 следующим образом. Пара р/у&С{а), если ¡3 есть {/-реакция контекста на входную последовательность (а,у), в то время, как К-реакция контекста на (а,у) не совпадает с реакцией эталонной сети на последовательность а. Входо-выходная пара в алфавитах V и 2 называется обпаружимой тестовой последовательностью а, если начальный отрезок этой пары содержится в регулярном множестве С(у) некоторого начального отрезка у последовательности а Иными словами, входо-выходная пара в алфавитах 11 и 2 обнаружима тестовой последовательностью а, если а обнаруживает всякую неисправную сеть, содержащую компоненту с такой входо-выходной последовательностью.

Регулярное множество проверяющего теста С(75) определяется как объединение регулярных множеств С(а) по всем последовательностям ае7"Л". Входо-выходная пара в алфавитах 11 и 2 называется обнаружтюй тестом ТЬ\ если данная входо-выходная пара обнаружима хотя бы одной последовательностью из множества ТЯ.

Теорема 4. Тестовая последовательность а обнаруживает неисправную сеть, если и только если компонента сети содержит последовательность из регулярного множества С(а).

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

Теорема 5. Пусть 71У - полный проверяющий тест относительно модели <Л*С,=,Лс(/1)> и РсЖ Р есть полный проверяющий тест относительно модели <Л»С,= Зс(А)>, если С(Р) содержит каждую последовательность из Г(75).

В пункте 3.3 представлен также разработанный алгоритм построения регулярного множества С(а) для тестовой последовательности а.

Так как все регулярные множества в нашем случае являются конечным», то теорема 5 позволяет решать задачу минимизации полного проверяющего теста относительно модели <А*С=,Зс(А)> как задачу нахождения строчного покрытия булевой матрицы минимальной стоимости, строкам которой поставлены в соответствие тестовые последовательности, а столбцам -последовательности из регулярного множества проверяющего теста. На пересечении /-й строки и у'-го столбца ставится 1, если входо-выходная последовательность принадлежит множеству С'(сг,), где а, - /-я последовательность проверяющего теста. Методы решения задачи хорошо известны. Современные средства вычислительной техники позволяют решить задачу нахождения покрытия минимальной стоимости для матриц достаточно большой размерности.

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

<А»С,=,3„(Х)>) где п - число состояний состояний эталонной сети, и является избыточным для компоненты, так как проверяет так же контекст, который предполагается исправным. Предложенный метод позволяет сократить исходный тест в среднем на 30 процентов.

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

В параграфе 4.1 рассматриваются модели <Л*С,=, Лс(Л)> и <А»С,<Зс(Л)>, где /(•(.' - автомат, описывающий поведение эталонной сети, состоящей из контекста С, который описывает совместное поведение исправной части системы, и компоненты А. Множество Зс{А) состоит из недетерминированных автоматов с входным алфавитом X и выходным алфавитом У, описывающих поведение сетей, состоящих из контекста С, но, возможно, другой компоненты из множества -3(/1). Показано, что избыточный проверяющий тест относительно данной модели может быть сокращен без потерн полноты как для эквивалентности, так и для редукции с использованием подхода, предложенного в предыдущей главе.

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

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

Теорема 6. Пусть 75' - полный проверяющий тест относительно модели <4»С,<,Зс(А)> и Рс:ТБ. Р есть полный проверяющий тест относительно модели <4«С,<,Лс(Л)>, если С(Р) содержит каждую последовательность из С(75).

Так как в этом случае все регулярные множества тоже конечны, то задачу минимизации полного проверяющего теста можно решать как задачу нахождения строчного покрытия булевой матрицы минимальной стоимости, строкам которой поставлены в соответствие тестовые последовательности, а столбцам - последовательности множества С(75). На пересечении /-й строки /-го столбца ставится 1, если /'-я входо-выходная последовательность принадлежит множеству С(а,), где а, - /-я последовательность проверяющего теста.

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

Пусть а=Х\ .. ,хк - входная последовательность сети, и Р=У\.. ..VI- - одна из

возможных реакций эталонной сети на последовательность а. Через С(а,Р) обозначим множество входо-выходных пар в алфавитах U и Z, при наличии которых проверяемая сеть может выдать выходную последовательность ¡} на входную последовательность а. Рассмотрим произвольную входо-выходную последовательность эталонной сети у/5.

Утверждение 7. Пусть L - сеть с контекстом С. alfi и у/5 - входо-выходные последовательности эталонной сети, и для любой последовательности из множества С(а,Р) существует начальный отрезок, который содержится в множестве С(у,<5). Если alfi - входо-выходная последовательность сети L, то yiô также является входо-выходной последовательностью сети L.

В параграфе 4.3 изложен предложенный алгоритм построения множества C(a,/J), и показано, что на основе утверждения 7 задача минимизации проверяющего теста может быть сведена к задаче нахождения строчного покрытия булевой матрицы минимальной стоимости, строкам которой поставлены в соответствие последовательности у15, а столбцам -входо-выходные последовательности множества C{y,S). На пересечении /'-й строки и j-ro столбца ставится 1, если у-я входо-выходная последовательность принадлежит множеству C(y,S), где у!5- входо-выходная последовательность эталонной сети, и у - последовательность проверяющего теста.

Данный подход имеет преимущество по сравнению с явным перебором неисправных сетей, как предлагалось C.B. Яблонским. В случае, когда компонента имеет п состояний, m входов и р выходов, и неисправности не увеличивают число состояний компоненты, число неисправных сетей равно рт", что не позволяет перечислил все неисправные сети даже для небольших т,пнр.

Заключение

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

На защиту выносятся следующие результаты:

1. Исследовано влияние параметров ^-метода на длину проверяющего теста для приведенного автомата. Предложен способ выбора данных параметров для получения более короткого проверяющего теста.

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

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

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

Список публикаций по теме диссертации

1. A. Cavalli, S. Prokopenko, N. Yevtushenko. Fault detection power of a widely used test suite for a system of communicating FSMs. Proceedings of IFIP WG 13.1 Intern. Workshop on Protocol Test Systems, Ottawa, Canada, 2000, pp. 35-56.

2. C.A. Прокопенко, H.B. Евтушенко. Минимизация проверяющих тестов для сложных многокомпонентных устройств. Материалы 3 международной конференции "Автоматизированное проектирование дискретных систем", Минск, 1999, том 3, с. 14-21.

3. Н.В. Евтушенко, С.А. Прокопенко. Построение проверяющих тестов для входо-выходных полуавтоматов. Материалы 2 всероссийской конференции "Новые информационные технологии в исследовании дискретных структур", Екатеринбург, 1998, с. 216-219.

4. С.А. Прокопенко. Построение проверяющих тестов для недетерминированных автоматов относительно эквивалентности. Тезисы

докладов молодых ученых СФТИ на конференции, посвященной 70-летию института, Томск, 1998, с. 60-61.

5. С.А. Прокопенко, Н.В. Евтушенко. К построению легко тестируемых автоматов. Материалы 2 международной конференции "Автоматизированное проектирование дискретных систем", Минск, 1997, том 3, с. 66-74.

6. N. Yevtushenko, A. Petrenko, R Dssouli, К. Karoui, and S. Prokopenko. On the design for testability of communication protocols. Proceedings of IFIP WG 6.1 International Workshop on Protocol Test Systems, Evry, France, 1995, p.p. 271286.

Введение.

1. Определения, обозначения, обзор литературы.

1.1. Автоматы.

1.2. Отношения между автоматами.

1.3.Модель неисправности и проверяющие тесты для автоматов.

1.4. Автоматные сети.

1.5.Проверяющие тесты для компоненты автоматной сети.

1.6.Методы построения тестов для изолированных автоматов.

1.6.1. Ж-метод.•.

1.6.2. Построение проверяющего теста для недетерминированного автомата относительно эквивалентности.:.

1.6.3. Построение проверяющего теста для недетерминированного автомата относительно редукции.

1.7.Методы построения теста для компоненты сети.

1.7.1. Методы построения теста для компоненты сети на основе сетевого автомата.

1.7.2. Тесты для компоненты сети на основе сетевого эквивалента.

1.8. Выводы по главе.

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

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

2.2. Оценка длины проверяющего теста.:.

2.3.Критерий доопределения неопределенных переходов.

2.4.Частичный автомат с одним входом.

2.4.1. Вспомогательные определения.

2.4.2. Частичный автомат с одним неопределенным переходом.

2.4.3. Частичный автомат с несколькими неопределенными переходами.

2.5. Доопределение неопределенных переходов.

2.6.Экспериментальные результаты.

2.7. Выводы по главе.

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

3.1. Модель неисправности.

3.2.0бнаружимые входо-выходные последовательности компоненты.

3.3.Минимизация проверяющего теста относительно эквивалентности.

3.3.1. Обнаружимые входо-выходные пары компоненты.

3.3.2. Построение характеристических множеств.

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

3.4. Экспериментальные результаты.

3.5.Сравнение предложенного метода с явным перебором неисправных компонент.

3.6. Выводы по главе.

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

4.1. Модель неисправности.

4.2.Минимизация проверяющего теста относительно редукции.

4.2.1. Обнаружимые входо-выходные пары компоненты.

4.2.2. Сведение задачи минимизации теста относительно редукции к задаче покрытия булевой матрицы.

4.3.Минимизация проверяющих тестов относительно эквивалентности.

4.3.1. Сохранение внешнего поведения.

4.3.2. Построение множества С(а,р).

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

4.4. Выводы по главе.

Актуальность проблемы. Сложность современных систем логического управления, таких как протоколы вычислительных сетей, сверхбольшие интегральные схемы (СБИС), постоянно возрастает; технологии производства систем постоянно меняются и совершенствуются, и, как результат, методы синтеза качественных проверяющих тестов "не успевают" за этими процессами [1-4]. Использование математических моделей при синтезе проверяющих тестов позволяет автоматизировать процесс построения тестов с гарантированной полнотой, т.е. тестов, обнаруживающих все наиболее вероятные неисправности для данной технологии производства. Однако, если описание системы произвольное, то может оказаться, что известные методы синтеза тестов не могут быть использованы даже с применением средств вычислительной техники из-за громадного объема необходимых вычислений. В этом случае необходимо минимизировать тесты, доставляемые формальными методами, сохранив для них возможность обнаруживать наиболее вероятные неисправности в системе.

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

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

Другой подход к минимизации тестов основан на модульном строении большинства систем. В этом случае система представляется как сеть из конечных автоматов, каждый из которых описывает поведение некоторой функционально законченной части системы. В случае, когда описать поведение всей системы одним автоматом не представляется возможным из-за больших размерностей реальных систем [10-13], инженер, разработчик тестов, обычно строит проверяющий тест для каждой компоненты сети в предположении, что остальные компоненты являются исправными. Однако, как известно [14], задача синтеза проверяющих тестов для автомата, компоненты сети, является значительно более сложной задачей, чем задача синтеза проверяющих тестов для изолированного автомата, т.к. управляемость и наблюдаемость автомата, компоненты сети, существенно снижаются по сравнению с изолированным автоматом. Как результат, большинство известных методов синтеза проверяющих тестов для компоненты сети доставляют множество тестовых последовательностей, часть из которых являются избыточными и могут быть удалены из теста без потери полноты теста относительно неисправностей проверяемой компоненты. Следует отметить, что в большинстве случаев количество неисправностей в компоненте достаточно велико, и поэтому такая минимизация проверяющего теста не может быть осуществлена перебором всех неисправных компонент.

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

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

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

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

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

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

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

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

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

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

1. Грант МО РФ (МОПО) 1998-2000 гг., раздел "Автоматика и телемеханика. Вычислительная техника", научно-исследовательская работа "Разработка математических и программных средств для проектирования оптимальных контроллеров методами структурной теории автоматов"

2. Программа МО РФ " Научные исследования высшей школы в области производственных технологий", раздел "Интеллектуальные системы автоматизированного проектирования и управления производством", НИР "Разработка интеллектуальной системы автоматизированного проектирования и тестирования цифровых контроллеров" (2000)

3. Межвузовская научно-техническая программа "Конверсия и высокие технологии. 1997-2000 гг.", раздел "Информационные технологии, электроника и связь", проект 95-1-21 "Информационные компьютерные технологии дискретного математического моделирования, анализа, синтеза и тестирования сверхскоростных интегральных схем логического управления"

4. Госбюджетная тема "Диаконт" 1996-2000 гг., выполняемая на базе Сибирского физико-технического института при Томском госуниверситете, научно-исследовательская работа "Исследование и разработка новых методов электромагнитного контроля и диагностики материалов, сред, объектов и технических систем", раздел "Разработка методик и аппаратуры исследований"

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

Апробация работы. Результаты, вошедшие в работу, обсуждались на заседаниях совместного семинара кафедры математической логики и проектирования радиофизического факультета ТГУ, кафедры программирования факультета прикладной математики и кибернетики ТГУ и лаборатории синтеза дискретных автоматов Сибирского физико-технического института при ТГУ. Кроме того, они докладывались на конференциях, в том числе и международных, в г.г. Еври (Франция), Оттава (Канада), Минске, Екатеринбурге, Томске, что подтверждается публикациями докладов и тезисов докладов [52-57].

Структура и объем диссертации. Диссертация состоит из введения, 4 глав, заключения и списка используемой литературы. Диссертация содержит 19 рисунков и 5 таблиц. Объем диссертации составляет 117 стр. текста, набранного в редакторе MS Word 97 (шрифт - Times New Roman Cyr, размер шрифта - 14 pt, межстрочный интервал - 1.5 строки), в том числе: титульный лист - 1 стр., оглавление - 4 стр., основной текст - 101 стр., библиография из 57 наименований - 6 стр., приложение - 5 стр.

4.4. Выводы по главе

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

-ЮЗ

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

На защиту выносятся следующие результаты:

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

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

3. Разработана технология сокращения проверяющего теста для компоненты сети из детерминированных автоматов без потери полноты теста.

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

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

1. Киносита К., Асада К., Карацу О. Логическое проектирование СБИС: Пер с япон. М.: Мир, 1988.- 309 с.

2. Скляров В.А., Новиков С.В., Ярмолик В.Н. Автоматизация проектирования ЭВМ: Учебное пособие для вузов. Мн.: Выш.ппс., 1990. -356 с.

3. Гольдман Р.С., Чипулис В.П. Техническая диагностика цифровых устройств. -М.: Энергия, 1976.- 224 с.

4. Данилин Н.С., Нуров Ю.Л. Диагностика и контроль качества изделий цифровой микроэлектроники.-М.: Издательство стандартов, 1990.-176 с.

5. Hartmanis J., Stearns R. Algebraic structure theory of sequential machines. Prentice-Hall, New-York, 1966, 210p.

6. Матросова А.Ю., Останин C.A., Паршина H.A. К синтезу контролепригодных комбинационных устройств // Автоматика и телемеханика, 1999, №2, с. 129-137.

7. Fadi Y. Busaba and Parag К. Lala. Self-checking combinational sircuit design for single and unidirectional multibit error. JETTA, 5, 1994, pp. 19-28.

8. Убар P. Проектирование контролепригодных дискретных систем (учебное пособие), Таллин, Таллинский политехнический институт, 1988, 68с.

9. S.T. Voung, A.A. Louriero, and S.T. Chanson. A framework for the design for testability of communication protocols. EFIP Transactions, Protocol Testing

10. Systems VI (the Proceedings of IFIP TC6 5th Intern. Workshop on Protocol Test Systems), North Holland, 1994, pp. 89-108.

11. Component testing for mobile and broadband telecommunications, COIMBRA, COPERNICUS project Proposal, 1996.

12. C. Besse, A. Cavalli, D. Lee. Optimizations technics and automatic test generation for TCP/IP protocols. Technical report of INT, Evry, France, 1999, 12 p.

13. D. Lee, M. Yannakakis. Principles and methods of testing Finite State Machines A Survey. Proc. of the IEEE, 84(8): 1090-1123, August, 1996.

14. Евтушенко H.B., Матросова А.Ю. Об одном подходе к синтезу проверяющих последовательностей для автоматных сетей // Автоматика и вычислительная техника, 1991, №2, с. 3-7.

15. Р.Н. Starke. Abstract Automata, North-Holland/American Elsevier, 1972, 419 P

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

17. Petrenko A., Yevtushenko N., Bochmann G.v. Fault models for testing in context//FORTE'96, 1996, September, Germany, pp. 163-178.

18. Yevtushenko N., Petrenko A., Trenkaev V. A Testing Strategy for Interacting Finite State Machines // Procceedings of the 5th Biennial Baltic Electronics Conference (BEC'96), Estoniajallinn, October 7-11,1996, pp. 137-141.

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

20. T.S. Chow. Test software design modeled by finite state machine // IEEE Transactions, SE-4, No.3, 1978, pp. 178-187.

21. Luo, G., Petrenko, A., and Bochman, v. G. Selecting test sequenses for partialli-specified finite state machines. Protocol Test Systems VII (the Proc. of IFIP WG 6.1 Intern. Workshop on Protocol Test Systems 1994), Chapman & Hall, 1995, pp. 95-110.

22. Евтушенко H.B., Петренко А.Ф. О проверяющих возможностях кратных экспериментов // Автоматика и Вычислительная техника.-1989.-№3.-С.9-14.

23. Евтушенко Н.В., Петренко А.Ф. Метод построения проверяющего эксперимента для произвольного детерминированного автомата // Автоматика и Вычислительная техника.-1990.-№5.-С.73-76

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

25. Куфарева И.Б. Применение недетерминированных автоматов в задачах синтеза проверяющих тестов для систем логического управления. Диссертация на соискание ученой степени, кандидата технических наук, Томск, 2000, 157с. (на правах рукописи).

26. Грунский И.С., Петренко А.Ф. Построение проверяющих экспериментов с автоматами, описывающими протоколы // Автоматика и Вычислительная техника.-1988.-№ 4.-С.7-11.

27. A. Petrenko, N. Yevtushenko. Test suite generation for a given type of implementation errors // Proc. of the IFIP 12th Intern. Conf. on Protocol Specification, Testing and Verifications, 1992, pp. 229-243.

28. Y. Watanabe, R. Brayton. The maximum set of permissible behaviors for FSM network // Trans, of IEEE / ACM Intern. Conf. on Computer-aided Design, 1993, pp. 316-328.

29. Т.Villa. The making of AURA П // Proc. of Intern. Workshop on Logic Synthesis, IWLS'99,1999, pp. 246-250.

30. Яблонский C.B., Чегис И.А. О тестах для электрических схем. "Успехи математических наук", 1955, вып. 4 (66), №10, с. 182-184.

31. Лукьянов Б.Д. О различающих и контрольных экспериментах с недетерминированными автоматами // Кибернетика и системный анализ, 1995, №5, с. 69-76.

32. Основы технической диагностики, под ред. П.П. Пархоменко. М.: Энергия, 1976. - 464 с.

33. Бадулин С.С., Барнаулов Ю.М., Бердышев В.А. и др. Автоматизированное проектирование цифровых устройств. М.: Радио и связь, 1981, 243 с.

34. I. Kohavi, Z. Kohavi. Detection of Multiple Faults in Combinational Logic Networks. IEEE Transactions on Computers, Vol. C-21, No.6, 1972.

35. T.Kam, T. Villa, R.Brayton, A. Sangiovanni-Vincentelli. Synthesis of finite state machines: functional optimization. Kluwer Academic Publishers, 1997. 283 p.

36. A.Petrenko, N.Yevtushenko, R.Dssouli. Testing strategies for communicating FMSs // Proc. of the 7th International Workshop Protocol Test Systems, Japan, 1994, p.181-196.

37. P. Tripathy, K. Naik. Generation of adaptive test cases from nondeterministic finite state models // IFIP Trans., Protocol Testing Systems V (the Proc. of IFIP TC6 5th Intern. Workshop on Protocol Test Systems), 1993, North-Holland, pp. 309-325.

38. A. Petrenko, N. Yevtushenko., G.v. Bochmann. Testing Deterministic Implementations from Nondeterministic FSM Specifications. Proceedings of

39. IP TC6 9th International Workshop on Testing of Communicating Systems, Germany, 1996, pp. 125-140.

40. M. Ghriga, P.G. Francl. Adaptive testing of nondeterministic communication protocols. Proceedings of the IFIP 6th International Workshop on Protocol Test Systems, 1993, pp. 349-363.

41. S. Fujiwara, G.V. Bochmann, F. Khendek, M. Amalou, A. Ghedamsi. Test selections based on finite state models // IEEE Transactions, SE-17, No.6, 1991, pp. 591-603.

42. A. Petrenko, G. v. Bochmann, R. Dssouli. Conformance relations and test derivation // Proceedings of 6th IFIP International Workshop on Protocol Test Systems, France, 1993. pp. 161-182.

43. G. v. Bochmann, A. Petrenko. Protocol testing: review of methods and relevance for software testing, ISSTA'94, ACM Intern. Symp. on Software Testing and Analysis, Seattle, U.S.A., 1994, pp.109-124.

44. G. v. Bochmann, A. Petrenko, and M.Yao. Fault coverage of tests based on finite state models. The proceedings of IFIP TC6 7th International Workshop on Protocol Test Systems, 1994, Japan. ,

45. Евтушенко H.B., Петренко А.Ф., Тренькаев B.H. Метод тестирования автоматных сетей, основанный на тестируемом поведении компоненты // Автоматика и вычислительная техника.-1996.-№2.- С.48-58.

46. F.C. Hennie. Fault detecting experiments for sequential circuits. IEEE 5th Ann. Symp. on Switching Circuits Theory and Logical Design, 1964, pp. 95-110.

47. M. Yannakakis, D. Lee. Testing finite state machines: fault detection // Journal of Computer and System Sciences, 1995, 50, pp. 209-227.

48. D. Lee and M. Yannakakis. Testing finite-state machines:state identification and verification. IEEE Trans, on Computers, Vol. 43, No 3, 1994, pp. 306-320.

49. J.E. Hopkroft, J.D. Ulmann. Introduction to automata theory, languages, and computations, 1974, Addisson-Wesley, NY.

50. C.A. Прокопенко. Построение проверяющих тестов для недетерминированных автоматов относительно эквивалентности. Тезисы докладов молодых ученых СФТИ на конф., посвященной 70-летию института, 1998, с. 60-61

51. С.А. Прокопенко, Н.В. Евтушенко. К построению легко тестируемых автоматов. Материалы 2 Межд. конф. "Автоматизированное проектирование дискретных систем", Минск, 1997, том 3, с. 66-74

52. Н.В. Евтушенко, С.А. Прокопенко. Построение проверяющих тестов для входо-выходных полуавтоматов. Материалы 2 Всероссийской конф. "Новые информационные технологии в исследовании дискретных структур", Екатеринбург, 1998, с. 216-219

53. С.А. Прокопенко, Н.В. Евтушенко. Минимизация проверяющих тестов для сложных многокомпонентных устройств. Материалы 3 Межд. конф. "Автоматизированное проектирование дискретных систем", Минск, 1999, томЗ, с. 14-21

54. N. Yevtushenko, A. Petrenko, R Dssouli, K. Karoui, and S. Prokopenko. On the design for testability of communication protocols. Proc. of the 6 Int. Workshop on Protocol Test Systems, 1995, p.p. 271-286.1. УТВЕРЖДАЮ1

55. Проректор по, научной работе ТГУ1. В.Н.декабря 2000г.1. СПРАВКА

56. Научный руководитель раздела,профессор '^Ь-ЛЕвтушенко Н.В.1. Заведующий отделом 102профессор- •»»1. Семенов В.С.

57. УТВЕРЖДАЮ" ебной работе ТГУ ¿Ревушкин А.С. ЗРдекабря 2000г.1. АКТо внедрении результатов диссертации Прокопенко С.А. в учебный процесс ТГУ

58. Зав. кафедрой математической логики и проектирования РФФ,Л

59. Декан радиофизического факультета, доцент кяЖл йи/ Малянов С.В.профессор 7Г Евтушенко Н.В.