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

со

сг

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

МЕЩЕРЯКОВА Ольга Викторовна

Методы синтеза и анализа некоторых классов автоматов-перечислителей

Специальность 01.01.09 - математическая кибернетика

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

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

Саратов - 1998

Работа выполнена на кафедре теоретических основ информатики и информационных технологий Саратовского государственного университета имени Н.Г.Чернышевского

Научный руководитель - Член-корреспондент РАЕН,

., доктор технических наук,

профессор Сытник А. А.

Официальные оппоненты - Член-корреспондент АТН Украины,

доктор технических наук, профессор Сперанский Д.В., кандидат физико-математических наук, доцент Кальянов Л.В.

Ведущая организация - Московский государственный

университет имени М.В.Ломоносова

/ (""¿г?

Защита состоится «» JUih.fi 1998г. в /-> час на заседании Диссертационного Совета К.063.74.04 при Саратовском государственном университете имени Н.Г.Чернышевского по адресу 410026, г.Саратов, 83, Саратовский государственный университет, механико-математический факультет.

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

Автореферат разослан «ЛО » ^/^Уи./; 1998г.

Ученый секретарь Диссертационного совета кандидат физико-математических наук доцент

Недорезов П.Ф.

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

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

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

Выход из строя (или отсутствие в силу сложностных, ценностных и прочих ограничений) структурного резервирования порождает вопрос: "Можно ли использовать свойства текущего закона функционирования автомата для формирования на выходах требуемой совокупности реакций?"

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

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

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

Идея предлагаемого подхода заключается в переходе при анализе поведения "неисправного" автомата от преобразовательной формы его представления к перечислительной.

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

Цель работы. Целью диссертационной работы является

1. Изучение свойств функциональной восстановимости некоторых собственных подклассов конечных детерминированных автоматов.

2. Разработка математических методов функционального восстановления поведения автоматов из заданного класса.

3. Описание класса автоматов, относительно которых заданный автомат функционально восстановим... , , г

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

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

{ОД}.

Описан класс&1ножество)конечных детерминированных автоматов, функционально восстановимых относительно класса инкрементарных автоматов.

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

Апробация работы и публикации. Основные результаты диссертации докладывались на П-ой Зимней школе по управлению вычислительными и контрольно-измерительными комплексами (Саратов, 1990), на VII Всесоюзном совещании по технической диагностике и отказоустойчивости (Саратов, 1990 г.), на Всесоюзной конференции «Актуальные проблемы прикладной математики» (Саратов, 1991), на школе молодых ученых по теории управляющих систем (Звенигород, 1990), на школе-семинаре «Проблемы теоретической кибернетики» (Москва, 1991), на семинаре «Интеллектуальные средства диагностирования РЭА» (Санкт-Петербург, 1991), на Всесоюзной конференции «Экспертные и обучающие системы»

(Саратов, 1992), на Международном научном семинаре «Экспертные и обучающие системы (ЭОС -95)» (Саратов, 1995), на XI Международной конференции по проблемам теоретической кибернетики (Ульяновск, 1996), на семинарах в Московском и Саратовском университетах. По теме диссертации опубликовано 7 работ.

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения и списка литературы (63 наименования). Объем работы -105 страниц машинописного текста.

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

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

Определение. Пусть даны конечные автоматы А=(8,Х,У,5,А,) и В=(8,11,У,6В1А.В). Будем говорить, что автомат В перечисляет автомат А, если

(V хе X) (Зр еЯ*) (V зе в ) Цз,х) = рг|р| 7ф,р), а слово р назовем перечисляющей последовательностью.

Определение. Пусть дан конечный автомат А=(8,Х,У,5,Х,). Автомат В = (8,Х,У,5В,А.В) с теми же множествами входных символов и и состояний назовем неустойчивой копией автомата А (неустойчивым относительно автомата А), если существует входной символ X; е X, которому соответствует выходная реакция, отличная от выходной реакции заданного автомата А, то есть,

(З^е Х)(3 б е Б) Цзд) Ф

Определение. Пусть даны конечный детерминированный автомат А=(8,Х,У,5Д) и семейство его неустойчивых копий А!=(8,Х,У,5;Л|), \ е1. Функционирование автомата А;, при котором возможно перечисление поведения исходного автомата А, назовем функционированием в защищенном режиме.

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

Задача синтеза. Пусть задан конечный детерминированный автомат А=($,Ха,У,5Д) и семейство его неустойчивых копий А,=(8,ХЬУ,5|,^), I е1. Необходимо для любого номера 1 е1 и любого входного слова г е ХА построить такое слово р е X"., что

О^еБ) Я(к,г) = рг!р, ^р).

Задача анализа. Дан автомат А=(8,ХЛ,УДА,). Необходимо найти семейство таких автоматов А;=(8,Х|,У,8|Д!), что для любого номера 1 е1 и любого слова г е ХЛ существовало слово р е X!, такое, что

