Введение к работе
Актуальность темы. Контроль и диагностика (расшифровка) автоматов являются старейшими, классическими и интенсивно изучающимися проблемами теории автоматов. Для конечных классов автоматов эти проблемы изучены достаточно полно в работах С.В.Яблонского, Э.Мура, М.П.Василевского, Я.М.Барздиня и многих других.
Для бесконечных классов изучение этих проблем находится в зачаточном состоянии. Их изучение связано с принципиальными трудностями (алгоритмическая неразрешимость в общем случае, отсутствие достаточно удобных моделей и т.п.). В последнее время ситуация изменилась в связи с появлением прикладных задач контроля и диагностики дискретных устройств на этапе их синтеза, когда задание на автомат осуществляется в виде спецификации на его заданное и запрещенное поведение. Эти спецификации задают бескопечные классы допустимых и запрещенных автоматов и требуется осуществить контроль результата синтеза на допустимость. Бесконечные классы автоматов возникают так же при контроле протоколов сети ЭВМ, при контроле компоненты сети автоматов (вычислений) и т.п. Такие классы изучались в работах А.Ф.Петренко, Н.В.Евтушенко, И.С.Грунского, И.И.Максименко, В.А.Твердохлебова, Д.В. Гавзова, В.В.Сапожникова, В.Вл.Сапожникова и др.
Данная диссертационная работа посвящена исследованию проблем контроля и диагностики в потенциально бесконечных классах конечных автоматов, эффективно заданных финитными средствами (частично-рекурсивными функциями, недетерминированными конечными автоматами, оценочными функциями). Такой подход достаточно адекватно отражает прикладные постановки. В силу сказанного, тема работы актуальна как в теоретическом, так и при-
4 —
кладном плане.
Цель работы состоит в разработке методов проведения экспериментов в возможно бесконечных конечно определенных классах автоматов, предназначенных для создания средств контроля распределенных систем на различных этапах их синтеза и эксплуатации.
Для достижения указанной цели поставлены и решены следующие задачи:
нахождение точных условий существования и нормальных форм алгоритмов проведения кратных условных экспериментов, восстанавливающих автомат из некоторого бесконечного класса, и экспериментов, различающих классы автоматов;
нахождение конструктивных точных условий существования, методов построения алгоритмов проведения экспериментов, различающих классы детерминированных реализации недетерминированных автоматов, оценок сложности таких экспериментов;
построение более простых, чем известные, тестов, проверяющих локальные неисправности дискретного устройства на уровне переходов автомата для моделей кратных и одиночных неисправностей, описанных недетерминированным автоматом, оценка сложности таких тестов.
Методы исследований, В работе использованы методы теории алгоритмов и рекурсивных функций, теории автоматов и графов. Автором, для решения поставленных задач, разработаны новые методы теории экспериментов с автоматами.
Новые научные результаты и положения, выносимые на защиту.
В работе впервые решены следующие задачи:
- получены точные (неконструктивные) условия существования
произвольных (частичных) и всюду-определенных алгоритмов
проведения восстанавливающих и (точно) различающих экспе-
— 5 —
риментов для бесконечных классов конечных автоматов;
получены нормальные формы таких алгоритмов, а именно: 1) показано, что итеративные алгоритмы Барздиня (основанные на стратегии наименьшей гипотезы) имеют те же восстанавливающие и различающие возможности, что и произвольные всюду-определенные алгоритмы и, следовательно, итеративные алгоритмы могут использоваться в качестве нормальной формы всюду-определенных; 2) перечисляющие алгоритмы (основанные па стратегии перебора гипотез) имеют те же восстанавливающие и различающие возможности, что и произвольные, а следовательно, могут использоваться в качестве их нормальной формы;
показано, что если для классов реализаций двух недетерминированных автоматов существует алгоритм проведения различающего эксперимента, то существует различающий алгоритм специального вида (задаваемый конечным автоматом) с минимальными (и конечными) значениями кратности и длины;
получены точные конструктивные условия существования алгоритмов проведения различающих экспериментов для классов реализаций двух недетерминированных автоматов,
предложен метод построения алгоритма проведения такого эксперимента (в виде конечного автомата) минимального по длине и кратности для случая, если он существует; на основе предложенного метода получены достижимые по порядку оценки параметров экспериментов, различающих классы реализаций;
найдены точные конструктивные условия, при которых автомат является различающим алгоритмом-экспериментатором для классов реализаций недетерминированных автоматов;
предложен метод построения более простого, чем известные, теста для детерминированного автомата, неисправности которого описаны недетерминированным автоматом (функцией неис-
— 6 —
правпостей), содержащим как переходы автомата-эталона, так и "подозреваемые" неисправные переходы;
впервые предложено совместное использование модели одиночных неисправностей переходов и функции неисправностей в виде недетерминированного автомата;
введена и исследована новая модель неисправностей автомата — одиночных неисправностей состояний;
получены не требующие моделирования неисправных автоматов методы построения более простых, чем известные, тестов, проверяющих одиночные неисправности переходов/состояний при заданной функции неисправностей; на основе предложенных методов найдены достижимые по порядку верхние оценки сложности тестов, проверяющих эти неисправности;
предложен метод построения так называемых локально-полных тестов, мощность которых в частных случаях минимальна по порядку.
Теоретическая и практическая ценность. В работе получен ряд нетривиальных окончательных результатов, имеющих теоретическое значение и позволяющих понять механизмы тестирования автоматов относительно конечно-определенных возможно бесконечных классов неисправностей. Полученные результаты могут быть использованы для контроля распределенных вычислительных систем, в частности сетей ЭВМ на различных этапах создания и эксплуатации.
Диссертация выполнена в течении 1993-96 гг. в соответствии с планами научно-исследовательских работ лаборатории прикладных проблем дискретной математики ИПММ НАН Украины "Исследование обратных задач теории автоматов применительно к идентификации и распознаванию дискретных систем", номер гос. регистрации 0194U022564; тема диссертации утверждена на заседании уче-
— 7 —
ного совета института (прот. N 1 от 14.01.1994).
Основные результаты получены автором самостоятельно и обсуждались с научными руководителями.
Апробация, Результаты работы докладывались и обсуждались на конференции "Методы и системы технической диагностики" (Саратов, 1993), II Украинской конференции по автоматическому управлению "Автоматика 95" (Львов, 1995), XII международной межвузовской конференции "Методы и средства технической диагностики" (Ивапо-Фрапковск,1995), XI международной конференции "Проблемы теоретической кибернетики" (Ульяновск, 1996), конференции "Интеллектуальные системы и компьютерные науки" (Москва, 1998), семинарах "Дискретпые системы и формальные языки" (ИПММ НАНУ, Донецк), семинарах в Саратовском государственном университете.
Публикации. По результатам работы опубликовано б работ. Две из них в соавторстве с научным руководителем, остальные — самостоятельно.
Структура и объем диссертации. Диссертация содержит 120 машинописных страниц, состоит из введения, четырех глав и списка литературы. Работа включает три таблицы.