Эксперименты в эффективно заданных классах автоматов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. Н. Г. ЧЕРНЫШЕВСКОГО

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

БОРОДАЙ Сергей Юрьевич / ^

ЭКСПЕРИМЕНТЫ В ЭФФЕКТИВНО ЗАДАННЫХ КЛАССАХ АВТОМАТОВ

01.01.09 - математическая кибернетика

Автореферат

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

Саратов - 1997

Работа выполнена в Институте прикладной математики и механики HAH Украины.

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

профессор Сперанский Д.В. кандидат физико-математических наук, старший научный сотрудник Грунский И.С.

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

член-корреспондент РАЕН, профессор Сытник A.A. кандидат физико-математических наук, доцент Кальянов JI. В.

Ведущая организация: Институт проблем управления РАН

Защита состоится " ¿6 " ¿¿А£?//Л 1997г. в мин. на

заседании Специализированного совета К 063.74.04 в Саратовском государственном университете им. Н.Г. Чернышевского по адресу: 410601, г.Саратов, ул. Астраханская, 83.

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

Автореферат разослан "_"_ 1997 г.

Ученый секретарь Специализированного совета кандидат физико-математических наук, доцент П.Ф.Недорезов

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

Актуальность темы. Контроль и диагностика (расшифровка) автоматов являются старейшими, классическими и интенсивно изучающимися проблемами теории автоматов. Для конечных классов автоматов эти проблемы изучены достаточно полно в работах С.В.Яблонского, Э.Мура, М.П.Васшгевского, Я.М.Барздиня и многих других.

Для бесконечных классов изучение этих проблем находится в зачаточном состоянии. Их изучение связано с принципиальными трудностями (алгоритмическая неразрешимость в общем случае, отсутствие достаточно удобных моделей и т.п.). В последнее время ситуация изменилась в связи с появлением прикладных задач контроля и диагностики дискретных устройств на этапе их синтеза, когда задание на автомат осуществляется в виде спецификации на его заданное и запрещенное поведение. Эти спецификации задают бескопечные классы допустимых и запрещенных автоматов и требуется осуществить контроль результата синтеза на допустимость. Бесконечные классы автоматов возникают так же при контроле протоколов сети ЭВМ, при контроле компоненты сети автоматов (вычислений) и т.п. Такие классы изучались в работах А.Ф.Петренко, Н.В.Евтушенко, И.С.Грунского, И.И.Максименко, В.А.Твердохлебова, Д.В. Гавзова, В.В.Сапожникова, В.Вл.Сапожникова и др.

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

кладном плане.

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

Для достижения указанной цели поставлены и решены следующие задачи:

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

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

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

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

Новые научные результаты и положения, выносимые на защиту.

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

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

риментов для бесконечных классов конечных автоматов;

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

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

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

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

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

- предложен метод построения более простого, чем известные, теста для детерминированного автомата, неисправности которого описаны недетерминированным автоматом (функцией неис-

правпостей), содержащим как переходы автомата-эталона, так и "подозреваемые" неисправные переходы;

- впервые предложено совместное использование модели одиночных неисправностей переходов и функции неисправностей в виде недетерминированного автомата;

- введена и исследована новая модель неисправностей автомата — одиночных неисправностей состояний;

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

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

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

Диссертация выполнена в течении 1993-96 гг. в соответствии с планами научно-исследовательских работ лаборатории прикладных проблем дискретной математики ИПММ HAH Украины "Исследование обратных задач теории автоматов применительно к идентификации и распознаванию дискретных систем", номер гос. регистрации 0194U022564; тема диссертации утверждена на заседании уче-

ного совета института (прот. N 1 от 14.01.1994).

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

Апробация, Результаты работы докладывались и обсуждались на конференции "Методы и системы технической диагностики" (Саратов, 1993), II Украинской конференции по автоматическому управлению "Автоматика 95" (Львов, 1995), XII международной межвузовской конференции "Методы и средства технической диагностики" (Ивапо-Франковск,1995), XI международной конференции "Проблемы теоретической кибернетики" (Ульяновск, 1996), конференции "Интеллектуальные системы и компьютерные науки" (Москва, 1996), семинарах "Дискретпые системы и формальные языки" (ИПММ ПАНУ, Донецк), семинарах в Саратовском государственном университете.

Публикации. По результатам работы опубликовано б работ. Две из них в соавторстве с научным руководителем, остальные — самостоятельно.

Структура и объем диссертации. Диссертация содержит 120 машинописных страниц, состоит из введения, четырех глав и списка литературы. Работа включает три таблицы.