(V ее Б) глХг) = рг,р| \(в,р).

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

Теорема 1.3.2. Задача построения автомата-перечислителя для произвольного множества неустойчивых автоматов алгоритмически неразрешима.

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

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

Рассмотрим автомат A=(S,X,Y,5,A.). Будем предполагать, что Y=S, то есть реакцией автомата является его внутреннее состояние и в дальнейшем без ограничения на общность рассуждений будем исследовать автомат такого типа.

Пусть автомат А = (S,X,5), где S = {s„s2,...,sn}, Х={х1,х2,...х1} - множества состояний и входных символов, п, leZ (Z - множество целых чисел).

Определение. Пусть А = (S,X,5) - конечный детерминированный автомат, для которого S = {si,...,sn}, Х={х„х2,-..,х,}. Закон функционирования описывается функцией

8(s,Xj) = ms+X; (mod n), (1)

где m e Z, u = IS |. Назовем поведение, реализованное функцией вида (1), инкрементарным, а автомат, осуществляющий инкрементарное поведение, инкрементарным автоматом, или I-автоматом. Поскольку поведение инк-рементарного автомата в аналитической форме характеризуется параметрами шип, будем обозначать в дальнейшем эти автоматы (т,п)-1-авто-ма-ты, где m -некоторое целое число, я - мощность множества состояний.

Рассмотрим конечный детерминированный автомат А = (S,X,S), где

S = {s,,s2.....s„}, X = {0,1}. Будем предполагать, что состояния автомата А

представляют собой k-значные числа в двоичной системе счисления, они могут быть занумерованы как s = 0,1,..., 2Ы. Тогда инкрементарное поведение этого автомата реализовано функциями 5](s,0) = 2s (mod 2k)

62(s,l) - 2s+l (mod 2k) (2)

Обозначим через множество инкрементарных автоматов

{А | | б! =2к, Х={0,1},}. Содержательно, этот класс включает в себя автоматы, для которых осуществляется последовательный ввод символов из алфавита {0,1} и "увеличение" по модулю 2к значения состояния. Иначе говоря, - это множество (2,2к)-1-автоматов, поведение которых описывается функциями вида (2).

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

Лемма 2.2.3. Для любого автомата из множества ^ преобразования, индуцированные входными символами 0,1 изоморфны.

Лемма 2.2.4. Семейство преобразований 1-автоматов из множества образуют группу на множестве классов эквивалентности относительно операции сложения.

Обозначим через {5Х}, х еХ, семейство преобразования инкремен-тарного автомата. В общем случае это семейство образует полугруппу преобразований.

Одним из хорошо изученных базисов в полугруппе является базис В={П8>Ь}.

Ф0= х - 1 (тос! 2к)

х,х = 0,1,...,п-3 п-1,х = п-2 п-2,х=п-1

[х, х = 0,...,п-3 . Ь(х) = „ 1 ___1 >гдеп=2 •

[п-1,х = п-2& х = п-1

Предположим, что полугруппа Од= {8х},х е X исходного 1-автомата

содержится в полугруппе Б. = {5Х }, X; е неустойчивого автомата.

1 '

Это означает, что любой элемент этих групп может быть получен из эле-

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

Иными словами, речь идет о необходимости определения разложения произвольного автоматного преобразования из Бд через составляющие Б д .

Представление каждого преобразования через функции базиса В в

а а

общем случае записывается в виде у 1 у 2..., где у е {Г,з}.

Существенно упростить это выражение позволяют свойства функций

1) (х) = ^х-а+1) = х - а, а=0,1,...

к е [х-1, к -гетно

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

5(х) = в(...^(х-а,)-...)-ак)-ак+1, (3)

где а^-.а^, - целые положительные числа, х еХ.

С содержательной точки зрения запись вида (3) означает, что автоматное преобразование 5 получается из элементов базиса В за число шагов к + +а, + а2 + ... + ак+).

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

представления каждого преобразования из D д в данном базисе В и най-

i

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

ный базис. Однако, существует выражение, содержащее минимальное число вхождений функции g. Такое представление для конкретного преобразования 5j е D д будем называть g-минимальным, а число вхождений g i

обозначим с(5) и назовем степенью преобразования 5.

Таким образом, исходную задачу взаимовыразимости преобразований

в группе D д можно разбить на две задачи: i

1. По заданному преобразованию 5 найти его степень с(5).

2. Зная степень с(5) для преобразования 8, найти коэффициенты а,,а2,...ак+1 в представлении (3).

Рассмотрим вначале вторую задачу. Пусть дано преобразование 5 и его степень с(5) (наименьшая):

