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

• Кунявская, Анна Наумовна
• кандидат физико-математических наук
• 2004

Оглавление диссертации кандидат физико-математических наук Кунявская, Анна Наумовна

Введение.

Глава 1. Классификация конечных детерминированных автоматов и алгебра композиции автоматов

1.1. Классификация конечных автоматов по свойствам комбинационных частей.

1.2. Алгебра композиции автоматов.

1.3. Свойства классов автоматов, как свойства их комбинационных компонент.

Глава 2. Установочная задача для автоматов, метод распознавания автомата с зацикливанием изменений состояний

2.1. Необходимое и достаточное условие существования решения установочной задачи.

2.2. Функционирование автомата с изменениями состояний в циклах.

2.3. Математическая модель процесс зацикливания автомата.

Глава 3. Метод решения установочной задачи на основе изменений состояний в цикле

3.1. Матричный метод построения решения установочной задачи.

3.2. Теорема о связи решения установочной задачи для модели зацикливания автомата.

3.3. Метод построения циклов графа GP.

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

4.1. Множество конституэнт единицы комбинационной части автомата и пары автоматов.

4.2. Граф, определяющий совмещение конституэнт единицы в функциях переходов и выходов автоматов.

4.3. Достаточные условия для распознавания автоматов методом зацикливания.

Введение диссертации (часть автореферата) на тему «Распознавание конечных детерминированных автоматов методом зацикливания»

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

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

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

А = (S, X, Y, S, Я), где S, X и Y - соответственно множества состояний, входных и выходных сигналов, а 5 и А, функции переходов 5: S х X —> S и выходов Л: S х X —> S, заменялась структурной формой, то есть, композицией преобразователей сигналов и элементов памяти.

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

У= (s,x) = (s, х) s'eS

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

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

В качестве средства разделения множества состояний автомата на подмножества используется приложение периодических последовательностей входных сигналов. Как показано A.M. Богомоловым и В.А. Твердохлебовым в работе [11], в этом случае возникает циклическое изменение состояний. Состояния, не вошедшие в циклы, можно исключить из анализа и оставить для анализа только те состояния, которые вошли в циклы.

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

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

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

В первой главе диссертации расширяется классификация конечных детерминированных автоматов на основании учета специфических свойств комбинационных частей автоматов. Для этого рассматривается представление комбинационной части наборами функций алгебры логики ос = (fi, f2, . , fni) и Р = (hj, h2, . , hn3). Кодирование элементов множества состояний S двоичными векторами размерности п} , множества входных сигналов X двоичными векторами размерности п2 и множества выходных сигналов Y двоичными векторами размерности п3 позволяет представить комбинационную часть набором функции алгебры логики вида: fl fa, %2> ••■ j % п2 , Z}, Z2, ■■■ , Z„i) h} (xj, X2, . , x n2 , Z], z2, . , Zni)

Кз (Xl, X2, ■■■, X n2 , Z], z2, ■■■ , Zni)

Принимаемая классификация построена на классификации функций fi, 1 < i < П[, hj, 1 < j < п3, по их принадлежности классам Поста: К0 (функции сохраняющие 0), К} (функции сохраняющие 1), KL (линейные функции), Кт (монотонные функции), Ks (самодвойственные функции). В качестве памяти автомата рассматривается набор из П] элементов задержки сигнала на один такт. Здесь же рассматривается наличие сочетаний свойств, то есть принадлежность функций алгебры логики классам вида j Т т s > где а имеет значение а, если класс определяется наличием у функции свойства а, и значение а , если функции класса не имеют свойства а.

В приложении 1, связанным с этой главой диссертации, содержится явное перечисление некоторых классов автоматов.

Задание конечного детерминированного автомата в виде трех множеств S, X, Y и двух функций 8 : S х X S , Л : S х X —> S удобно для теоретического рассмотрения законов функционирования автомата с использованием свойств функций и множеств. Такого представления автомата оказывается недостаточным для решения задач, связанных с анализом структуры технической (биологической, экономической, производственной и т.п.) системы, в качестве математической модели, которой используется автоматом.

Техническая система и, в частности, дискретные устройства управления (см. С.В. Яблонский [66], В.М. Глушков [26] ) создается на основе композиции элементов логического типа и элементов памяти. В первой главе диссертации приводятся правила правильной композиции элементов и новое, предлагаемое рассмотрение связей элемента с другими элементами в структуре автомата.

