Применение недетерминированных автоматов в задачах синтеза проверяющих тестов для систем логического управления тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Куфарева, Ирина Борисовна

• Куфарева, Ирина Борисовна
• кандидат технических наук
• 2000

Оглавление диссертации кандидат технических наук Куфарева, Ирина Борисовна

Введение.

1. Основные понятия, постановка задачи и обзор существующих методов ее решения.

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

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

1.2.1. Отношения конформности.

1.2.2. Отношения различимости.

1.2.3. Операция ^-пересечения автоматов.

1.2.4. Наблюдаемая форма автомата.

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

1.4. Применение недетерминированного автомата для описания эталонного поведения системы.

1.5. Мутационный автомат и его применение для описания класса неисправностей.

1.6. Постановка задачи.

1.7. Обзор существующих методов.

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

2. Стратегия построения тестов относительно модели <А,<,8иЬ(М)> на основе отличающих автоматов.

2.1. Структура теста.

2.1.1. Построение проверяющего теста на основе верхней оценки длины отличающей последовательности.

2.1.2. Структура Василевского.

2.1.3. Обобщение структуры Василевского на случай модели <А,<,ЗиЬ(М)>

2.2. Отличающие автоматы.

2.3. Построение теста относительно модели <А,<,5иЬ(М)>.

2.3.1. М-покрывающие множества.

2.3.2. Построение теста на основе М-покрывающих множеств.

2.3.3. Построение М-покрывающих множеств.

2.3.3.1. ¿-полные и ¿-конфликтные продолжения путей.

2.3.3.2. Множества-спутники ¿-полных продолжений путей в отличающем автомате.

2.3.3.3. Применение достаточных условий ¿'-полноты и ¿-избыточности продолжения путей.

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

3. Методы построения тестов для частных случаев модели

A,<,Sub{M)>

3.1. Построение тестов для детерминированного автомата или недетерминированного автомата с попарно s-несовместимыми состояниями в классе подавтоматов произвольного мутационного автомата М.

3.1.1. Запрещенные подмножества состояний отличающего автомата и их характеристические множества.

3.1.2. Построение М-покрывающих множеств.

3.1.3. Построение теста.

3.2. Построение тестов для недетерминированного автомата в классе автоматов с ограниченным числом состояний.

3.2.1. Представление основных свойств отличающего автомата в терминах эталонного автомата.

3.2.1.1. Свойства А -проекций путей в отличающем автомате.

3.2.1.2. Ловушки.

3.2.2. Построение теста на основе m-покрывающих множеств.

3.2.3. Построение т-покрывающих множеств.

3.2.3.1. Функция подсчета состояний.

3.2.3.2. Алгоритм построения m-покрывающих множеств.

3.3. Построение тестов для недетерминированного автомата с попарно s -несовместимыми состояниями в классе автоматов с ограниченным числом состояний.

3.3.1. Основные свойства m-покрывающих множеств.

3.3.2. Построение теста.

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

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

4.1. Выбор параметров метода построения теста.

4.1.1. Стратегия М-покрывающих множеств и выбор Е.

4.1.2. Выбор множества V.

4.2. Метод подсчета состояний.

4.3. Исследование качества теста, полного относительно выходных неисправностей.

4.3.1. Одиночные константные неисправности и перепутывания входов

4.3.2. Неисправности, не увеличивающие число состояний.

4.4. Построение тестов для компонент автоматных сетей.

4.4.1. Построение теста на основе автомата сети.

4.4.2. Построение теста на основе сетевого эквивалента компоненты в присутствии контрольной точки.

4.4.3. Построение теста на основе сетевого эквивалента компоненты без контрольной точки.

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

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

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