S(x)= g(...(g(x-a,)-...)-ak)-ak+,. Для решения этого уравнения используется метод итерационного вло-жения. По существу он представляет собой аналог грамматического разбора "сверху-вниз". В параграфе 2 второй главы предложен алгоритм, который позволяет находить коэффициенты а,,а2,...а1(+1>задающих каноническое представление преобразования 8(х) и строить множество перечисляющих последовательностей вида

а а а

р = 0 1 1 0 2 ... 10 к + 'для входного символа 0.

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

а„ а, а

р = 0 0 1 0 1 1 ... 1 0 р.

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

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

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

Рассматривается 1-автомат А={8,Х,5}, для каждого элемента порождающего множества {б,^} автомата А определяется при помощи алгоритма построения классов е-эквивалентности, предложенный А.А.Сытни-ком, соответствующий класс эквивалентности К(Д). Без ограничений на общность рассуждений можно считать, что они различны, то есть все элементы порождающего множества неэквивалентны. На множестве автоматных преобразований определим операцию

Ес- (ВКЗХб) I (Ухе X.) (3 хе X) 5Х = К(5Х) },гдесе N.

Положим Е = ив для всех натуральных значений параметра с и для с

функций переходов-выходов автомата А={8,Х,5} и дадим определите расширения ЛТ]М(А) инкрементарного автомата А.

Определение. Под расширением инкрементарного автомата А (обозначим А"Ш(А)) будем понимать множество автоматов, для которых выполняется утверждение

{Ак}к 6, с АТЫ(А)« (V В е{Ак} к6,) (3 с е Ы) В = Ее(А).

Утверждение 3.2.1. Для того чтобы задача анализа математической модели поведения в защищенном режиме функционирования автомата А была разрешима относительно семейства неустойчивых автоматов {Ак}ке1, необходимо и достаточно, чтобы для каждого автомата Ак семейства I существовало такое натуральное число с, при котором выполняется равенство Ак е ЕС(А).

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

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

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

В параграфе 3 сформулирован критерий перехода инкрементарного автомата в защищенный режим функционирования.

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

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

Для описания механизма «сжатия» информации в теории автоматов используется аппарат так называемых (8,Х)- гомоморфных образов, введенный и разработанный В.М.Глушковым Эти объекты представляют собой копии автомата, одновременно уменьшенные по двум параметрам: множеству входных символов X и множеству внутренних состояний-выходных символов 8. Принципиально важной особенностью является способность гомоморфных образов сохранять в процессе подобного «сжатия» определенный «слепок» информации об исходном автомате.

Определение. Пусть заданы два йнкремёнтарных автомата

А = (Б, Ха,5а) и В = (й, Х„,8В) {8а}, {5в} - автоматные преобразования, заданные на множестве состояний-выходных символов Б. Автомат В назовем (8,Х) - гомоморфным образом автомата А, если существует отображение ср: Б х ХА -> вх Хв, называемое (Б,Х)-гомоморфизмом, такое, что справедливо условие

(У5 €8) (Ух е ХА ) рг 1ф (8Л(з,х)) = 8В (ф (в,х)) &(8А(з,х)) = бв (Ф (з,х)).

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

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

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

Из утверждения теоремы вытекает ряд следствий.

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

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

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

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

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

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

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

Автор выражает глубокую признательность научному руководителю член-корреспонденту РАЕН, доктору технических наук, профессору Сытнику Александру Александровичу за постановку задачи и постоянное внимание к работе.

1. Волосивец С.С., Мещерякова О.В. О е-приближениях некоторых аналитических и дифференцируемых функциях // Межвузовский сборник научных трудов. Актуальные проблемы фундаментальной математики. Москва. Изд-во МФТИ. 1997. с.79-84.

2. Мещерякова О.В. Восстановление правильного функционирования линейных автоматов// Методы и системы технической диагностики. Вып.18. Саратов., 1993. с.124-125.

3. Сытник Л.Л., Мещерякова О.В. Автомат как модель базы данных /Методы и системы технической диагностики.Вып.11.Саратов1989.87-88с.

4. Сытник A.A., Мещерякова О.В. Программная реализация процедур самовосстановления поведения конечных автоматов //Материалы Всесоюзной конференции «Актуальные проблемы прикладной математики» Саратов, 1991 Часть 3. с.319

5. Сытник A.A., Мещерякова О.В. Восстановление конечно-автоматных преобразований // Методы и системы технической диагностики .Вып 16. Саратов, 1992. с. 48-56.

6. Сытник A.A., Мещерякова О.В. Об одном методе восстановления правильного функционирования сдвигового регистра // Искусственный интеллект. Теория и приложения Вып.2. Саратов 1995, с 8-11.

7. Сытник A.A. Мещерякова О.В., Посохина Н.И. Об одном подходе к синтезу самовосстанавливающихся автоматов // Тезисы докладов на XI Международной конференции по проблемам теоретической кибернетики, Ульяновск, 1996. с. 188-189.