2.0В30Р СОДЕРЖАНИЯ ДИССЕРТАЦИИ

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

В первом разделе рассмотрены алгоритмические аспекты теории экспериментов с автоматами из бесконечных классов. В 1.1 вводятся необходимые понятия и определения. Эксперименты проводятся с всюду-определенными инициально-связными приведенными детерминированными автоматами Мили с входным алфавитом X и

выходным алфавитом Y.

Слова во входном алфавите X, выходном алфавите Y и алфавите X х Y называются входными, выходными и вход-выходными соответственно. Множество всех вход-выходных слов, порождаемых автоматом А из начального состояния, называется поведением автомата и обозначается Л^. Класс всех автоматов, содержащих в поведении множество вход-выходных слов w обозначаем Л.(го). Под контрольным экспериментом для автомата относительно класса понимается конечное множество его вход-выходных слов, не принадлежащее более никакому другому автомату класса.

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

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

Теорема 1.2,9, Равносильны утверждения: 1) класс А поддастся иоссгановлешпо; 2) А является подклассом поддающегоос восстано-влепию реку реи в по-пер с числимого класса; 3) существует такая частично-рекурсивная функция что класс А включается в ее область определения и окрестность любого автомата А да ее области определения не содержит ни одного автомата класса А, кроме, возможно, самого А; 4) класс А. поддается восстановлению перечисли ющим алгоритмом.

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

ствующий контрольный эксперимент для каждого автомата класса А Следствие 1.2.11 устанавливает, что существование точно различающего алгоритма есть точное условие существования восстанавливающего алгоритма для объединения двух поддающихся восстановлению рекурсивно-перечислимых классов автоматов. В 1.2 также получены точные условия существования (теоремы 1.2.5, 1.2.6, 1.2.7, следствие 1.2.8) различающих и точно различающих алгоритмов-экспериментаторов .

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

Теорема 1.3.4. Равносильны утверждения: 1) существует всюду-определенным алгоритм-экспериментатор, восстанавливающий класс А; 2) существует всюд}г-определенный алгоритм, восстанавливающий такой рекурсивпо-перечислимый класс А!, что Л С А'; 3) существует такая общсрскурсивиая функция ф, что окрестность любого автомата А не содержит ни одного автомата класса А, кроме, возможно, самого А; 4) существует итеративный алгоритм-экспериментатор, восстанавливающий класс А; 5) существует рекурсивпо-перечислимый класс контрольных экспериментов относительно класса А, содержащий по крайней мере по одному контрольному эксперименту относительно А для каждого автомата.

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

автомату иа словах длины <р(п(Н)), где <р — неубывающая общере-курсивпая функция, а п — число состояний автомата Н.

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

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

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

В 2.2 формулируются необходимые понятия и определения, постановка задачи. Инициальным недетерминированным автоматом (НД-автоматом) называется пятерка У, ¿о), где 5 — это

множество состояний, X и У — это входной и выходной алфавиты соответственно, Г : 5 X X — функция поведения, а

So — начальное состояние. Через sp обозначается множество состояний, в которые НД-автомат может переходить под действием входного слова р из состояния &, а через s(p,q) — множество тех состояний, в которые НД-автомат может переходить из .s под действием входного слова р, порождая выходное слово q. Через А обозначается множество всех выходных слов, которые НД-автомат может порождать из состояния s под действием слова р. В случае, когда для всех х £ X, у £ Y, s £ S, выполняется |й(а:,у)| ^ 1, НД-автомат называется наблюдаемым. Известно, что для каждого НД-автомата найдется наблюдаемый НД-автомат с тем же поведением. Поэтому далее рассматриваются только наблюдаемые автоматы. Эти обозначения распространяются и па автоматы-акцепторы в алфавите X X Y. В этом случае, такие акцепторы интерпретируются как НД-автоматы с входным алфавитом X, выходным алфавитом Y и выделенным множеством финальных состояний. Множество принимаемых акцептором <5 слов обозначается L(Q).

Ацикличным называется автомат, не содержащий циклов. Такой автомат всегда частичен.

Вводится понятие автомата-экспериментатора (опросника) — алгоритма-экспериментатора частного вида. Простым автоматом-экспериментатором называется ацикличный автомат акцептор в алфавите X X У, такой, что для каждого его нефиналыюго состояния д найдется только один входной сигнал х3, по которому переходы определены (то есть sxs ф 0). Такому акцептору соответствует алгоритм-экспериментатор fig, который проводит простой условный эксперимент с черным ящиком следующим образом. В начале работы начальное состоянии s® объявляется текущим. Из текущего состояния з на исследуемый черный ящик R додается входной сигнал xs (для которого sxs ф 0). Считывается выходной сигнал у исследуемого черного ящика R. Если в акцепторе s (xs, у) ф 0, то те-