В качестве основных свойств положения отдельного элемента в структуре выбраны:

- управляемость входом элемента (вход элемента является внешним входным узлом автомата);

- наблюдаемость выхода элемента.

В соответствии с этим разработана алгебра композиции автоматов и построена классификация типов размещения элементов в структуре автомата. Предлагаются следующие операции:

- операция изолированного раздвоения узла,

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

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

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

- теорема 10 о существовании точно одного в классе (2, 2, 2)-автоматов сильносвязного, самодвойственного и сохраняющего 0 автомата,

- теорема 11 о длине синхронизирующей последовательности для сильносвязного, самодвойственного и сохраняющего 0 автомата (из класса (2, 2, 2)-автоматов), теорема 12 о частном случае эквивалентности свойств сохранять О и сохранять 1.

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

Во второй главе диссертации рассматривается установочная задача для автомата, условие существования ее решения и сведение задачи распознавания автомата к установочной задаче. Основные результаты получены Э.Муром [1 ] иА.Гиллом [23].

В теореме 13 уточняется представление о процессе решения установочной задачи и разделяются два способа уменьшения множества распознаваемых состояний:

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

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

Основное содержание второй главы диссертации составляет изложение основных положений метода распознавания автомата (в заданном семействе автоматов), базирующихся на приложении периодической последовательности выходных сигналов. В работе A.M. Богомолова и В.А. Твердохлебова ([11], теорема 23) показано, что функционирование конечного детерминированного автомата под воздействием периодической входной последовательности с любым периодом р е X и рассмотрением связей состояний s и 8 (s, р), s е S , определяется конечным графом с циклами и деревьями, корни которых являются вершинами циклов.

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

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

При изменении состояний в цикле рассматривается возможность наблюдения при изменении состояний в цикле:

- выходных сигналов вида Л (s, pri р) Л(д (s, pr, а р), pr\p\ р ), то есть, первого или последнего выходного сигнала для каждого периода р и состояния s, принадлежащего циклу;

- выходного слова Л (s, р) для каждого состояния s цикла и отдельного периода р,

- некоторых выходных сигналов слова Л (s, р).

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

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

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

- принадлежность всех состояний автомата циклам при зацикливании одной и той же компоненте связности,

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

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

- наличие циклов в виде петель (циклов длины 1) и циклов длины К.

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

Для того, чтобы распознавание автомата методом зацикливания сделать содержательно понятным, в параграфе 3.2 все основные формальные понятия и построения иллюстрируются на примере. Для этого задаются три автомата А] , А2 , и А3 , выбираются периоды р} , р2 и р3 и строятся математические модели процессов зацикливания. На рис. 18-26 приведены соответствующие графы, показан выбор наблюдаемых выходных последовательностей и рассмотрены функции переходов и выходов конечного детерминированного автомата, представляющего пределы зацикливания.

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

В четвертой главе диссертации разрабатывается метод зацикливания, в котором получили развитие основные положения, изложенные в предыдущих главах. В качестве распознаваемых автоматов рассматриваются автоматы с nj двоичными задержками (2nl состояниями), множеством входных сигналов и множеством (Е2) "3 выходных сигналов, то есть, автоматы вида А = ((Е2) , (Е2) *2, (Е2) щ , 8, X ). Функции 8 и 1 оказываются представленными соответственно наборами (fh f2, . . . fnj) и (hj, h2, . . . hn3) функций алгебры логики, каждая из которых зависит от nl + п2 двоичных переменных.

Задача распознавания автомата, без потери общности, ограничивается распознаванием автомата в паре автоматов (A j , Л2). Для этого автоматы представляются наборами функций (fn.fn, ■ ■ - Ли) и (hn, h2i, . . . hn3i) , /= 1,2 , и исследуются условия неравенства функций. Анализируемые функции gi и g2 заменяются их совершенными дизъюнктивными нормальными формами, в которых знаки « V» заменяются знаками «©»

2 Г сложения по mod 2). Суммы конституэнт единицы g и g^ совмещаются в

I SI сумму gi © g . Каждая конституэнта, входящая в сумму g^ © g^, является конституэнтой В СДНФ ТОЛЬКО ДЛЯ ОДНОЙ ИЗ функций g; ИЛИ (лемма 3).

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