Актуальность проблемы. Тестирование является одним из важнейших этапов в процессе проектирования, производства и эксплуатации систем логического управления. Оно имеет своей целью контроль правильности функционирования системы. Проверка функционирования осуществляется путем подачи на вход системы определенных последовательностей входных воздействий - тестов, и наблюдения выходных реакций системы с последующим их анализом [1, 2, 4-6]. Если о характере возникающих в системе неисправностей ничего неизвестно, то в процессе тестирования может быть обнаружена ошибка; однако, если ошибки не обнаружены, это не гарантирует исправности системы. Поэтому обычно тестирование проводится в предположении, что возможны только неисправности определенного класса. Известно, что для всякого конечного множества неисправностей [2], а также для некоторых бесконечных [16, 40-42], существует конечный набор входных последовательностей, при подаче которого на вход тестируемой системы обнаруживаются все неисправности данного множества. Этот набор называется полным проверяющим тестом относительно данного множества неисправностей. Тестирование с применением полных тестов позволяет, в зависимости от выходных реакций системы на последовательности теста, сделать заключение либо о неправильности функционирования системы, либо об ее исправности в смысле отсутствии в ней ошибок данного класса. Проблема генерации полных тестов заключается в нахождении возможно меньшего набора входных воздействий, обнаруживающего все неисправности класса.

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

Существующие методы генерации тестов для систем логического управления могут быть условно разделены на структурные и абстрактные. В основе структурного подхода лежит представление системы в виде сети из элементарных логических элементов - вентилей. Если сеть представляет собой комбинационную схему, то есть ее реакция на очередной входной сигнал не зависит от поступивших ранее сигналов, то тест для нее может быть получен с применением многочисленных методов построения тестов относительно константных неисправностей [3]. Известно [3, 7, 8], что тесты, построенные для таких схем в предположении, что имеют место только одиночные константные неисправности, обнаруживают также высокий процент неисправностей другого рода, то есть являются достаточно качественными, а длина их не слишком велика. Основным недостатком данных методов является необходимость явного перечисления всех константных неисправностей, что представляет собой трудоемкую задачу, поскольку число вентилей в современных схемах огромно. Кроме того, неисправности, возникающие, например, в КМОП-схемах, нередко приводят к увеличению числа состояний [9], в результате чего схема из комбинационной превращается в последовательностную, и полнота тестов, построенных относительно константных неисправностей, резко падает.

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

Абстрактный подход к проблеме генерации тестов состоит в рассмотрении тестируемых систем с точки зрения их поведения, при отвлечении от внутренней структуры. В качестве математической модели поведения систем логического управления часто применяется конечный автомат [2, 4-6], адекватно отражающий специфику последовательностных систем. Модель конечного автомата традиционно используется в технической диагностике [3, 12], а в последнее время с успехом применяется также в области тестирования программного обеспечения и протоколов вычислительных сетей [13-15]. При данном подходе предполагается, что исправное поведение тестируемой системы описывается конечным автоматом, равно как и ее поведение при наличии неисправности. Таким образом, моделью возникающих в системе неисправностей служит некоторое множество конечных автоматов, называемое классом неисправностей, а полным проверяющим тестом - множество входных последовательностей, обнаруживающее все неисправные автоматы этого класса.

Выбор класса неисправностей представляет собой самостоятельную задачу, решение которой требует глубокого изучения предметной области. Выбранный класс должен адекватно отражать неисправности, часто встречающиеся на практике. При этом следует иметь в виду, что чем выше мощность выбранного класса неисправностей, тем длиннее, как правило, тесты, обнаруживающие все неисправности этого класса. В ряде известных работ по построению тестов для конечных автоматов [12, 13, 17-20, 38] делается предположение о том, что неисправности не увеличивают числа состояний в системе, или увеличивают его в некоторых пределах. Другими словами, в качестве класса неисправностей рассматривается множество всех автоматов с количеством состояний, не превышающим заданного целого числа. Методы [12, 13, 17-20, 38] построения полных проверяющих тестов относительно таких классов привлекательны тем, что они не требуют явного перечисления неисправностей. Однако тесты, полные относительно класса неисправностей, не увеличивающих числа состояний системы, имеют очень большую длину, поскольку мощность такого класса экспоненциально возрастает с ростом числа состояний системы; при этом они не являются полными относительно возникающих на практике неисправностей, так как последние в ряде случаев увеличивают число состояний системы. Тесты, построенные в предположении, что количество состояний системы в результате возникновения неисправности может возрасти, но ограничено сверху некоторым целым числом, вообще неприменимы на практике из-за своих огромных размеров. В реальных ситуациях в качестве проверяющего теста часто используется обход графа переходов автомата, описывающего поведение исправной системы [4, 21], однако полнота такого теста остается мало изученной.

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

