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

В процессе эксплуатации сложных технических систем неизбежно возникают неисправности, они связаны с материальной природой систем и, следовательно, изменением во времени, поэтому устранить вероятность появления дефекта принципиально нельзя. Однако можно предусмотреть своевременную амортизацию неполадок, то есть быстрое и достоверное обнаружение неисправностей и устранение их последствий. Организация восстановления поведения (ВП) сложной системы включает как обеспечение восстанавливаемости поведения объекта на этапе его проектирования, а также самодиагностирование и самовосстановление объекта в процессе функционирования, так и применение спектра восстановительных процедур, основанных на том или ином виде резервирования. Традиционные методы структурного восстановления поведения сохраняют изначальную преобразовательную форму поведения за счет подключения исправного дубля-резерва. Невозможность или нецелесообразность их реализации инициирует применение функционального восстановления, которое опирается на принцип обучения Я. З. Цыпкина [48] и переход к перечислительной форме представления текущего поведения. Математические модели сложных систем позволяют оценить поведение системы с двух точек зрения: если закон функционирования задан как отображение множества последовательностей входных сигналов в множество последовательностей выходных сигналов, то есть представляет собой преобразование некоторого множества, то говорят, что реализуется модель поведения в преобразовательной форме. Если закон функционирования задан как перечисление всех последовательностей входных сигналов индуцирующих данный выходной сигнал, то говорят о реализации модели поведения в перечислительной форме. Автоматы, реализующие эти две модели, называются автоматами-преобразователями и автоматами-перечислителями соответственно. В случае функционального ВП текущий закон функционирования выступает как «обучающаяся» система, которая после приложения специальных «обучающих» последовательностей должна генерировать сигналы, эквивалентные реакциям исправного поведения -" необученной" системы. В процессе «обучения» (функционального восстановления) происходит отход от точного соблюдения изначального преобразовательного соотношения между входными и выходными сигналами, хотя последние в точности совпадают с реакциями исправной технической системы. Анализ перехода от автоматов-преобразователей к автоматам-перечислителям и обратно позволяет выявить весь спектр функциональных особенностей поведения рассматриваемой системы. Вместе с тем, задача функционального ВП не сводится только к проблеме собственно восстановления поведения, в более общем ключе это задача приведения произвольного текущего поведения сложной системы (возможно, неисправного) к заданному виду. Формальная постановка задачи ВП была сделана A.A. Сытником и В. А. Твердохлебовым.

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

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

Исследованию общей теории автоматов, а также вопросов их возможного прикладного использования посвящено большое число работ отечественных и зарубежных специалистов: М. А. Айзерман и др. [2,3], М. Арбиб [4], Я. М. Барздинь, Б. А. Трахтенброт [6,45], А. М. Богомолов, Д. В. Сперанский [9], В. И. Варшавский [15,16], М. А. Гаврилов и др. [18], В. М. Глушков [20,21], А. Гилл [19], Н. Е. Кобринекий, Б. А. Трахтенброт [25], В. Б. Кудрявцев и др. [26], О. П. Кузнецов [27,28], В. Г. Лазарев, Е. И. Пийль [30], М. Минский, К. Шеннон, Дж. фон Нейман [1,33], В. А. Твердохлебов [44], Дж. Ульман [5,46], М. Л. Цетлин [47], С. В. Яблонский [49] и многие другие.

Способность математической модели поведения дискретной системы с памятью имитировать работу некоторого объекта рассматривается в рамках проблематики универсальных автоматов, являющейся одним из разделов общей теории автоматов. Её возникновение связано с появлением работ К. Шеннона, М. Минского, Дж. фон Неймана [1,33], наметивших основные направления исследований. М. Минский [1, стр.163] отмечает «.определенная категория множеств элементов „универсальна“ в том смысле, что из таких элементов можно собрать машины, реализующие произвольные. функции». В этой же работе [1,стр.177] элемент назван универсальным, если некоторое, достаточно большое множество объектов «обладает некоторыми подобными свойствами этого элемента или отличающимися лишь в количественном отношении». В. М. Глушков [20,стр.420] называет автомат универсальным, если «любой алгоритм может быть представлен в виде конечного набора выполняемых этим автоматом команд программ работы и фактически реализован им при условии игнорирования ограничений, накладываемых конечностью памяти автомата». В работах К. Шеннона [1,стр.214] и А. Тьюринга [1,стр.230] показана возможность построения машины Тьюринга универсальной в том смысле, что на ней можно выполнять любой вычисление. Универсальная машина воспроизводит работу частной, если «описание последней наносится на ленту универсальной машины по определенному коду, подобно начальной последовательности». Затем М. Дэвис [1] и Р. Петер [1] получили ряд условий, определяющих в явном виде метод построения команд универсальной машины Тьюринга. Обобщение универсальной вычисляющей машины с целью построения универсальной конструирующей машины рассматривалось Дж. фон Нейманом [33]. Универсальность машины заключалась, в её способности к самовоспроизведению, «.процесс начинается с одного экземпляра универсального конструктора и его описания, а заканчивается двумя экземплярами этого комплекса» [33,стр. И]. Фон Нейман впервые предсказал, что «.благодаря тесной связи задач саморемонта и самовоспроизведения результаты по самовоспроизведению «.могут решить проблему надежности, [33,стр.40]. Дальнейшие исследования понятия «универсальность» были посвящены уточнению и конкретизации указанных подходов на множествах нулевых функций и конечных детерминированных автоматов с последующей интерпретацией для комбинационных и последовательностных устройств. Достаточно условно можно выделить три основных направления в этих работах.