Основные положения иллюстрируются примером для конкретного (заданного диаграммой Мура на рис. 30) автомата. В теореме 17 содержится представление суммы © формулой, аналогичной формуле разложения функций по переменным в логическом базисе < &,v, >.

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

В первом достаточном условии (теорема 18) основными свойствами являются:

- существование в множестве {fju © .} цилиндрического (по координатам, соответствующим кодам состояний) подмножества,

- зацикливание по единственному циклу,

- нечетная длина цикла.

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

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

Теорема 20 обобщает теоремы 18 и 19 на случай наблюдения выходных сигналов на всех выходных каналах автомата.

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

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Кунявская, Анна Наумовна

Заключение

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

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

2. Решена установочная задача для автоматов с зацикливанием. Для чего построена и исследована математическая модель процесса зацикливания автомата. Изучено функционирование автомата с изменениями состояний в циклах. Получены необходимое и достаточное условие существования решения установочной задачи в исследуемом классе автоматов (с зацикливанием).

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

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

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

Основные публикации

1. Кунявская А.Н. Об одном подходе к классификации конечных автоматов по свойствам комбинационных компонент. Деп. в ВИНИТИ. 16.10. 2002 года. № 1763-В2002. 31 с.

2. Кунявская А.Н Решение установочных задач конечных автоматов экспериментом с зацикливанием состояний./ /Межвузовский сборник научных трудов. Теоретические проблемы информатики и ее приложений-Вып.5.- Саратов.-Изд-во Сарат. ун-та. 2002 г.

3. Сытник А.А., Креницкий А.П., Кунявская А.Н Об одном подходе к исследованию дискретных систем с изменяемым поведением./ /Межвузовский сборник научных трудов. Теоретические проблемы информатики и ее приложений - Вып.4.- Саратов.- ГосУНЦ «Колледж».-2001 г. С. 120-125.

4. Сытник А.А., Кунявская А.Н., Рзун И.Г. Об одном подходе к распознаванию автомата с изменениями состояний в циклах. / /Межвузовский сборник научных трудов. Теоретические проблемы информатики и ее приложений - Вып.5.- Саратов.- Изд-во Сарат. ун-та. 2002 г.

5. Сытник А.А., Шульга Т.Э., Кунявская А.Н. Анализ и синтез универсального автомата-перечислителя. //Тезисы докладов Международной конференции «Компьютерные науки и информационные технологии». Саратов. 2002 г.С. 70-71.

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

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

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

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

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

5. Баранов С.И. Цифровые устройства на программируемых БИС с матричной структурой. М. Радио и связь. 1986. 270 с.

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

7. Бахтурин Ю.А. Основные структуры современной алгебры. М. Наука. 1990.318 с.

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

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

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

11. П.Богомолов A.M., Твердохлебов В.А. Диагностика сложных систем. Киев. Наукова Думка. 1974. 128 с.

12. Богомолов A.M., Твердохлебов В.А. Целенаправленное поведение автоматов. Киев. Наукова Думка. 1975. 123 с.

13. Брауэр В. Введение в теорию конечных автоматов. М. Радио и связь. 1987. 392 с.

14. Буевич В.А. Построение универсальной о.-д. функции с двумя переменными. //Проблемы кибернетики. 1965. N 15. С. 249-252.

15. Бурбаки Н. Теория множеств. М. Мир. 1965. 455 с.

16. Бусленко Н.П. Моделирование сложных систем. М. Наука. 1978. 399 с.

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

18. Ван дер Варден Б.Л. Алгебра. М. Наука. 1979. 623 с.

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

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

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

22. Геллер С.И., Журавлев Ю.И. Основы логического проектирования цифровых вычислительных машин. М. Сов. радио. 1969 272 с.

23. Гилл А. Введение в теорию конечных автоматов. М. Наука. 1966. 272 с.

24. Гороховский С.С., Рысцов И.К. Об изоморфизме графов отображений. //Кибернетика. 1982. N 6. С. 45-52.

25. Горяшко А.П. Логические схемы и реальные ограничения. М. Энергоиздат. 1982. 184 с.

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

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

28. Глушков В.М., Капитонова Ю. В., Летичевский А.А. Теоретические основы проектирования дискретных систем. //Кибернетика. 1977. N 6. С. 5-20.