В классической технической диагностике [3, 12] система считается исправной, если и только если ее поведение на всех входных последовательностях совпадает с поведением заданного детерминированного автомата, называемого эталонным автоматом. Это требование оказывается слишком сильным, если речь идет о тестировании устройства со сниженной управляемостью и/или наблюдаемостью [28, 29], или о тестировании сетевых протоколов [35-38]. В этих ситуациях допускаются некоторые изменения в поведении системы, которые не влияют на ее пригодность, то есть система может оказаться пригодной к эксплуатации, несмотря на то, что ее поведение отличается от эталона; в технической диагностике такие изменения носят название необнаружимых или несущественных неисправностей. В ряде случаев [29-38] допустимые отклонения в поведении системы могут быть описаны с помощью недетерминированного автомата, который рассматривается в качестве эталона поведения системы. Система исправна, если ее поведение «содержится» в поведении этого автомата.

На данный момент методов построения тестов для недетерминированного эталона практически не существует. В немногочисленных работах [40-42], посвященных этой теме, в качестве класса неисправностей рассматривается бесконечное множество автоматов, для которого не обязательно существует конечный тест, вследствие чего указанные работы представляют скорее теоретический интерес. В работах по тестированию соответствия сетевых протоколов [35, 36] рассматривается узкий класс частных случаев, и полнота построенных тестов не гарантируется.

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

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

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

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

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

Реализация полученных результатов. Исследования, результаты которых изложены в диссертации, проводились в рамках работ по госбюджетной тематике Сибирского физико-технического института при Томском государственном университете (ТГУ) (программа 1995-2000 гг. «Исследование и разработка новых методов электромагнитного контроля и диагностики материалов, сред и технических систем», шифр «Диаконт», раздел «Разработка методик и аппаратуры исследований»). Разработанные в диссертации способы представления необнаружимых неисправностей с помощью недетерминированных автоматов и методы построения тестов для них нашли применение в теоретических исследованиях по гранту РФФИ (проект № 99-01-00337 «Решение автоматных уравнений и неравенств», 1999-2000). Методы генерации проверяющих тестов для недетерминированных автоматов были также использованы в процессе работы по гранту НАТО совместно с научной группой университета г. Беркли, США. Полученные теоретические результаты внедрены в учебный процесс и используются при подготовке курсов «Теория автоматов» и «Техническая диагностика» на радиофизическом факультете ТГУ и курса «Техническая диагностика» на факультете прикладной математики и кибернетики.

Предложенные методы синтеза проверяющих тестов были реализованы в виде пакета прикладных программ в работах по межвузовской научно-технической программе «Конверсия и высокие технологии. 1997-2000 гг.» (проект № 95-1-21 «Информационные компьютерные технологии дискретного математического моделирования, анализа, синтеза и тестирования сверхскоростных интегральных схем логического управления»). В пакет входят программы построения полных тестов для недетерминированного эталонного автомата и различных частных случаев предложенного в работе класса неисправностей, а именно: класса всех автоматов с количеством состояний, не превышающим заданного целого числа («метод подсчета состояний»), и класса автоматов с неисправностями выходов.

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