В рамках первого изучались проблемы использования универсальных элементов при синтезе и анализе систем искусственного интеллекта, способных к адаптации и обучению. Работы В. И. Варшавского [15], Я. М. Барздиня [6], М. Л. Цетлина [47] развивали идеи, высказанные Дж. фон Нейманом.

Изучение универсальных булевых функций и конечных автоматов проводилось Э. В. Евреиновым и И. В. Прангишвили [23], А. П. Горяшко [22], В. А. Мищенко [32], Э. А. Якубайтисом [50] и многими другими с целью построения универсальных и многофункциональных модулей. Превалирующей в этих работах была идея о достижении универсальности за счет перенастройки структуры технического объекта, что во многом близко концепции М. Минского. Прикладная значимость подобных результатов обусловлена их использованием в настоящее время при разработке отказоустойчивых систем, опирающихся на введение аппаратурной избыточности и допускающих проведение реконфигурационных мероприятии.

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

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

Цель работы состоит в представлении нового подхода к исследованию свойств, моделированию и восстановлению поведения сложной системы — через рассмотрение свойств ее специальным образом построенной числовой модели, в частности, через исследование моделирующей системы линейных алгебраических сравнений (СЛАС) и матрицы Вандермонда как матрицы коэффициентов СЛАС. Для достижения указанной цели поставлены и решены следующие задачи: построение числовой модели поведения по заданной автоматной модели (в качестве автоматной модели взят автомат Медведева) — анализ числовой модели и выявление ее связи с автоматной и полугрупповой моделями сложных системполучение метода выделения класса автоматов, допускающих числовое моделированиеоценка ранга матрицы Вандермонда и вспомогательных числовых функцийнахождение ранга матрицы Вандермонда для произвольного числа состояний автоматапостроение автомата Медведева по его числовой моделинахождение семейства моделей (и/или его представителей) по заданному автомату Медведева;

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

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

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

Основные результаты настоящей докладывались и обсуждались на конференции «Проблемы технической кибернетики» (Ульяновск, 1996), на конференциях «Интеллектуальные системы и компьютерные науки (МГУ, 1996, 1997), на конференции the First International Conference CASYS'97 on Computing Anticipatory SYStems (Liege, Belgium, 1997), на семинарах кафедры математической кибернетики (СГУ, 1997;2000), на семинарах кафедры теоретических основ информатики и информационных технологий (СГУ, 19 972 000).

Результаты работы опубликованы в 9 статьях автора.

Работа выполнена на 98 страницах машинописного текста, состоит из оглавления, введения, 3 глав и списка литературы.

В первой главе рассматривается формализация понятий системы, модели, задачи восстановления поведения и приводятся необходимые для изложения работы основные определения и используемые в работе леммы и теоремы из области теории автоматов, теории полугрупп и теории чисел. Далее в первой главе вводится понятие числовой модели. Числовая модель строится для автомата Медведева А-^^З) с некоторыми ограничениями на функцию переходов 3. Обозначив внутренние состояния автомата целыми числами от О до т-1, можно считать 5= {0,1,. , т-} = ОЬ (т) — множество состояний автомата Медведева — кольцом вычетов по модулю т. В этом кольце вычетов относительно операций сложения и умножения по модулю т для заданной функции переходов 3 строится семейство fxxex моделирующих степенных функций. В Лемме 1.4.1. доказывается связь между множеством моделирующих степенных функций {/х}хеХ и множеством (й)^ автоматных отображений автомата А, то есть взаимосвязь числовой и полугрупповой моделями. Далее в работе показана связь между числовой и полугрупповой моделями поведения автомата. Степенные функции, используемые в числовой модели, составляют полугруппу отображений, индекс и период которой однозначно определяют наибольшую возможную степень моделирующей функции, что доказывает теорема 1.4.1. Лемма 1.5.2. дает дополнительную оценку сверху старшей степени моделирующей функции. Далее в первой главе рассматривается возможность нахождения коэффициентов моделирующих функций. Матричное уравнение для нахождения коэффициентов, а именно матрица коэффициентов (матрица Вандермонда) и ее свойства, определяют основную теорему 1.5.2. о возможности моделирования поведения автомата и ее следствие о числовом моделировании автоматов с простым числом состояний.

Вторая глава полностью посвящена вопросу оценки и нахождения ранга матрицы Вандермонда, рассматриваемой над целочисленным кольцом. Для этого рассматривается три отдельных случая — случай простого модуля, модуля как степени простого числа и произвольного целочисленного модуля. Исследование матрицы Вандермонда проводится в предположении, что числовое моделирование возможно. Вторая глава содержит также описание преобразованного метода Гаусса и рекурсивный вывод формул преобразования элементов матрицы Вандермонда к итоговому треугольному виду. Леммы 2.2.1, 2.2.2 и 2.2.3 отражают свойства числовых функций, используемых для оценки ранга матрицы Вандермонда. Теоремы 2.2.1 и 2.2,2 определяют значение ранга матрицы Вандермонда в случае модуля, представляющего собой простое число в некоторой положительной степени и в случае произвольного модуля кольца вычетов.

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

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

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

Заключение

.

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

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

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

2. проведен анализ представленной числовой модели и выявлена ее связь с автоматной (на примере автомата Медведева) и полугрупповой (полугруппа преобразований конечного автомата) моделями сложных систем;

3. для построенной числовой модели получен метод выделения класса автоматов, допускающих числовое моделирование (так называемый, преобразованный метод Гаусса);

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

5. предложен способ построения числовой модели по заданной автоматной модели (автомат Медведева);