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

Посохина, Наталия Игоревна

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

Посохина, Наталия Игоревна АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Саратов МЕСТО ЗАЩИТЫ

2000 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

Диссертация по математике на тему «Задачи синтеза и анализа перечислителей в некоторых классах конечных автоматов»

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

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

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

РГБ ОД

ПОСОХИНА Наталия Игоревна ~ 3 ГЛДР

л,

1Я ЯГ г. и и и

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

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

САРАТОВ-2000

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

Научный руководитель:

Официальные оппоненты:

академик РАЕН, доктор технических наук, профессор А. А. СЬ1ТНИК

доктор технических наук, член-корреспондент АТН Украины, профессор Д.В. СПЕРАНСКИЙ,

кандидат физико-математических наук, доцент Л.В. КАЛЬЯНОВ

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

Защита диссертации состоится «^З» 2000 г. в

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

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

Автореферат разослан «¿¿51 ^ ^¿¡¿¿¿¿¿^ 2000 г.

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

2 ¡6 ъ /У, о

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

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

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

Рассматриваемое множество I вариантов поведения сложной системы представлено множеством математических моделей поведения Г = {y,}t€l ■ Множество П средств преобразования поведения сложной системы определено как множество отображений {©Л«^ ввда oüy.T' Г', где r'=rUf для некоторых

дополнительных вариантов поведения Г, порожденных действиями средств преобразования поведения на Г. Правила F расшифровки преобразованных вариантов поведения сложной системы заданы отображением gF вида gF : Р(Г') -> Г. Для заданных эталонного (требуемого) варианта поведения у0 еГ и подмножества вариантов поведения Г0 (Г0 порождается учитываемым классом неисправностей сложной системы) требуется найти такое преобразование о еС1, для которого выполняется условие: gf.(«(ro,)) = {/0}.

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

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

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

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

команд, программ работы и фактически реализован им при условии игнорирования ограничений, накладываемых конечностью памяти автомата". В работах К.Шеннона и А.Тьюринга показана возможность построения машины Тьюринга универсальной в том смысле, что на ней можно выполнять любые вычисления. Универсальная машина воспроизводит работу частной, если "описание последней наносится на ленту универсальной машины по определенному коду, подобно начальной последовательности". Затем М Дэвис и Р.Петер получили ряд условий, определяющих в явном виде метод построения команд универсальной машины Тьюринга. Обобщение универсальной вычисляющей машины с целью построения универсальной конструирующей машины рассматривалось Дж.фон Нейманом. Универсальность машинь» заключалась, в её способности к самовоспроизведению, "...процесс начинается с одного! экземпляра универсального конструктора и его описания, а заканчивается двумя экземплярами этого комплекса". Фон Нейман впервые предсказал, что "...благодаря тесной связи задач саморемонта и самовоспроизведения результаты по самовоспроизведению могут решить проблему надежности". Дальнейшие исследования понятия "универсальность" были посвящены уточнению и конкретизации указанных подходов на множествах нулевых функций и конечных детерминированных автоматов с последующей интерпретацией для комбинационных и последовательностных устройств. Достаточно условно можно выделить три основных направления в этих работах.

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

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

Достаточно долго вне рамок активных исследований

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

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

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

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

получение метода выделения класса автоматов, допускающих числовое моделирование;

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

нахождение ранга матрицы Вандермонда для произвольного числа состояний автомата;

построение автомата Медведева по его числовой модели; нахождение семейства моделей (и/или его представителей) по заданному автомату Медведева;

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

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

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

дан метод выделения класса автоматов, допускающих числовое моделирование;

дана схема построения автомата Медведева по его числовой модели;

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

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

Публикации. Основные результаты работы содержатся в 9 статьях

автора, список которых приведен в конце автореферата.

Объем и структура работы. Работа выполнена на 98 страницах

машинописного текста, состоит из оглавления, введения, 3 глав,

списка литературы и приложения. Библиография состоит из 51

названия.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Пусть дан автомат Медведева A=(S,X,S). Обозначим внутренние состояния автомата целыми числами от 0 до от-1, тогда Л-{О, 1, ... ,m-l}=GL(m), то есть S совпадает с полугруппой вычетов по модулю т.

При фиксированном хеХ функцию переходов S данного автомата можно считать обобщенной подстановкой вида:

/о 1) ... »-Л

^о - Vi/.

Относительно множества степенных функций {fx\xcx, построенных для данной S можно утверждать следующее: Лемма 1.4.1. Множество степенных функций {fx}xex моделирует поведение автомата А в том смысле, что всякое его автоматное отображение g из {gsbes может быть представлено в виде КОМПОЗИЦИИ функций ИЗ {fxlxsX-

Моделирование степенными функциями допускают только такие автоматы, что для любого входного сигнала хеХ, 5, может бьггь представлена степенной функцией /ч с фиксированными коэффициентами из {0, 1, ... ,/я-1} вида: fx(s) - аа +a15 + a2s2+...+ais'(modw),s sS

Функции s\ s2, ..s1} составляют полуфуппу

отображений с так называемой константой s° = 1 (mod т). Ее подполугруппа {х1, s2, ..., s'} является периодической полугруппой, порождаемой s. По определению, индекс полугруппы - это наименьшее целое положительное число г0 такое, что sr° = sr,+n для некоторого п, период полугруппы - это наименьшее положительное число то из всех возможных п. Данным г0 и то соответствует единственная (с точностью до изоморфизма) полугруппа преобразований {s,si,...s'i+mo"1} • В полугруппе векторов умножение определяется покомпонентно, поэтому все /-тые компоненты вееторов полугруппы образуют подполугруппу полугруппы чисел {0,1,...т-1}, порожденную числом ;. Следовательно, говоря! о связи между индексами и периодами векторной и покомпонентной полугрупп, надо учитывать,, что период векторной полугруппы должен содержать все периоды покомпонентных полугрупп, а значит, должен являться их наименьшим общим кратным. Индекс векторной полугруппы

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

Теорема 1.4.1. Пусть т =1а'}р\а^{>1аг--ркак " разложение числа т на простые множители, ао ¿о,а1 >о,у = ]Д . Тогда индекс и период полугруппы преобразований вычисляются по

формулам:

Лемсма 1.5.2. Для старшей степени / справедлива следующая оценка сверху: / <т-1.

Однако найденное таким образом число / не является наибольшей степенью многочлена, а всего лишь ее верхней оценкой. Говоря о том, что начиная с некоторого числа г0 степенные функции будут циклически повторяться, мы имели в виду тождественность функций 5Г°+' = /0+т°"(тас1»|)> > 0, а для рассмотрения базиса множества нам необходима еще и их взаимная

линейная независимость.

Коэффициенты степенной функции находят,

подставляя в последовательно числа 0,1,...,/л-1 и приравнивая полученные результаты числам из соответствующей

обобщенной подстановки. В результате получается система линейных сравнений по модулю т (в матричном виде): 1 1 ... 1 2 22 ... 2'

(тя-1) Ои-1)2 ... (т-1)' Матрица слева есть ни что иное как матрица Вандермонда,

Г 1 II ... 1 1 2 22 ... 2'

(т-1) (т-1)2 ... (т-1)' где в качестве переменных взяты константы 1,...,/я-1. Теорема 1.5.2. Поведение автомата А можно моделировать множеством степенных функций {/х}хсх в том и только том случае, когда ранг расширенной матрицы [Аф] равен рангу матрицы М и каждые элемент столбца свободных членов кратен наибольшему общему делителю всех элементов соответствующей строки

5, У0

X а2 = 52 — (тос!/и)

матрицы М

Следствие. Если число т - простое, то моделирующее множество степенных функций {fx\xex можно построить для произвольного автомата А (то есть поведение всех автоматов с простым числом состояний моделируется подходящим набором степенных функций).

Число линейно независимых столбцов представляет собой число степенных функций, которые могут быть использованы в разложении, но ранг матрицы одновременно с этим является и числом линейно независимых строк. По столбцам матрицы расположены значения степенных функций s, s2, .J на наборе (1,2,...т- li)T. По строкам матрицы расположены элементы а, а2, ...а' полугруппы (а), порожденной элементом а, где а последовательно принимает значения 1,2,...от-1. В терминах линейной независимости столбцов^ совпадение ранга матрицы с числом / означает, что при моделировании используются все функции а при ранге,

меньшем / часть функций может не использоваться, и соответствующие им коэффициенты а, при решении матричного уравнения Ma = 7 (mod т) являются свободными переменными. При применении к матрице Вандермонда, вычисляемой по простому модулю, прямого хода преобразованного метода Гаусса получены следующие формулы для итоговой треугольной матрицы:

/-2 а-1 V-Г1 : ,,

ЛГ'-' g=ljp=k-p-\ J К,1 — 1,1

О, к < i

При рассмотрении простейшего случая составного модуля т=ра, полугруппа {0, 1, ...,ра-1} является объединением полугруппы с идемпотентом 1 (своей приведенной полугруппы) и полугруппы с идемпотентом 0, состоящей из всех кратных р чисел. Приведенная полугруппа содержит <р(ра)-ра-ра'х чисел, а остальные риЛ чисел принадлежат примитивному идемпогенту 0 или ра. Каждая строка матрицы М представляет собой элементы полугруппы по умножению,

порожденной первым элементом строк», расположенные в строке в порядке их порождения. При этом, для оценки ранга матрицы строятся вспомогательные числовые функции. Строка {кр") имеет вид; {кр"): кр", ¡¿р2", ..., 0,..., 0. Число кр", принадлежащее идемпотенту 0, порождает полугруппу <*р"НАр", (кр")2, ..., (крп)г, ..., (кр")т+г'1}, здесь г - индекс полугруппы {кр"), а /я - ее период. Тогда длина строки, порожденной {кр") - это индекс полугруппы {кр"), уменьшенный на единицу ¡}=г-1. Оценим величину /?. Используя стандартное алгебраическое обозначение [У1 для наименьшего целого, большего или равного х, получим

-1.

г =

\а и а

1» п

Число попарно различных значений

записано как

к«)=2>|

а а

к — 1 I

15 п < а -1, может быть ГО, х = 0

Фактически, характеристическая функция % в данном случае

определяет, содержит ли промежуток

а а

к'к-1

хотя бы одно целое

число, а \(а) - число промежутков, содержащих целые числа, на интервале [1,а). Так как длина строки - это величина /?, то попарно различных длин строк будет также в точности Ца), причем эти длины принимают значения от 1 до а -1 включительно. Оценим количество строк вида {кр"), имеющих одну и ту же длину. Лемма 2.2.1. Справедлива следующая оценка сверху: у(а) < 24а-1 ■ Лемма 2.2.2. В матрице М всего (р (рй") строк вида {кр"), (к,р)=\, \<п<а-\.

При этом строки, порожденные элементами с различной кратностью п

вхождения элемента р могут иметь одну и ту же длину Д

Лемма 2.2.3. Всего строк одной и той же длины Д в матрице М будет:

п= №

или

и=1

1=/»+1

№ = Т<р(рап) = р

№

-г?

/>+ч I р

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

indp

случае, для произвольного s-того шага метода Гаусса: т^={арУ , далее, V л > 3 mf =ар'(а-1 -1)

причем /иш(,) = а(а-1)...(йг-j +l)ps, и система условий обнуления строки:

если существует i такое, что п = х (mod <р(р° '* "'1)) и существует с* такое, что выполняется кр"л- х = рс* (mod/?в"'*"лИ), где х е {1, .. .s -1}, тогда для всякого / > / в строке <(Ар") кратности п все элементы, начиная с i -того на данном шаге преобразования методом Гаусса становятся нулевыми, и если при этом с > a-s - п +1, то в нуль обращаются все строки кратности п (так как при i* = s, то есть при с' > a- s - п -И, вся преобразуемая строка кратности л становится нулевой и исключается из дальнейшего рассмотрения). Если же существует/ такое,что Vi

Я-iycUs-jr1 = cc-n-i* +\ (mod (р(ра~"~'*х))> то все Vj=l )

элементы, стоящие на / -той позиции строки кратности п останутся неизменными. Помимо этого, все преобразуемые на данном шаге строки кратности п = а - s +1 обнуляются и исключаются из рассмотрения.

Теорема 2.2.1. При сведении двух матриц Л/0) и

суммарный ранг

(то есть число линейно независимых векторов) для модуля р" меньше

или равен (]>а-1).

Рассматривая случай сложного модуля т =2а°pf1^"2... Рк°к >

оказывается, что матрицы вида Л/1', порождаются только

примитивными идемпотентами, остальным идемпотентам не

принадлежат никакие другие элементы, отличные от них самих. Более

того, ранг матрицы Вандермонда в случае сложного модуля

т =2а°pi"lp2a2- ■■ Ркак равен наибольшему из чисел (р,аг1).

Тем самым, справедлива следующая теорема:

Теорема 2.2.2. Ранг матрицы Вандермонда определяется формулами

rang = шах (да, -1), а0 = 0, max а, < 3. \<1<к 1<;<и

rang < max (да, -1), аа Ф О, и» остальных случаях. О<i<k '

Третья глава посвящена приложению числовой модели в области теории автоматов. В первом параграфе приводится алгоритм

построения числовой модели автомата по заданному автомату. Второй параграф рассматривает преобразование числовой модели при исследовании поведение автомата на входном слове а = хххг..х„, оно

будет задаваться словарной функцией fm коэффициенты которой вычисляются алгебраическим путем как

/„(*) = «о + (тоёти) = /г (/х (.../(л)))(тойт)-

П П-1 ' 1

Пусть а = аЪ, /л($) = а0 /ь(5) =Ь0 н-^лч-.-.+Ь^'. Тогда

коэффициенты/а будут вычисляться по формулам:

.а к = О,...,I2

А.....

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

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

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

Список работ, в которых содержатся основные результаты диссертации:

1. Сытник А.А., Мещерякова О.В., Посохина Н И. "Об одном подходе к синтезу самовосстановления автоматов" //Проблемы теоретической кибернетики. Материалы XI Международной конференции 10-14 июня 1996 г. М. рос.гос. гуманит. университет

1996, 226 с.

2. Посохина Н.И., Шульга Т.Э. "Об одном подходе к построению автомата-перечислителя" //Методы кибернетики и информационные технологии, /под ред. Д.С.Черешкина.- Саратов: ГосУНЦ "Колледж",

1997. Вып. 2., с.

3. Посохина Н.И. "Об одном подходе к решению задачи синтеза автоматов-перечислителей" //Теоретические проблемы информатики и ее приложений. /Саратов: ГосУНЦ "Колледж", 1997. Вып.1, с. 101109.

4. Sytnik A.A., PosohinaN.I. "On Some Methods Of Discret Systems/'t Behaviour Simulation" //The materials of The First International / Conference CASYS'97 on Computing Anticipatory SYStems, Liege, / Belgium, 1997, p. 97-104.

5. Сытник А.А., Посохина Н.И. "Об одном подходе к восстановлению поведения автоматов" // Материалы международной конференции "Новые информационные технологии в науке, образовании, телекоммуникациях и бизнесе". Часть 2.1998. с 306.

6. Посохина Н.И., Абашкин А.В. "Некоторые свойства степенных функций, моделирующих поведение КДА" //Теоретические проблемы информатики и ее приложений. /Саратов: ГосУНЦ "Колледж", 1998. Вып.2, стр.3-8

7. Сытник А.А., Посохина Н.И., Шульга Т.Э. "Об одном подходе к решению задачи синтеза автоматов-перечислителей" //Теоретические проблемы информатики и ее приложений. /Саратов: ГосУНЦ "Колледж", 1998. Вып.2, стр. 103-116.

8. Сытник А. А., Посохина Н.И. "Об одном подходе к восстановлению поведения конечных детерминированных автоматов" //Известия РАЕН серия МММИУ, том 3, 1999, номер 1, стр.91-99.

9. Посохина Н.И. «О свойствах моделирующей матрицы» // Теоретические проблемы информатики и ее приложений. /Саратов: ГосУНЦ "Колледж", 1999. Вып.З.

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Посохина, Наталия Игоревна

Введение

ГЛАВА 1. Математические модели поведения дискретных систем

§ 1 Моделирование и восстановление поведения сложных систем: некоторые методологические аспекты

§ 2 Содержательная постановка задачи восстановления поведения сложной системы

§ 3 Математический аппарат, используемый при моделировании и восстановлении поведения

1.3.1. Основные определения

1.3.1.1. Элементы теории полугрупп

1.3.1.2. Элементы теории автоматов

1.3.1.3. Элементы теории чисел

§ 4 Введение числовой модели конечного детерминированного автомата

1.4.1. Числовая модель

1.4.2. Исследование полугруппы преобразований

§ 5 Нахождение коэффициентов моделирующих функций

ГЛАВА 2. Оценка ранга матрицы Вандермонда, рассматриваемой над целочисленным кольцом

§ 1. Матрица Вандермонда в кольце вычислений по простому модулю

§ 2 Ранг матрицы Вандермонда в случае простейшего составного модуля и свойства некоторых целочисленных функций

Введение диссертация по математике, на тему "Задачи синтеза и анализа перечислителей в некоторых классах конечных автоматов"

В процессе эксплуатации сложных технических систем неизбежно возникают неисправности, они связаны с материальной природой систем и, следовательно, изменением во времени, поэтому устранить вероятность появления дефекта принципиально нельзя. Однако можно предусмотреть своевременную амортизацию неполадок, то есть быстрое и достоверное обнаружение неисправностей и устранение их последствий. Организация восстановления поведения (ВП) сложной системы включает как обеспечение восстанавливаемости поведения объекта на этапе его проектирования, а также самодиагностирование и самовосстановление объекта в процессе функционирования, так и применение спектра восстановительных процедур, основанных на том или ином виде резервирования. Традиционные методы структурного восстановления поведения сохраняют изначальную преобразовательную форму поведения за счет подключения исправного дубля-резерва. Невозможность или нецелесообразность их реализации инициирует применение функционального восстановления, которое опирается на принцип обучения Я.З.Цыпкина [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), на семинарах кафедры теоретических основ информатики и информационных технологий (СГУ, 19972000).

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

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

В первой главе рассматривается формализация понятий системы, модели, задачи восстановления поведения и приводятся необходимые для изложения работы основные определения и используемые в работе леммы и теоремы из области теории автоматов, теории полугрупп и теории чисел. Далее в первой главе вводится понятие числовой модели. Числовая модель строится для автомата Медведева А-^^З) с некоторыми ограничениями на функцию переходов 3. Обозначив внутренние состояния автомата целыми числами от О до т-1, можно считать 5= {0,1, . , т-\} = ОЬ(т) - множество состояний автомата Медведева - кольцом вычетов по модулю т. В этом кольце вычетов относительно операций сложения и умножения по модулю т для заданной функции переходов 3 строится семейство \fx\xex моделирующих степенных функций. В Лемме 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. предложен способ построения числовой модели по заданной автоматной модели (автомат Медведева);

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Посохина, Наталия Игоревна, Саратов

1. Автоматы. Сборник статей под ред. К.Шеннона. М.: Иностранная литература, 1956. - 403с.

2. Айзерман М.А., Алескеров Ф.Т. Выбор вариантов. Основы теории. -М.: Наука, 1990. 236с.

3. Айзерман М.А. и др. Логика. Автоматы. Алгоритмы. М.: Физматгиз, 1963. - 140с.

4. Арбиб М. Алгебраическая теория автоматов, языков, полугрупп. М.: Статистика, 1975. - 335с.

5. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. М.: Мир, 1978. - 4.1. - 612с.

6. Бардзинь Я.М., Калниньш Я.Я. Универсальный автомат с переменной структурой//Автоматика и вычислительная техника, 1974. №2. С.9-18

7. Богомолов A.M. и др. Эксперименты с автоматами. Киев: Наукова Думка, 1973. - 144с.

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

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

10. Богомолов А.М., Сытник A.A. Универсальные конечные автоматы// Доклады АН СССР. 1987. Т. 294. - №3. - С.525-528.

11. Богомолов С. А. О восстановлении автомата по экспериментам// Дискретная математика, 1989. -Т.1. -Вып.1. С. 135-146

12. Боревич З.И., Шафаревич И.Р. Теория чисел. М.: Наука, 1985. - 451с.

13. Бурбаки Н. Алгебра. (Многочлены и поля. Упорядоченные группы) -М.: Наука, 1965. 300с.

14. Вагнер В.В. Теория полугрупп и ее приложение. Саратов: Изд-во СГУ, 1965,-С.3-179.

15. Варшавский В.И. Коллективное поведение автоматов. М.: Наука, 1973. - 407с.

16. Варшавский В.И. Апериодические автоматы. -М.: Наука, 1976. 424с.

17. Виноградов И.М. Основы теории чисел. М.: Наука, 1981. - 176с.

18. Гаврилов М.А., Девятков В.В., Пупырев В.И. Логическое проектирование дискретных автоматов. М.: Наука, 1977. - 352с.

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

20. Глушков В.М. Синтез цифровых автоматов. М.: Физматгиз, 1962. -476с.

21. Глушков В.М. Абстрактная теория автоматов// Успехи мат. наук, 1961. Т. 14. - Вып. 5. - С.3-62.

22. Горяшко А.П. Логические схемы и реальные ограничения. М.: Энергия, 1982. - 184с.

23. Евреинов Э.В., Прангишвили И.В. Цифровые автоматы с настраиваемой структурой. М.: Энергия, 1974. - 240с.

24. Клир Дж. Системология. М.: Радио и связь, 1990. - 539с.

25. Кобринский Н.Е., Трахтенброт Б.А. Введение в теорию конечных автоматов. М.: Физматгиз, 1962. - 404с.

26. Кудрявцев В.Б. и др. Введение в теорию автоматов. М.: Наука, 1985. -319с.

27. Кузнецов О.П. Сети из языков// Автоматика и телемеханика, 1980. -№6. -С.152-161.

28. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. М.: Энергоатомиздат, 1989. - 328с.

29. Курош А.Г. Курс высшей алгебры М.: Наука, 1975. - 345с.

30. Лазарев В.Г., Пийль Е.И. Синтез управляющих автоматов. М.: Энергоатомиздат, 1989. - 328с.

31. Мальцев А.И. Алгоритмы и рекурсивные функции. М.: Наука, 1986. -368с.

32. Многофункциональные автоматы и элементная база цифровых ЭВМ (под ред. В.А.Мшценко) М.: Радио и связь, 1981. - 240с.

33. Нейман Дж. Теория самовоспроизводящихся автоматов. М.: Мир, 1971. - 382с.

34. Паризек Б., Шварц С. О мультипликативной полугруппе классов вычетов по модулю mil РЖ "Математика". 1960. - №4. - 3826. - С.26.

35. Поеохина Н.И., Шульга Т.Э. Об одном подходе к построению автомата-перечислителя// Методы кибернетики и информационные технологии, (под ред. Д.С.Черешкина)- Саратов: ГосУНЦ "Колледж", 1997. Вып. 2. С.113-115.

36. Поеохина Н.И. Об одном подходе к решению задачи синтеза автоматов-перечислителей// Теоретические проблемы информатики и ее приложений. -Саратов: ГосУНЦ "Колледж", 1997. Вып.1 - С. 101-109.

37. Поеохина Н.И., Абашкин A.B. Некоторые свойства степенных функций, моделирующих поведение КДА// Теоретические проблемы информатики и ее приложений. Саратов: ГосУНЦ "Колледж", 1998. - Вып.2. -С.3-8.

38. Поеохина Н.И. О свойствах моделирующей матрицы// Теоретические проблемы информатики и ее приложений. Саратов: ГосУНЦ "Колледж", 1999. - Вып.З. - С.97-102.

39. Сытник A.A. Восстановление поведения сложных систем. Саратов: Изд. СГУ, 1992. - 192с.

40. Сытник A.A., Мещерякова О.В., Поеохина Н.И. Об одном подходе к синтезу самовосстановления автоматов// Проблемы теоретической кибернетики. Материалы XI Международной конференции 10-14 июня 1996 г. -М.: рос. гос. гуманит. университет 1996. 226с.

41. Сытник A.A., Посохина Н.И. Об одном подходе к восстановлению поведения автоматов// Материалы международной конференции "Новые информационные технологии в науке, образовании, телекоммуникациях и бизнесе", 1998. Ч. 2. - С.306.

42. Сытник A.A., Посохина Н.И. Об одном подходе к восстановлению поведения конечных детерминированных автоматов// Известия РАЕН серия МММИУ, 1999. Т. 3. - №1. - С.91-99.

43. Сытник A.A., Посохина Н.И., Шульга Т.Э. Об одном подходе к решению задачи синтеза автоматов-перечислителей// Теоретические проблемы информатики и ее приложений. Саратов: ГосУНЦ "Колледж", 1998. - Вып.2. -С.103-116.

44. Твердохлебов В.А. Логические эксперименты с автоматами. Саратов: Изд-во СГУ, 1988. - 184с.

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

46. Ульман Дж. Вычислительные аспекты СБИС.-М.: Радио и связь, 1990.-480с.

47. Цетлин M.JI. Исследования по теории автоматов и моделированию биологических объектов. -М.: Наука, 1969. 317с.

48. Цыпкин Я.З. Адаптация и обучение в автоматических системах. М.: Наука, 1968. - 399с.

49. Яблонский C.B. Введение в дискретную математику.-М.: Наука, 1979. -272с.

50. Якубайтис Э.А. Логические автоматы и микромодули. Рига: Зинатне, 1975. - 260с.