Апробация работы. Научные результаты [48-55], составившие основу данной работы, по мере их получения обсуждались на заседаниях объединенного семинара кафедры математической логики и проектирования радиофизического факультета ТГУ, кафедры программирования факультета прикладной математики и кибернетики ТГУ и лаборатории синтеза дискретных автоматов Сибирского физико-технического института (СФТИ) при ТГУ. Кроме того, они докладывались на конференциях, в том числе международных, в г. г. Будапеште, Минске, Новосибирске и Томске, что подтверждается соответствующими публикациями докладов и тезисов докладов [48-50, 52, 54, 55], и на научном семинаре в г. Беркли, США [53]. Также эти результаты обсуждались и были одобрены в научной группе научно-исследовательского института СИМ в г. Монреале, Канада.

Структура и объем диссертации. Диссертация состоит из введения, 4 глав, заключения и списка используемой литературы. Объем диссертации составляет 176 страниц текста, набранного в редакторе М8

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

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

В данной главе представлены результаты компьютерных экспериментов по построению полных проверяющих тестов относительно модели <А,<,8иЬ(М)> методами, предложенными в диссертации. Целью проведенных экспериментов было изучение возможности применения

158 мутационного автомата для описания различных неисправностей в системах логического управления, встречающихся на практике, а также исследование качества полных тестов относительно модели <А,<,8иЬ(М)>, построенных по методам глав 2 и 3. Результаты экспериментов позволяют сделать вывод о возможности практического применения данной модели и разработанных в диссертации методов синтеза тестов для нее.

Заключение

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

Разработан общий метод построения теста для недетерминированного автомата относительно редукции, полного в классе подавтоматов произвольного мутационного автомата. На основе этого метода предложены методы построения тестов для различных частных случае задачи. Для тех частных случаев модели <Л,<,8иЪ(М)>, для которых ранее были известны методы построения тестов, метод, предложенный в диссертации, позволяет генерировать тесты не большей, а в некоторых случаях меньшей длины. В частности, это касается случая, когда эталонный автомат А является детерминированным приведенным автоматом, а мутационный автомат М имеет произвольную структуру, и случая, когда А - произвольный недетерминированный автомат, М - мутационный автомат специального вида, описывающий всевозможные автоматы с количеством состояний, не превышающим заданного целого числа т.

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

На защиту выносятся:

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

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

3) Методы построения полных проверяющих тестов для частных случаев задачи, разработанные на основе общей стратегии:

- метод построения теста для детерминированного приведенного автомата (или недетерминированного автомата с попарно ¿-несовместимыми состояниями) и класса неисправностей, состоящего из подавтоматов произвольного мутационного автомата;

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

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

161

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

Список литературы диссертационного исследования кандидат технических наук Куфарева, Ирина Борисовна, 2000 год

1. Мур Э.Ф. Умозрительные эксперименты с последовательными машинами // Автоматы-М.: Изд-во иностр. лит., 1956 С. 179-210.

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

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

4. Богомолов A.M., Грунский И.С., Сперанский Д.В. Контроль и преобразования дискретных автоматов. Киев: Наук, думка, 1975- 176 с.

5. Богомолов A.M., Сперанский Д.В. Аналитические методы в задачах контроля и анализа дискретных устройств. Саратов: Изд-во Сарат. ун-та, 1986.-240 с.

6. Грунский И.С., Козловский В.А., Пономаренко Г.Г. Представление конечных автоматов фрагментами поведения. Киев: Наук, думка, 1990-232 с.

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

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

9. C.F. Hawkins, J.M. Soden, A.W. Righter, F.J. Ferguson. Defect classes an overdue paradigm for CMOS 1С testing // International Test Conference, 1994. -pp.413-425.

10. Ю.Матросова А.Ю. Метод обнаружения неисправностей в синхронном устройстве // Автоматика и телемеханика, 1977, №12, с 129-137.

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

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

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