кущим объявляется состояние з (хя,у). Если з (х3,у) = 0, то эксперимент прекращается, в качестве результата выдается 1 (Од (/?.) = 1). При достижении финального состояния эксперимент прекращается, в качестве результата выдается 2 (17д(/2) = 2).

Так как акцептор ацикличен, процесс проведения эксперимента всегда конечен, и результат его определен, а имепно: $1д(П) = 1, если Ь{$) П Ая = 0 , и £1Я{11) = 2, если Ь{0) П Ля Ф 0.

Кратным автоматом-экспериментатором называется конечная последовательность С}у ■ ■ - простых автома,тов экспериментаторов. В работе определен соответствующий ей алгоритм-экспериментатор ,... • Работает он следующим образом. Последовательно проводятся простые алгоритмы-экспериментаторы $2д. с черным ящиком Е для всех г от 1 до ТУ, кроме тех г, при которых из уже полученного в процессе эксперимента мпожества вход-выходных слов {и>1,,.. черного ящика Я видно, что ¡Г2д;(Л) = 1. В

качестве результата выдается тах (Я), то есть 1, если для всех г выполняется (Я) = 1 и 2 в противном случае. На классе всех простых алгоритмов-экспериментаторов зафиксирован эффективный линейный порядок. Каждому ацикличному акцептору соответствует конечная упорядоченная последовательность (¿1,... , С}^ всех максимальных (по отношению включения множеств принимаемых слов) простых автоматов-экспериментаторов, для которых выполняется Ь{(}{) С Ь(<3). Так как последовательность ... , фл/ конечна, то она является кратным автоматом-экспериментатором. В дальнейшем будем отождествлять с таким автоматом-экспе-римептатором. Легко видеть, что процесс проведения эксперимента с любым черным ящиком из А(Х, У) всегда конечен и результат его определен, а именно: Г2д(Д) = 2, если Ь(С$) П Ад ф 0, и Пд(Д) = 1, если Ь{($) П Ад = 0. В подразделе показано, что для проведения эксперимента последовательность (¿1,... ,£¿N-1 соответ-

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

В 2.3 получены (неконструктивные) точные условия, при которых произвольный акцептор является автоматом-экспериментатором, различающим классы реализации недетерминированных автоматов А "а В (теорема 2.3.5). Затем, на ее основе, получены точные конструктивные условия, при которых искомый различающий алгоритм-экспериментатор существует (теорема £.3.6). Этот результат является окончательным и центральным. Точные условия существования искомого алгоритма-экспериментатора фактически заключаются в конечности множества [Лд \ Л^] П А]дпд(, где ]А П В[ является наибольшим всюду-определенным недетерминированным автоматом, для которого Л]дПй[ Ад П Ад, а [IV] —- замыкание множества слов IV по начальным, отрезкам. Для проверки конечности этого множества строится специальный автомат К ЕЯ и проверяется на наличие циклов. Теорема 2.3.6 утверждает, что искомый алгоритм-экспериментатор существует точно тогда, когда КЕН не содержит циклов. Кроме того, на основе теоремы 2.3.6, получен метод построения различающего тупикового автомата-экспериментатора. Он позволяет строить различающий алгоритм минимальной кратнсрсти и длины, всегда, когда для данной пары автоматов различающий алгоритм существует. Найдены достижимые по порядку

верхние оценки длины, кратности и объема различающих экспериментов, равные: пш, |Х|пт и тгт|.Х^пт^ соответственно. Здесь п,т — число состояний НД-автоматов А и В соответственно.

В 2.4 найдены точные условия существования различающих автоматов-эксперимептов при ограничении на принимаемое множество слов в виде частичного недетерминированного автомата. То есть, решена задача: определить, существует ли для данных НД-автоматов А,В и частичного НД-автомата С такой различающий классы реализаций автоматов А и В автомат-экспериментатор СЦ, что £(£>) С А(С). В теореме 2.4.1 получены точные конструктивные условия существования такого простого различающего автомата-экспериментатора для непересекающихся классов реализаций, а в следствии 2.4.2 — кратного для произвольного случая. Условия сформулированы в терминах свойств специального конечного графа, который строится по автоматам А, В, С. Предложен метод построения таких различающих автоматов-экспериментаторов, когда они существуют.

В 2.5 получены точные конструктивные условия (теорема 2.5.2), при которых автомат-акцептор является различающим автоматом-экспериментатором.

Таким образом, в разделе 2 впервые получены точные конструктивные условия существования экспериментов, различающих классы реализаций НД-автоматов А и В и построены методы их проведения.

В разделе 3 изучается случай, когда автомат А детерминирован, а класс неисправных автоматов состоит из таких реализаций НД-автомата В, которые являются его подавтоматами (так называемые фиксации автомата В). При этом исправный автомат А является подавтоматом НД-автомата В и имеет тоже множество состояний БА = 5В = {^о,..., }. Такая постановка позволя-

ет говорить о неисправностях переходов эталона А, определенных НД-автоматом В. На неисправные автоматы могут накладываться дополнительные ограничения двух видов: а) одиночные неисправности переходоз; б) одиночные неисправности состоянии. Последние вводятся и изучаются впервые.

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

В 3.2 формулируются необходимые понятия и определения, постановка задачи. Рассматриваются безусловные эксперименты. Конечное множество входных слов PCX* называется проверяющим тестом для автомата А относительно класса Л, если для любого неэквивалентного автомату А автомата С найдется ахово р £ Р, для которого Xa(sq,p) Ac(sq\p). Проверяющий тест определяет контрольный эксперимент. Одиночной неисправностью переходов автомата называется его преобразование, заключающееся в изменении значений функции поведения не более, чем для одной из пар (а, х). Одипочной неисправностью состояний автомата называется его преобразование, заключающееся в изменении значений функции поведения не более чем для одного состояния s и, может быть, нескольких х. Одиночные неисправности переходов автомата А порождают класс СГ(Л) по правилу: автомат С принадлежит классу СГ(А) тогда и только тогда, когда не более чем для одной пары (з, х) выполняется неравенство FA(s, х) ф Fc(s, х). Одиночные неисправности состояний автомата порождают класс S(A) по правилу: автомат С принадлежит классу S(A) тогда и только тогда, когда не более чем для одного состояния s и, может быть, нескольких входных сигналов х выполняется неравенство Fa(s,x) ф Fc{s,x). Функция неисправностей F : S X X 2SxY порождает класс F(A) по правилу: автомат С принадлежит классу F(A) тогда и только тогда, когда для любой пары s, х выполняется i*c(s>х) Я Р(з,х)> Функция

неисправностей определена на множестве переходов этанола и определяет НД-автомат В с начальным состоянием «о, функцией поведения а класс -Р(Л) представляет собой множество его детерминированных подавтоматов. В работе показано, как от НД-автомата. В перейти к функции неисправностей, задающей тот же класс неисправностей. Функция / : (X X У)* 2я называется оценочной для класса автоматов А, если для каждого автомата С € А и для каждого слова (р, '¡) выполняется а^ (р, д) £ /(р><7)- В работе предложены соотношения, определяющие для класса Р(А) оценочную функцию. Функция / : (X X У)* 28 порождает масс А/ по правилу: С £ Л, если для каждого слова (р, (¡) выполняется (р, <]) £ /(р, д). Очевидно, что если / правильно оценивает класс А, то А С А/. В разделе рассматривается задача построения более простых, чем известные кратных контрольных тестов относительно классов 1?(А) П У(Л), Р(А) П с>(Л), А/ П А/ и оценка их сложности.

В 3.3 вводятся и исследуются базисы достижимости и различимости эталона. Базисом достижимости называется совокупность слов р0,... ,рп-1> такая, что p¿ = Если, при этом, каждый элемент р{ базиса таков, что для любого его собственного начального отрезка р выполняется неравенство з£р ф я,, то будем называть такой базис достижимости простым, а если для каждого слова р, меньшей, чем /),- длины, выполняется неравенство з^р ф л; — минималь-пьш (по длине). Пусть для каждой неупорядоченной пары состояний з^} задано такое слово р^, что Аа(^>Р;,>) Ф Совокупность этих слов будем называть базисом различимости автомата А. Если при этом для любого собственного конечного отрезка р слова р;^ выполняется равенство = Аа(^>р)> то будем называть такой базис различимости простым, а если это же равенство выполняется для любого слова р, имеющего меньшую, чем слово длину, базис называется минимальным (по длине). Пусть Л и С

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

Лемма 3.3.3. Пусть к — натуральное число, и (t, tip) £ £j для всех t € Т. Равносильны утверждения : 1) хр — минимальное по длине среди всех слов вида хр', таких что х 6 X и Хс(1,р') Ф ^A^ftP1) по крайней мере для одного I G Т; 2) хр — минимальное по длине среди всех слов вида хр', таких что х £ X и XA(tx(p,p') ф \A(tipx,p') по крайней мера для одного t £ Т.

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

В 3.4 рассматривается задача построения проверяющего теста, относительно 7(А) П F(A) (то есть для случая одиночных неисправностей описанных функцией неисправностей (IIД-автокатом). Пред-ложеи метод ее решения (алгоритм 3.4.1). Он состоит в построении множества Р, содержащего все слова вида pixpij, такие, что Sj € sf (ж, XA(s,x)), a Sj ф Sk — s'-x] и все слова вида piX, такие, что |Ад(з$,а;)| ^ 1. Теорема 3.4.1 устанавливает, что в случае, когда Pi и pij являются элементами простых базисов достижимости, множество Р является проверяющим тестом. Предложенный метод не требует моделирования неисправных автоматов, полученный тест проще известных.

В 3.5, за счет усиления требований на базис различимости, метод распространен на случай одиночных неисправностей состояний. Теорема 3.5.1 устанавливает, что в случае минимального базиса различимости, множество -Р, построенное алгоритмом 3.4.1 является

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

Известно, что ни для модели кратных неисправностей, возникающих в соответствии с функцией неисправпостей,пи для модели произвольных одиночных неисправностей переходов не было получено оценок сложности кратного теста, меньших, чем М.П.Василевским для случая произвольных неисправностей, не увеличивающих число состояний. В случае, когда недетермшшровашшй автомат В является полным (то есть \ц = (^ х У)*), тест Р, достроенный по алгоритму 3.4.1, практически совпадает с тестом Василевского. Поэтому справедливы полученные им достижимые по порядку верхние оценки для длины, кратности и объема теста, а именно: 2п — 1, п2т, п3т соответственно. Здесь ш — число входных сигналов. Предложенный выше метод построения теста рассчитан на локальные неисправности, когда автомат В существенно отличается от полного. Ясно, что в этом случае тест Р имеет меньшие значения кратности и объема. В подразделе введен параметр а, называемый степенью педетерми-нированпости автомата неисправностей В и получены оценки, связывающие а и сложность теста. Пусть

\ яе^жбх /

Здесь ¿1-число тех пар (5,ж), для которых |звж| = 1, но 1.

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

неисправностей (автоматом В) со степенью недетерминироваино-сти а в наихудшем случае, а через v(г¡,nг,a) — наименьший объем теста в наихудшем случае. Так как нас интересуют локальные неисправности, ограничимся случаем, когда а < Доказано следующее утверждение.

Теорема 3.5.2. Пусть п оо, т оо, а < 1/2. Имеют место соотношения

к(п,т,а) ~ п2та

и(п,т, а) ~ п"та(2--

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

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

В разделе 4 рассматривается задача построения так называемых жжалыю-иолных тестов. В 4.1 обсуждаются истоки задачи. В 4.2 формулируются необходимые понятия и определения, постановка задачи. В 4.3 введены операции над тестами, благодаря которым выделены полезные рекуррентные соотношения (теорема 4.3.3, 4.3.4), из которых непосредственно следует метод построения теста. Мощность теста не превышает С(пг)(к^2 п)"1-1, где С(т) — константа, зависящая от ш, в то время как временная сложность — полиномиальна, что лучше известных методов.

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

Основные результаты работы опубликованы в:

1. Бородам С.Ю., Грунский И.С. Рекуррентное построение локально-полных тестов. //Кибернетикаи системный анализ". — 1992. — №4. — С.20-25.

2. Бородай С.Ю., Грунский И.С. Контроль одиночных неисправностей автомата при явно заданной функции неисправностей./ /Методы и системы техн.диагностики. Саратов: изд.СГУ. 1993.— Выи.18. — с.25.

3. Бородай С.Ю. Контроль одиночных неисправностей автомата с явно заданной функцией неисправностей.//Кибернетика и системный анализ". — 1995. — №6. — С.65-74.

4. Бородай С.Ю. Контроль одиночпых неисправностей автомата с заданной функцией неисправностей.//Методы и средства техн.диагностики: Сб.трудов XII Международной межвуз. конф., Ив.-Франковск, 1995. — c.GO.

5. Бородай С.Ю. Эксперименты с классами реализаций НД-автоматов//Тезисы II Укр.конф.по автоматическому управлению "Автоматика 95". Львов, 1995, т.З — с.101.

6. Бородай С.Ю. Условные и безусловные эксперименты с классами реализаций НД-автоматов //Тезисы докладов XI Международной конференции по проблемам теор. кибернетики /Под редакцией C.B. Яблонского. Ульяновск: изд. СВНЦ., 1996. — с.27.

Oi

у S ¡}<OU^ /