29. Глушков В.Г., Цейтлин Г.Е., Ющенко Е.Л. Алгебра, язаки, программирование. Киев. Наукова Думка. 1974. 328 с.

30. Горбатов В.А. Основы дискретной математики. М. Высшая школа. 1986.311 с.

31. Дроздов Е.А. Оптимизация структур цифровых автоматов. М. Сов. радио. 1975. 352 с.

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

33. Заде JI. Общая теория систем. М. Мир. 1966.

34. Закревский А.Д. Алгоритмы синтеза дискретных автоматов. М. Наука. 1971.512 с.

35. Зыков А.А. Основы теории графов. М. Наука. 1987. 381 с.

36. Капитонова Ю.В. Об изоморфизме абстрактных автоматов. //Кибернетика. 1965. N 4,5.

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

38. Кратко М.И. Алгоритмическая неразрешимость проблемы полноты для конечных автоматов. //Доклады АН СССР. 1964. Т. 155. N 1. С. 35-37.

39. Кунявская А.Н. Об одном подходе к классификации конечных автоматов по свойствам комбинационных компонент. Деп. в ВИНИТИ. 16.10. 2002 года. № 1763-В2002. 31 с.

40. Кунявская А.Н Решение установочных задач конечных автоматов экспериментом с зацикливанием состояний. / /Межвузовский сборник научных трудов. Теоретические проблемы информатики и ее приложений Вып.5.- Саратов.- Изд-во Сарат ун-та. 2002 г.

41. Кудрявцев В.Б., Алешин С.В., Подколзин А.С. Введение в теорию автоматов. М. Наука. 1985. 319 с.

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

43. Мелихов А.Н. и др. Применение графов для проектирования дискретных устройств. М. Наука. 1974. 294 с.

44. Месарович М., Такахара Я. Общая теория систем: математические основы. М. Мир. 1978. 256 с.

45. Многофункциональные автоматы и элементная база цифровых ЭВМ.//Под ред. В.А. Мищенко. М. Радио и связь. 1981. 240 с.

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

47. Пархоменко П.П. О технической диагностике. М. Знание. 1969. 64 с.

48. Пикар С. О базисах симметрической группы.//Кибернетический сборник. 1965. Вып. 1. с. 7- 34.

49. Поспелов Д.А. Логические методы анализа и синтеза схем. М. Энергия. 1974. 368 с.

50. Сытник А.А. Перечислимость при восстановлении поведения автоматов. //Доклады РАН N 328 N 1.1993.

51. Сытник А.А. Восстановление поведения сложных систем. Саратов. Изд- во Сарат. ун-та. 1992. 192 с.

52. Сытник А.А. Методы и модели восстановления поведения автоматов. //Автоматика и телемеханика. 1992. N11.

53. Сытник А.А., Кунявская А.Н., Рзун И.Г. Об одном подходе к распознаванию автомата с изменениями состояний в циклах. / /Межвузовский сборник научных трудов. Теоретические проблемы информатики и ее приложений Вып.5.- Саратов.- Изд-во Сарат ун-та.2002 г.

54. Сытник А.А., Шульга Т.Э., Кунявская А.Н. Анализ и синтез универсального автомата-перечислителя. //Тезисы докладов Международной конференции «Компьютерные науки и информационные технологии». Саратов. 2002 г.С. 70-71.

55. Твердохлебов В.А. Логические эксперименты с автоматами. Саратов. Изд- во Сарат. ун- та. 1988. 184.Трахтенброт Б.А., Барздинь Я.М. Конечные автоматы. Поведение и синтез. М. Наука. 1970. 400 с.

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

57. Ушаков И.А. Построение высоконадежных систем. М. Энергия. 1974. 64 с.

58. Феррари Д. Оценка производительности вычислительных систем. М. Мир. 1981. 376 с.

59. Фридман А., Меннон П. Теория и проектирование переключательных схем. М. Мир. 1978. 580 с.

60. Харари Ф. Теория графов. М. Мир. 1973. 300 с.

61. Цетлин М.Л. Исследования по теории автоматов и моделированию биологических объектов. М. Наука. 1969. 317 с.

62. Цифровая вычислительная техника. //Под ред. Э.В. Евреинова. М. Радио и связь. 1991. 464 с.

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

64. Яблонский С.В. Введение в дискретную математику. М. Наука. 1979. 272 с.

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