14. A. Petrenko, G. v. Bochmann, R. Dssouli. Conformance relations and testthderivation // Proceedings of 6 IFIP International Workshop on Protocol Teat Systems, France, 1993.-pp. 161-182.

15. Петренко А.Ф. Эксперименты над протокольными объектами // Автоматика и вычислительная техника. 1987, № 1. - С. 16-21.

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

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

18. A. Petrenko. Checking experiments with protocol machines // Proceedings of IFIP TC6 4th International Workshop on Protocol Test Systems, 1991, North-Holland, pp. 83-94.

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

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

21. S. Naito, M. Tsunoyama. Fault detection for sequential machines by transition tours // Proceedings of Fault Tolerant Comp, Syst., 1981, p. 238-243.

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

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

24. J.A. Brzozowski, B.F. Cockburn. Detection of Coupling Faults in RAMs // Journal of Electronic Testing: Theory and Applications, No.l, 1990, pp. 151-162.

25. B.F. Cockburn, J.A. Brzozowski. Near-optimal tests for classes of write-triggered coupling faults in RAMs // Journal of Electronic Testing: Theory and Applications, No.3, 1992, pp. 251-264.

26. J.A. Brzozowski, H. Jurgensen. A model for sequential machine testing and diagnosis // Journal of Electronic Testing: Theory and Applications, No.2, 1992, pp. 219-234.

27. R. David, J.A. Brzozowski, H. Jurgensen. Random test length for bounded faults in RAMs // Proceedings of the 3rd European Test Conference, The Netherlands, 1993, pp. 149-158/

28. Горяшко А.П. Синтез диагностируемых схем вычислительных устройств. -М.: Наука, 1987.-287 с.

29. Watanabe Y., Brayton R.K. The maximum set of permissible behaviors for FSMS network // Trans. Of IEEE / ACM Int. Conf. On Compute-aided design. 1993.-p. 316-328.

30. Т.Кат, T.Villa, R.Brayton, A. Sangiovanni-Vincentelli. Synthesis of finite state machines: functional optimization. Kluwer Academic Publishers, 1997. -283 p.

31. A. Petrenko, N.Yevtushenko, G. v. Bochmann. Fault models for testing in context // Proceedings of the IFIP 1st Joint International Conference FORTE/PSTV. Chapman & Hall, 1996. pp. 163-178.

32. A. Petrenko, N.Yevtushenko, R.Dssouli. Testing strategies for communicating FSMs // Proceedings of the IFIP 7th International Workshop on Testing of Communicating Systems, 1994, pp. 193-208.

33. A. Petrenko, N.Yevtushenko, G. v. Bochmann, R.Dssouli. Testing in context: framework and test derivation // Computer communications, Vol. 19, pp. 1236-1249, 1996.

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

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

36. A. Petrenko, N. Yevtushenko., G.v. Bochmann. Testing Deterministic Implementations from Nondeterministic FSM Specifications. Proceedings of IFIP TC6 9th International Workshop on Testing of Communicating Systems, Germany, 1996, pp. 125-140.

37. P.H. Starke. Abstract Automata, North-Holland/American Elsevier, 1972, 4191. P

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

39. Лукьянов Б.Д. Детерминированные реализации недетерминированных автоматов // Кибернетика и системный анализ, 1996, №4, с. 34-50.

40. S. Boroday. Distinguishing tests for nondeterministic finite state machines.th *

41. Testing of Communicating Systems. Proceedings of 11 International Workshop on Testing of Communicating Systems. Kluwer Academic Publishers, 1998.-pp. 101-107.

42. Pomeranz, S.M. Reddy. Test generation for multiple state-table faults in finite-state machines // IEEE Transactions on Computers, Vol. 46, No 7, pp. 782-794, 1997.

43. S.H. Unger. Asynchronous sequential switching circuits. Wiley-interscience.

44. A. Petrenko, N. Yevtushenko, G.v. Bochmann. Experiments on nondeterministic systems with respect to the reduction relation. University of Montreal, Dept. Publ. #932, 1994.

45. A. Petrenko, N. Yevtushenko. Solving asynchronous equations // Formal Description Techniques / Protocol Specification, Testing and Verification. Kluwer Academic Publishers, 1998. pp. 125-140.

46. Евтушенко H.B., Тренькаев B.H. Методы синтеза проверяющих тестов для компоненты автоматной сети. Новые информационные технологии в исследовании дискретных структур. Доклады второй всероссийской конференции. - Екатеринбург, 1998. - с. 219-223.

47. Куфарева И.Б., Евтушенко Н.В. Технология разработки методов построения тестов для недетерминированных автоматов. -Международная конференция "Всесибирские чтения по математике и механике", тезисы докладов. Томск: изд-во ТГУ, 1997. - Т. 1 -С.156-157.

48. Куфарева И.Б., Петренко А.Ф., Евтушенко Н.В. Синтез проверяющих тестов для недетерминированных автоматов относительно редукции. -Автоматика и вычислительная техника, №3, 1998. С. 10-21.

49. Евтушенко Н.В., Куфарева И.Б., Петренко А.Ф. К распознаванию свойств конечно-автоматных отображений. III сибирский конгресс по индустриальной и прикладной математике INPRIM-98. Тезисы докладов, часть 4. - Новосибирск, изд-во ИМ СО РАН, 1998. - С. 94.

50. I.Koufareva. Test Suite Derivation for a Nondeterministic FSM w.r.t Reduction Relation. Talks Presented at the Meeting on Control and FSM Synthesis and Related Testing/Validation Issues. - Berkeley, 1998 (на правах рукописи).

51. Куфарева И.Б. Исследование отношений между недетерминированными автоматами. Тезисы докладов молодых ученых СФТИ на конференции, посвященной 70-летию института. - Томск, 1998. - С. 32-33.

52. Зав. кафедрой мат. логики и проектирования РФФпрофессор1. Евтушенко Н.В.

53. УТВЕРЖДАЮ" ;тор СФТИ при ТГУмарта 2000 г.1. Колесник А.Г.1. СПРАВКА

54. Organisation du Traite de l' Atlantique Norjd —p^m"i

55. Division dejAjfairot JcicntifUjucj et llEnt>ironncmtnt / SçUnti/ix and Environmental Affairs Division1. P.T^MT'IOM ÏHA^e CJAH^ér

56. SA.12.302(971217) ^ ^OdiAugtiSt, 19991. Fax: 4-I5IO UI«^1. Prof. RJC. Brayton

57. Electrical Engineering Si. Computer Science

58. University of California p—

59. Room 573 Cory Hall rQc I M H31. Berkeley, CA 94720-17701. USA.1. Dear Professor Brayton,

60. CTRICAT. ENGINEERING & COMPUTER SCIENCE

61. MVERSITY OF CALIFORNIA, BERKELEY

62. RKELEY . DAVIS . IRVINE . LOS ANGELAS • RIVERSIDE • SAN DIEGO . SANFRAN'CSCO

63. SANTA SAJUAK/. • SANTA CRU

64. CORY HAIL t 1770 iRKELEY CA 9472C-1770bnjwn® ecc3.bcrkc!cy,cdu httpi//,w»w.eec5.bei'!«!ey^du/ -brayton (510) 643-9S01 Fax: [phone]. July 26.19991. Dr. J. A Rausell-Colom

65. Programme Director for Priority Area on High Technology NATO

66. Scientific Affairs Division B-1110 Brussels Belgium1. Dear Dr. Rausell-Colom:

67. We request an extension of the NATO Travel Grant for a period of 9 months.

68. Some results in the case of the asynchronous composition operator have been published by Yevtushenko and Petrenko in the paper "Solving Asynchronous Equations".

69. Robert K. Brayton Professor