Модели и методы анализа, интерполяции и распознавания автоматов

Епифанов, Антон Сергеевич

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

Епифанов, Антон Сергеевич АВТОР

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

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

2011 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

Диссертация по математике на тему «Модели и методы анализа, интерполяции и распознавания автоматов»

Автореферат диссертации на тему "Модели и методы анализа, интерполяции и распознавания автоматов"

Епифанов Антон Сергеевич

Модели и методы анализа, интерполяции и распознавания автоматов

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

АВТОРЕФЕРАТ

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

Саратов - 2011

О з МАР 2011

4856577

Работа выполнена в Институте проблем точной механики и управления РАН (г.Саратов)

Защита диссертации состоится «17» марта 20II г. в 17 часов 00 мин. на заседании диссертационного совета ДМ 212.243.15 при Саратовском государственном университете им.Н.Г.Чернышевского по адресу: 410012, г.Саратов, ул.Астраханская, 83, СГУ, механико-математический факультет.

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

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

доктор технических наук, профессор Твердохлебов Владимир Александрович

Официальные оппоненты: доктор физико-математических наук,

доцент Андрейченко Дмитрий Константинович

кандидат физико-математических наук, доцент Богомолов Сергей Анатольевич

Ведущая организация:

Институт проблем управления РАН (г.Москва)

Автореферат разослан « > февраля 2011 г.

Ученый секретарь

диссертационного совета,

кандидат физико-математических наук, доцент

В В. Корнев

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

Актуальность темы. Теория автоматов как один из разделов математической кибернетики нашла применение в технике (синтез технических систем, техническое диагностирование), в информатике (построение компиляторов, тестирование программ), в медицине и др. Формирование и развитие теория автоматов получила, например, в работах Дж.Неймана [12], В.М.Глушкова [6-7], В.Б.Кудрявцева и др. [10], М.И.Кратко [9], М.А.Айзермана [1] и др. Фундаментальным направлением в теории автоматов явилась теория экспериментов с автоматами (работы Э.Мура [11], А.Гилла [5]). Основа для использования моделей и методов дискретной математики в теории автоматов изложена, например, в работах С.В.Яблонского [14] и сборнике [8]. Исследования по теории автоматов проводились в Саратовско-Донецкой Школе, возглавлявшейся А.М.Богомоловым ([2-4]), в которую входили Д.В.Сперанский, В.Н.Салий, Ю.А.Скобцов, В.Г.Скобелев, А.А.Сытник, И.С.Грунский, В.ЛТвердохлебов и др.

Анализ распространения основных положений, моделей и методов теории автоматов на область сложных систем при использовании традиционных средств задания автоматов (таблицами, матрицами, графами, логическими уравнениями, формулами языка регулярных выражений) показал, что требуется добавить новые средства, согласующиеся с возросшей размерностью автоматных моделей и неполнотой их представления, а также для устранения барьера между дискретными символьными и числовыми математическими структурами. Представления числовыми математическими структурами законов функционирования автоматов позволяет, во - первых, в ряде случаев преодолевать барьер размерности данных в моделях, а, во-вторых, принципиально расширить формальный аппарат теории автоматов на основе включения в него развитых числовых структур и методов геометрии. В 19951996гг. В.А. Твердохлебовым [13] был предложен новый подход к заданию законов функционирования конечных детерминированных автоматов - задание геометрическими образами, при котором автоматное отображение представляется в формах символьного и числового графиков. Это позволяет использовать для задания законов функционирования автоматов геометрические кривые, с расположенными на них точками автоматных-

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

Основные результаты диссертации получены с участием автора при выполнении исследований по планам НИР Института проблем точной механики и управления РАН: "Разработка методов и моделей для управления и технического диагностирования мехатронных систем (2007г., № гос. регистрации - 0120.0 502444)", " Разработка основных положений моделей и методов описания законов функционирования сложных технических систем в форме причинно-следственных комплексов взаимодействий разнородных процессов (2008-2010г.г., № гос. регистрации - 0120. 0 803005)" и по грантам РФФИ " Разработка моделей и методов для технического диагностирования больших систем с использованием автоматных моделей и интерполяции по числовым геометрическим образам законов функционирования объекта диагностирования (2007-2008гх, №07-07-00088а)" и "Разработка методов технического диагностирования сложных систем с учётом интервалов времени, на которых законы функционирования систем не определены или невозможно применение средств диагностирования (2008-2009г.г., №08-08-00534)" .

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

Задача 1. Исследовать возможность методов интерполяции Ньютона, Лагранжа, Гаусса, Бесселя, Стерлинга и др. для законов функционирования

автоматов, частично заданных геометрическими образами.

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

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

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

- последовательностями вторых координат точек геометрических образов автоматов;

- последовательностями точек на аналитически заданных кривых, интерпретируемых как вершины геометрических образов;

- классом (4,2,2)-автоматов и его подклассами, определенными по свойствам Поста.

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

Научная новизна. Основные результаты диссертации являются новыми и впервые получены автором:

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

2. Получены оценки для сравнения по точности интерполяции методами Ньютона, Лагранжа и др. для частично заданных законов функционирования автоматов, последовательности вторых координат вершин геометрических образов которых определены числовыми последовательностями из массива The

On-Line Encyclopedia of Integer Sequences™ (OEIS™(CIIIA)). Получены оценки для автоматов с частично заданными геометрическими образами, представляющими класс (4,2,2}-автоматов д его подклассы и класс линейных (8,2,2)-автоматов.

3. Разработаны метод и алгоритм распознавания таких автоматов, законы функционирования которых заданы геометрическими образами, расположенными на аналитически заданных геометрических кривых: у=е<*-5-5\

y = l + cos(—+1.75), >' = l — I , У=1—~—I И Др.

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

- вершины геометрических образов которых расположены на аналитически заданных геометрических кривых, содержащихся в банке ENCYCLOPÉDIE DES FORMES MATHÉMATIQUES REMARQUABLES (Фракция);

- по последовательностям Вторых координат вершин геометрических образов (включая оценку последовательностей длины 1 млн.знаков из массива OEIS™(CUIA)) ;

-для законов функционирования автоматов из класса (4,2,2)-автоматов и его подклассов.

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

Апробация работы: Основные результаты работы докладывались и обсуждались на 2-ой школе-семинаре молодых ученых «Управление большими системами», (г.Воронеж, 9-12 июля 2007г.), Международной научной конференции "Гарантоспособные системы, сервисы и технологии DESSERT-2007" (г.Кировоград, Украина, 24-27 апреля 2007г.), Международной научной конференции «Автоматизация проектирования дискретных систем» (г.Минск, Белоруссия, Объединенный Институт проблем информатики НАН Беларуси, 14

-15 ноября 2007г.), Международной научной конференции "Гарантоспособные системы, сервисы и технологии DESSERT-2008" (г.Кировоград, Украина, 23-26 апреля 2008г.), Международной научной конференции "Информационные технологии и системы ИТиС'08" (г.Геленджик, 29 сентября - 3 октября 2008г.),

5-ой школе-семинаре молодых ученых «Управление большими системами» (г.Липецк, 21-24 октября 2008г.), Второй (1-3 октября 2008г) и Третьей (5-7 октября 2009г.) Международных научных конференциях "Управление развитием крупномасштабных систем" (г.Москва, Институт проблем управления РАН) , Международной научной конференции «Математические методы в технике и технологиях ММТТ-22» (г.Псков, 25 - 30 мая 2008г.), Международной научной конференции "Гарантоспособные системы, сервисы и технологии DESSERT-2009" (г.Кировоград, Украина , 22-25 апреля 2009г.), Международной научной конференции «Дискретные модели в теории управляющих систем» (г.Москва, МГУ им.М.В.Ломоносова, факультет ВМК,

6—9 апреля, 2009г.), на 7-ой молодежной научной школе по дискретной математике и ее приложениям (г.Москва, Институт прикладной математики им.МВ.Кслдыша РАН, 18-23 мая 2009г.), 6-ой школе-семинаре молодых ученых «Управление большими системами» (г.Ижевск, Удмуртский государственный университет, 31 августа - 5 сентября 2009г.), Международной научной конференции «Мехатроника, автоматизация, управление (МАУ-2009)» (п.Дивноморское, 28 сентября - 3 октября 2009г.), на 10-ом Международном семинаре «Дискретная математика и ее приложения», (г.Москва, МГУ, механико-математический факультет, 1-5 февраля 2010г.), Международной научной конференции "Гарантоспособные системы, сервисы и технологии DESSERT-2010" (г.Кировоград, Украина , 11-15 мая 2010г.), на Седьмой Международной научно-практической конференции "Теоретические и прикладные аспекты построения программных систем" (Украина, г.Киев, Киевский Национальный Университет им.Т.Шевченко, факультет кибернетики, 4-8 октября 2010).

Публикации. Основные результаты диссертации опубликованы в 20 печатных работах [А1-А20] (включая монографию [A3]), список которых приведен в конце автореферата. Статьи [А1,А2] опубликованы в изданиях, содержащихся в Перечне ведущих рецензируемых научных журналов и изданий, рекомендованных ВАК.

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, списка литературы и приложения. Общий объем диссертации 142 страницы, включая 16 рисунков, список литературы и приложение. Библиография содержит 93 наименования.

ОБЗОР СОДЕРЖАНИЯ ДИССЕРТАЦИИ

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

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

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

Глава 2 также содержит результаты оценки точности интерполяции методами Ньютона и Лагранжа частично заданных законов функционирования автоматов, представляющих класс (4,2,2)-автоматов и его подклассы, класс линейных (8,2,2)-автоматов. Кроме этого рассмотрена интерполяция частично заданных законов функционирования автоматов, которые определены последовательностями вторых координат точек геометрических образов.

Оценка точности интерполяции проведена для начальных отрезков длины

до 1 млн. знаков в приближенных представлениях величин из массива Н1 при новом выборе узлов интерполяции, что привело к разработке двух методов интерполяции ( метод 1 и метод 2).

Исследованные инициальные автоматы вида Ач =(S, X, Y, б, X, s0), где S, X и Y - множества состояний, входных и выходных сигналов, 5 и X - функции переходов и выходов вида b:S*X S, X:S*X Y, a s0eS - начальное состояние, представлены классами автоматов: классами (п, т, I) - автоматов, где п~ |S|, т = |Х|, I = |Y| , и классами (и, т, /)а начальных отрезков геометрических образов длины d, определяющих автоматы из класса (п, т, /) -автоматов. (Геометрическим образом инициального автомата ASf =(S, X, Y, 5, X, s0) называется автоматное отображение

р = U {(p,X(sc,p))}, дважды линейно упорядоченное введением линейного

'0 р«х'

порядка o>i на множестве X* и линейного порядка со2 на Y.) Геометрический образ автомата представляется точками символьного графика G| , расположенного в системе координат с осью абсцисс (X*, M[) и осью ординат (Y, Юг). График G] преобразуется в график G2 точек с числовыми координатами, в котором каждая пара (р,у) е р^ графика Gi заменена парой (п(р), г2(у)), где г,(р) и г2(у) - номера р и у по порядкам сох и т2 и р|о получено из р^ заменой вторых координат пар последним знаком последовательности X(s0,p). Числовая форма G2 геометрического образа автомата изоморфно вкладывается в первый квадрант прямоугольной декартовой системы координат на плоскости, что позволяет исследовать методы интерполяции частично заданных геометрических образов классическими методами интерполяции. В диссертации проведен сравнительный анализ точности интерполяции методами Ньютона и Лагранжа, а также модифицированными методами Ньютона и Лагранжа. Модификация методов интерполяции состоит в том, что узлами интерполяции являются точки геометрических образов автономных подавтоматов вида A0=(S, {0}, Y, So, Яо, So)

1 МассивНсостоитю 10 величии: с, я, m = i—— (золотоесечение), \2 , V2 , 1п(2), 1л(10),

v 2

С(3)= Ё—, , константы Каталана Q- —, константа Эйлера у = lim(I + —+ - + ... + --1л(л)).

х "-о(2п + 1) 2 3 п

и А)=(5, {1}, У, 5ь X], Бо). Введем для сравнения эффективности интерполяции двух методов интерполяции в заданном классе автоматов функцию, числовые показатели которой имеют интерпретацию как показатели эффективности

методов интерполяции: рК.п'.п? ) = 1 - , где п' (п^) - число

шах(п ^п^ + п,

автоматов, для которых методом а (методом Р) восстановлено больше точек, чем методом р (чем методом а ), а п" - число автоматов, для которых совпадает число правильно восстановленных точек методом а и методом Р , при условии п^ + п^ + п" * 0. В диссертации исследованы методы интерполяции Ньютона (К) и Лагранжа (Ь), а функция получения оценок эффективности интерполяции имеет вид

- -где

тздп а ,пл) + п4

Функция ) использована для получения оценок

эффективности интерполяции методами Ньютона и Лагранжа в классе (4,2,2)-автоматов и его подклассах, выделенных свойствами Поста, а также в классе линейных (8,2,2)-автоматов. В классах автоматов получены оценки, характеризующие эффективность методов интерполяции в зависимости от длины геометрических образов автоматов. Значения функции Р = О интерпретируются как равная эффективность обоих методов интерполяции. При Р=1 только один из методов интерполяции правильно восстанавливает некоторые точки геометрических образов 'автоматов из рассматриваемого класса автоматов. Значение п,где 0<п <1 , функции Б интерпретируется как числовой показатель величины эффективности одного из методов. Следующие теоремы содержат оценки эффективности интерполяции для указанных выше классов автоматов методами Ньютона и Лагранжа.

Теорема 2.1.1. Пусть узлами интерполяции для геометрического образа длины с! каждого автомата А=(8, {0,1}, У, 5, А, Бо) из класса инициальных (4,2,2)-автоматов являются точки геометрических образов автономных подавтоматов А0=(8, {0}, У, бо , Ао, во) и А1=(5, {1}, У, 5] , А[, Бо) автомата А. Тогда для методов интерполяции Ньютона и Лагранжа при <1=30 в классе инициальных (4,2,2) - автоматов выполняется отношение > и функция Р принимает значение р(п^, п^, п^ ) = 0,65 (метод интерполяции Ньютона с оценкой 0,65 точнее метода Лагранжа).

Теорема 2.1.2. Пусть узлами интерполяции для геометрического образа длины (1 каждого автомата А=(8, {0,1}, У, 5, X, во) из класса инициальных (4,2,2)-автоматов являются точки геометрических образов автономных подавтоматов Ао={8, {0}, У, 8о, Хо, б0) и А]=(8, {1}, У, 61 , Хь Бо)

автомата А . Тогда для методов интерполяции Ньютона и Лагранжа при d=62 в классе инициальных (4,2,2) - автоматов выполняется отношение п" > л, и функция Р принимает значение Р(п6ы2,п^,п" )=0,44 (метод интерполяции Ньютона с оценкой 0,44 точнее метода Лагранжа).

Теорема 2.1.3. Пусть узлами интерполяции для геометрического образа длины <1 каждого автомата А=(8, {0,1}, У, 8, X, Бо) из класса инициальных (4,2,2)-автоматов являются точки геометрических образов автономных подавтоматов Ао=(8, {0}, У, 50, Хо, эо) и А) =(8, {1}, У, 5, , Хь во)

автомата А . Тогда для методов интерполяции Ньютона и Лагранжа при <1=126 в классе инициальных (4,2,2) - автоматов выполняется отношение > ^ и функция Б принимает значение РСп^.п^п^;) = 0,14 (метод интерполяции Ньютона с оценкой 0,14 точнее метода Лагранжа).

Теорема 2.1.4. Пусть узлами интерполяции для геометрического образа длины <1 каждого автомата А=(8, {0,1}, У, 8, X, 5о) из класса инициальных (4,2,2)-автоматов являются точки геометрических образов автономных подавтоматов Ао=(8, {0}, У, 50 , Хо, Бо) и А1=(8, {1}, У, 5, , Хь Бо)

автомата А . Тогда для методов интерполяции Ньютона и Лагранжа при с!=126 в классе инициальных (4,2,2) - автоматов выполняется отношение пИ > "¡1 и функция Р принимает значение ) = 0,14 (метод

интерполяции Ньютона с оценкой 0,14 точнее метода Лагранжа).

Теорема 2.2.1. Пусть узлами интерполяции для геометрического образа длины с! каждого автомата А=(8, {0,1}, У, 5, X, во) из класса линейных (8,2,2) -автоматов являются точки геометрических образов автономных подавтоматов Ао=(8, {0}, У, 5о , Хо, Бо) и А[=(8, {1}, У, 5! , Х.ь б0) автомата А . Тогда для методов интерполяции Ньютона и Лагранжа при (1=254 в классе инициальных линейных (8,2,2) - автоматов выполняется отношение п^ > п^ и функция Р принимает значение Р^.п^п^ ) = 0,012 (метод интерполяции Ньютона с оценкой 0,012 точнее метода Лагранжа).

В третьей главе разработаны методы и алгоритмы распознавания

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

Определение 3.1. Пусть L - геометрическая кривая и Д - отрезок на оси абсцисс, на котором определена часть кривой L ( или вся кривая L). Эту часть кривой будем обозначать L (Д).

Теорема 3.1. Пусть а = {Ai}ie[- семейство инициальных автоматов , где Ai=(Sj, X, Y, 5i, Aj ,s0j), s0. e S,, a P = (Yiîiei - семейство их геометрических образов , расположенных соответственно на кривых из семейства Ь = . Если существует отрезок Д оси абсцисс , на котором для любых i, j e I, при ¡■ф-j, выполняется система равенств {Ь1(Д)}П{Ц(Д)}=0 и на отрезке Д определены некоторые точки геометрических образов из семейства р , то отрезок Д содержит решение простым безусловным экспериментом задачи распознавания автомата относительно семейства а .

В четвертой главе разработаны алгоритмы оценки сложности законов функционирования автоматов на основе имеющихся оценок сложности для стандартного набора автоматов. Для этого стандартные автоматы предполагаются заданными геометрическими кривыми для примера выбранными из Международного французского банка математических кривых ENCYCLOPÉDIE DES FORMES MATHÉMATIQUES REMARQUABLES (т.е. представленными последовательностями вторых координат точек, интерпретируемых как последовательности вторых координат точек геометрических образов автоматов) и последовательностями в приближениях величин из массива H (см.стр.9).

Сложность оценивается по показателям спектра рекуррентных описаний последовательностей вторых координат точек геометрических образов законов функционирования автоматов, расположенных на кривых из Международного французского банка математических кривых ENCYCLOPÉDIE DES FORMES MATHÉMATIQUES REMARQUABLES. Получены оценки сложности законов функционирования автоматов из класса (4,2,2)-автоматов и его подклассов.

Полученная оценка для каждого инициального автомата A=(S, X, Y, 5, X, so), где jY| = / , распространяется на оценку сложности /! изоморфных по выходам автоматов. Введем множество

ctm(Hj) = <Ad», A», A¡?(q>), А™(л/2), АЦЧВД), A^lnClO)), AjKP», Aj(C), Aj(T)},

где m - число входных сигналов автомата , d - длина последовательности, интерпретируемой как последовательность вторых координат точек геометрического образа автомата, 3 е Hd, Hj — множество начальных отрезков длины d последовательностей, определяющих элементы из массива Н, А™(Р) - дискретный детерминированный автомат, определяемый величинами m,d и р.

Теорема 4.1.1. Множество законов функционирования автоматов из a"(Hd), для d=l000000, по нулевому уровню fio спектра Q разбивается на 2

класса эквивалентности по сложности: {A¿(e),A<f(я),A|f(<р),А°$2), А°(£(3))} и А™(т/2), а31(1л(2)),а31(1п(10)),а31(С)>А™(тг)}, и по первому уровню fii спектра Q образуют одноэлементные классы эквивалентности по сложности.

Теорема 4.1.2. Множество законов функционирования автоматов из а"{Н^), для d=1000, по нулевому уровню Cío спектра ÍÍ разбивается на 2 класса эквивалентности по сложности: {A3'(e),A™(^),A31K(3))} и {A'd А™ (ф), А™ (л/2), A™ (ln(2)), A™ (ln(10)), А™ (С), А™(у)}; и по первому уровню fii спектра Í2 образуют одноэлементные классы эквивалентности по сложности.

Автор выражает глубокую благодарность профессору В.А.Твердохлебову за руководство работой над диссертацией.

Список использованной литературы

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

2. Богомолов А.М., Салий В.Н. Алгебраические основы теории дискретных систем. -М.: Наука, 1997.

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

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

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

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

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

8. Дискретная математика и математические вопросы кибернетики / Под.ред. С.В.Яблонского и О.Б.Лупанова. -М.:Наука,1974.

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

10. Кудрявцев В.Б., Алёшин C.B., Подколзин АС. Введение в теорию автоматов. - М: Наука,1985.

11. Мур Э.Умозрительные эксперименты с последовательными машинами / Автоматы. Сб. статей под ред. К.Шенкона и ДМаккарти, - М.-.ИИЛ, 1956. С.179-213.

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

13. Твердохлебов В. А Геометрические образы законов функционирования автоматов - Саратов: Изд-во «Научная книга», 2008.

14. Яблонский C.B. Введение в дискретную математику. - М.гНаука, 1988.

Список публикаций автора по теме диссертации

Al. Епифанов A.C. Автоматная интерпретация целочисленных последовательностей. // Изв. Сарат. ун-та. Новая серия. Сер. Математика, Механика, Информатика. - 2010. - Т. 10,вып.4.С.58-64.

А2. Епифанов АС. Анализ геометрических образов законов функционирования автоматов. // Управление большими системами. Выпуск 24. М.: ИЛУ РАН, 2009. С.81-98.

A3. Епифанов АС. Анализ фазовых картин дискретных динамических систем.-Саратов:Изд-во «Научная книга», 2008. ISBN 978-5-9758-0926-1

A4. Епифанов АС. Интерпретация спектра характеристик дискретных систем при проектировании./Мэтериалы 6-ой международной конф. «Автоматизация проектирования дискретных систем». Т.1, Минск.2007.С.73-77

А5. Епифанов A.C. Интерполяция фазовых картин дискретных детерминированных систем. // «РАДЮЕЛЕКТРОНШ I КОМП'ЮТЕРШ СИСТЕМИ», Харюв, №5,2008. С. 128-132.

А6. Епифанов A.C. Анализ эффективности применения методов интерполяции для доопределения законов функционирования сложных систем. / Информационные технологии и системы (ИТиС'08):сборник трудов конференции. - М.: ИППИ РАН, 2008. -517с. С. 104-108.

А7. Епифанов A.C. Классификация законов функционирования дискретных динамических систем на основе спектра параметров. / V Всероссийская школа-семинар молодых ученых «Управление большими системами»: Сборник трудов.-T.l. - Липецк, ЛГТУ,2008.С. 17-23.

А8. Епифанов A.C. Построение и анализ классов (Н,т,с1(Н))-автоматов. / V Всероссийская школа-семинар молодых ученых «Управление большими системами»: Сборник трудов.-Т.1. - Липецк, ЛГТУ,2008.С.23-30.

А9. Епифанов A.C. Использование интерполяции и экстраполяции для анализа законов функционирования сложных систем. - Материалы второй международной конференции "Управление развитием крупномасштабных систем МLSD'2008". И: 2008. - С.232-235.

А10. Епифанов A.C. Анализ фазовых картин дискретных динамических систем с использованием спектра динамических

параметров.//«РАДЮЕЛЕКТРОНШ I КОМП'ЮТЕРШ СИСТЕМИ», Харюв,№5,2009. С.111-116.

AI 1. Епифанов A.C. Анализ дискретных динамических систем, заданных в форме числовых структур.//«РАДЮЕЛЕКТРОНШ I КОМП'ЮТЕРШ СИСТЕМИ», Харюв,№6,2009.С. 118-122.

А12. Епифанов A.C. Анализ геометрических образов и свойств автоматов.-Восьмая международная конференция «Дискретные модели в теории управляющих систем»: Москва, 6—9 апреля, 2009 г.: Труды / Отв. ред. В. Б. Алексеев, В.А.Захаров. — М.: Издательский отдел факультета ВМиК МГУ им. МВ.Ломоносова; МАКС Пресс, 2009. - 380с. С.87-92.

А13. Епифанов A.C. Классификация дискретных детерминированных автоматов по свойствам геометрических образов. Материалы 7-ой молодежной научной школы по дискретной математике и ее приложениям. ИПМ РАН им.М.В.Келдыша. М. Часть 1. Под ред. А В.Чашкина.2009г. С.34-39.

А14. Епифанов АС. Метод диагностирования программируемых логических интегральных схем с использованием геометрических образов. / Науково-техшчшш журнал "ШФОРМАЩЙНО - КЕРУЮЧ1 СИСТЕМИ НА ЗАШЗНИЧНОМУ ТРАНСПОРТ! №4(77), Харьков, 2009, С.152-155.

Al 5. Епифанов A.C. Автоматная интерпретация фрагментов

последовательности ДНК / Информационные технологии и системы (ИТиС'08):сборник трудов конференции.-М.: ИППИ РАН, 2009.С.318-323.

А16. Епифанов A.C. Анализ операций совмещения геометрических образов законов функционирования автоматов. // «РАДЮЕЛЕКТРОНШ I КОМП'ЮТЕРШ СИСТЕМИ», Харгав,№5,2010.С.219-223.

Al 7. Епифанов АС. Оценка сложности и классификация маршрутов по сложности на основе спектра параметров.//«РАДЮЕЛЕКТРОНШ I КОМП'ЮТЕРШ СИСТЕМИ», Харюв,№7,2010.С. 180-184.

А18. Епифанов A.C. Метод оценки сложности и классификации законов функционирования дискретных детерминированных автоматов. //Материалы X Международного семинара "Дискретная математика и ее приложения" / Под редакцией О.М.Касим-Заде. - М.: Изд-во механико-математического факультета МГУ, 2010. - 549с. С.358-361.

А19. Епифанов АС. Метод оценки сложности законов функционирования автоматов на основе дискретных riv-функций. Научно-тех. журнал «Информационно-управляющие системы на железнодорожном транспорте», №4(83), Харьков, 2010, с. 119-122.

А20. Епифанов АС. Оценка сложности законов функционирования автоматов с использованием дискретных сегментных функций. Материалы седьмой Международной научно-практической конференции "Теоретические и прикладные аспекты построения программных систем". Киев, 2010. С.225-234.

Подписано в печать 07.02.2011. Формат60х84 1/16. Бумага офсетная. Гарнитура Times New Roman. Печать RISO. Объем 1,0 печя. Тираж 120 экз. Заказ № OÍ О Отпечатано с готового оригинал-макета Центр полиграфических и копировальных услуг Предприниматель Серман Ю.Б. Свидетельство №3117 410000, г.Саратов, у «.Московская, 152, офис' 19

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

ВВЕДЕНИЕ.

ГЛАВА 1. ОСНОВНЫЕ ПОНЯТИЯ, ИСПОЛЬЗУЕМЫЕ

МОДЕЛИ И МЕТОДЫ.

1.1. Геометрические образы законов функционирования дискретных детерминированных динамических систем.

1.2. Классические методы интерполяции как средство доопределения законов функционирования дискретных детерминированных динамических систем.

1.3. Спектр динамических параметров рекуррентного определения числовых последовательностей.

ГЛАВА 2. ДООПРЕДЕЛЕНИЕ ЧАСТИЧНО ЗАДАННЫХ ЗАКОНОВ ФУНКЦИОНИРОВАНИЯ АВТОМАТОВ НА ОСНОВЕ КЛАССИЧЕСКИХ МЕТОДОВ ИНТЕРПОЛЯЦИИ.

2.1. Анализ эффективности применения классических методов интерполяции для доопределения законов функционирования автоматов в классе (4,2,2)-автоматов.

2.2. Анализ эффективности в классе (8,2,2)-автоматов методов интерполяции Ныотона и Лагранжа по узлам интерполяции, определенным автономными подавтоматами.

2.3. Анализ эффективности методов интерполяции Ныотона и Лагранжа по узлам интерполяции, расположенным на прямых, параллельных оси абсцисс.

ГЛАВА 3. РАСПОЗНАВАНИЕ АВТОМАТОВ.

3.1. Распознавание автоматов по их геометрическим образам.

3.2. Метод распознавания автоматов, заданных последовательностями вторых координат точек геометрических образов автоматов.

ГЛАВА 4. ОЦЕНКА СЛОЖНОСТИ И КЛАССИФИКАЦИЯ ПО СЛОЖНОСТИ ЗАКОНОВ ФУНКЦИОНИРОВАНИЯ АВТОМАТОВ.

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

4.2. Оценка сложности и классификация по сложности геометрических образов автоматов из класса (4,2,2)-автоматов.

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

4.4. Метод оценки сложности конечных детерминированных автоматов по числу состояний в минимальной форме с использованием дискретных Шу-функций.

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

В классе дискретных детерминированных динамических систем конечные детерминированные автоматы образуют простейший, но достаточно исследованный подкласс. Развитые методы анализа, синтеза, распознавания и т.п. конечных детерминированных автоматов эффективно применяются в решении прикладных задач для реальных систем, автоматные модели которых явно задаются таблицами, матрицами, графами, логическими уравнениями и др. После введения Мак-Каллоком и Питтсом (1943 г.) основных положений, на которых строится понятие автомата, теория автоматов получила развитие в работах Дж.Неймана, С.Клини, М.Л.Минского, Дж.Маккарти, М.Арбиба, В.М.Глушкова, А.А.Летичевского, Ю.В.Капитоновой, В.Б.Кудрявцева, С.В.Алешина, А.С.Подколзина, М.И.Кратко, Н.Е.Кобринского, Б.А.Трахтенброта, Я.М.Бардзиня, В.Г.Лазарева, Е.И.Пийля, В.И.Варшавского, С.И.Баранова, М.А.Спивака, М.А.Айзермана и др. Результаты исследований, представленные в работах указанных авторов, составляют фундаментальную основу символьной теории автоматов, т.е. теории, в которой автоматы, как правило, не связаны с классическими числовыми структурами, что ограничивает применение в теории автоматов методов классической математики.

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

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

В диссертации поставлены и рещены следующие задачи.

Задача 1. Исследовать возможность методов интерполяции Ныотона, Лагранжа, Гаусса, Бесселя, Стирлинга и др. для законов функционирования автоматов, частично заданных геометрическими образами.

- последовательностями вторых координат точек геометрических образов автоматов;

- классом (4,2,2)-автоматов и его подклассами, определенными по свойствам Поста;

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

Принципиальную важность задач интерполяции для математики показали выдающиеся математики, именами которых названы методы интерполяции: Ньютон, Лагранж, Гаусс, Стерлинг, Бессель и др. Актуальность интерполяции при распознавании автоматов связана с тем, что математические модели сложных систем не могут быть полными и точными и, как правило, в этих моделях определены только фрагменты процесса функционирования, а при решении задач управления сложными системами, задач технического диагностирования и др. требуется хотя бы грубая информация о процессах функционирования системы в целом.

Один из основных классов задач математической кибернетики составляют задачи распознавания поведения (наблюдаемого функционирования) искусственных и естественных систем. При этом распознаются системы по поведению или по функционированию (технические системы), распознаются свойства систем, состояний систем и т.д. Задачи из этого класса задач решали А.Тыоринг (тест Тьюринга), Э.Мур и А.Гилл (распознавание автоматов и состояний автоматов), С.В.Яблонский (логические способы контроля) и др. Решение задач управления необходимо использует решение задач распознавания состояния и положения объекта управления. Все эти задачи для случая дискретных детерминированных систем формулируется как задачи распознавания автомата в заданном семействе автоматов или задачи распознавания свойств и состояний автомата.

Фундаментальные понятия сложности — класс Р-проблем, разрешимых за полиномиальное время детерминированными машинами Тыоринга, и класс NP-проблем, разрешимых за полиномиальное время недетерминированными машинами Тыоринга, связаны с автоматами машинами Тьюринга). На ряду с общим «алгоритмическим» пониманием сложности в теории автоматов исследовались частные варианты показателей сложности: число состояний автомата, длины входных и выходных последовательностей, число компонент связности в структуре автомата, сложность структуры структурного автомата и др.

Проблема оценки сложности автоматов исследовалась многими авторами сразу же после введения автоматных моделей. Дж. Фон Нейман задачам оценки сложности автоматов посвятил ряд разделов своей работы «Теория самовоспроизводящихся автоматов»:

Роль высокой и очень высокой сложности (включая роль сложности и необходимость соответствующего теоретического обоснования и др);

Переоценка проблем сложных автоматов — проблемы иерархии и эволюции.

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

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

Оценка точности интерполяции проведена для начальных отрезков длины до 1 млн. знаков в приближенных представлениях величин л , е, ер = 1 + (т.н. золотое сечение), л/2, 1/2, 1п(2), 1п(10), = константа

2 х=\ *

Каталана с = £——константа Эйлера / = Нт(1+ — + - + .+— 1п(п))) и др. „=о(2гс +1) «->«> 2 3 п

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

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

В главе 4 на основе спектра динамических параметров П (см, [81]) осуществляется исследование свойств фундаментальных математических величин, заданных приближенно в виде последовательностей, и законов функционирования дискретных детерминированных динамических систем в форме геометрических образов. Ввиду того, что геометрический образ взаимно-однозначно определяется последовательностью вторых координат его точек, в главе свойства законов функционирования исследуются на основе анализа свойств числовых последовательностей. Рассматривается множество последовательностей длины от 80 до 10 млн. знаков, представленных в банке [92], определяющих приближения фундаментальных математических величин к , е, ер = 1 (т.н. золотое сечение), л/2,

00 1 00 (— 1п(2), 1п(10), С(3) = Х—Г' константа Каталана с = —константа Эйлера х=\х п=о (2п +1) у = Нт(1+—+ — + . +——1п(и))) и др. Для классификации и оценки сложности и-»® 2 3 п последовательностей используется спектр динамических параметров, характеризующих сложность правил порождения последовательности. Для каждой последовательности строятся спектр и на основе совпадения по показателям построенных спектров множество разбивается на классы эквивалентных последовательностей. Например, с точки зрения используемого спектра динамических характеристик, наибольшую сложность среди указанных выше последовательностей на начальном отрезке длины 50 знаков имеют число е и константа Каталана С = ——г. При л=о(2и + 1) увеличении длины анализируемых начальных отрезков до 200 знаков сложнейшими оказались последовательности, задающие приближения чисел л/2 и 1п(10), при длине 1000 знаков - наибольшую сложность имеют е , \[2 и

00 1

3) = на начальном отрезке 2000 знаков наибольшую сложность имеет последовательность, задающая приближение 1п(2), в то время как те , е, <р (т.н. золотое сечение), V2,V2,1п(10), £(3), константа Каталана и константа Эйлера имеют одинаковую сложность при данной длине. С увеличением длины начальных отрезков последовательностей до 5000 знаков оказывается, что последовательности тс , е, ср (т.н. золотое сечение), -Jl, \fi, ln(2), £(3), константа Каталана и константа Эйлера имеют одинаковую сложность, а ln( 10) оказывается самой сложной.

Проведенный в главе 4 анализ последовательностей вторых координат точек геометрических образов всех членов класса (4,2,2)-автоматов, т.е. автоматов, имеющих 4 состояния, 2 входных и 2 выходных сигнала, выявил следующие свойства. Класс (4,2,2)-автоматов, состоящий из 16777216 элементов, разбит на 4 подкласса по числу состояний у автомата после минимизации. В построенных подклассах для последовательностей вторых координат точек геометрических образов автоматов на основе использования спектра динамических параметров П вы числены следующие характеристики: - минимальное значение сложности в подклассе автоматов, имеющих i состояний после минимизации, к12 - максимальное значение сложности в подклассе и к\ - среднее значение сложности, в подклассе. Отмечено, что к\ имеет одинаковое значение для всех / е {l, 2,3,4}, к а к'2 и к12 растут с увеличением i , причем -^-=15, т.е. в подклассе автоматов, имеющих после минимизации 4 состояния (все 4 состояния у таких автоматов различимы), максимальное значение сложности с точки зрения используемого спектра в 15 раз больше, чем в подклассе автоматов, имеющих после минимизации 1 состояние (все 4 состояния у таких автоматов эквивалентны). Среднее значение сложности к\ почти в 8 раз меньше, чем к\.

Также в главе 4 приведены результаты по оценке сложности и классификации по сложности законов функционирования автоматов, заданных геометрическими кривыми, извлеченными из банка 2D,3D-KpHBbix и фракталов, представленного в сети Интернет по адресу [93]. Для анализа выбраны 50 наиболее известных и распространенных геометрических кривых на плоскости: спираль Фибоначчи, лемниската Берну лли х2 + у2)2 =а2(х2-у2)), баллистическая кривая (y = -x + c-in^i--j), эвольвента t+-) t2 круга (Paramétrisation complexe : z = a(eil-te^ 2o = a + - J e'^"du) ,

2 о логарифмическая спираль (Abscisse curviligne et équation intrinsèque 2 : 2 s = pV1 + k ), спираль Архимеда (Absvcisse curvilgne: le s = a jVi + t2dt, 2п7г < 0 < 2(n+l )ж), астроида ( +fï = lia* ), спираль Галилео о

Abscisse curviligne : ds = 7a2 + 2b(a + 2b)82 + b2e4de ), брахистохрона (Équation x=a,y=-b fonctionnelle : J -¡L minimal ), кардиоида (Paramétrisation complexe : x=0,y=0 vM z = + 2eu + e2lt) ), улитка ПаСКаЛЯ ( (x2 + y2 - eax)2 = a2(x2 + y2) ), ЦИССОИДа t2

• 2 x(x2 + y2) = ay2), кривая Корно (Paramétrisation complexe : z = ajem du), кривая о

Гаусса (У =-г='е 2гг2 ), корноида ((х2+у2)3+а2(Зх4-6х2у2-5у4) + 8а4у2-4а6=0) и аы 2л др. Проведенное исследование свойств 20-кривых включило:

- построение по кривым законов функционирования автоматов;

- построение спектров для последовательностей вторых координат точек геометрических образов построенных автоматов;

- разбиение множества геометрических образов на классы эквивалентности на основе совпадения показателей на уровнях £20 - Дз спектра О.

По показателям нулевого уровня Г20 используемого спектра П эквивалентными по сложности оказались автоматы, законы функционирования которых задают: 1.спираль Фибоначчи; 2. двулистник геометрическая кривая, определенная уравнением (х2 + у2)2 = (ах + Ьу)х2, где а=1, Ь=0.5; 3.кривая Сакре. Класс эквивалентности на четвертом уровне Г2з спектра П составляют автоматы, заданные окружностью и астроидой.

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Епифанов, Антон Сергеевич, Саратов

1. Автоматы. М.: Мир. 1956. 404с.

2. Айерланд К., Роузен М. Классическое введение в современную теорию чисел. — М.: Мир, 1987.

3. Берже М. Геометрия. Т. 1, 2. —М.: Мир, 1984.

4. Брус Дж., Джиблин П. Кривые и особенности. — М.: Мир, 1988

5. Бухштаб A.A. Теория чисел.-М.:Просвещение,1966

6. Васильев Н. Б., Гутенмахер В. Л. Прямые и кривые. — М.: МЦНМО,2000.

7. Айзерман М.А. и др. Логика. Автоматы. Алгоритмы. Физматгиз. —М. — 1963.-556с.

8. Апериодические автоматы. М.: Наука, 1974. 423с.

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

10. Варшавский В.И. Коллективное поведение автоматов. М.:, 1975. 408 с.

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

12. Гинзбург С. Математическая теория контекстно-свободных языков. М.:Мир, 1970г.328с.

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

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

15. Епифанов A.C. Интерпретация спектра характеристик дискретных систем при проектировании./Материалы 6-ой международной конф.Автоматизация проектирования дискретных систем». Т.1, Минск. 2007.

16. Епифанов A.C. Спектры динамических характеристик фундаментальных математических величин и 3-х классов автоматов. /Материалы международной конф. «Проблемы и перспективы прецизионной механики и управления в машиностроении».- Саратов. 2007.

17. Епифанов A.C. Интерполяция фазовых картин дискретных детерминированных систем. // «РАДЮЕЛЕКТРОНН1 I КОМП'ЮТЕРШ СИСТЕМИ»,Харюв,№5,2008.

18. Епифанов A.C. Анализ фазовых картин дискретных динамических систем. Саратов: Изд-во «Научная книга», 2008. — 156 с. ISBN 978-59758-0926-1

19. Епифанов A.C. Классификация маршрутов по сложности управления движением на основе спектра параметров. / Научно-тех. журнал «Информационно-управляющие системы на железнодорожном транспорте», №4, Харьков, 2008, с.7. ISSN 1681-4886

20. Епифанов A.C. Классификация законов функционирования дискретных динамических систем на основе спектра параметров. / V Всероссийская школа-семинар молодых ученых «Управление большими системами»: Сборник трудов.-T.l. Липецк, ЛГТУ,2008.С. 17-23.

21. Епифанов A.C. Построение и анализ классов (Н,т,с1(Н))-автоматов. / V Всероссийская школа-семинар молодых ученых «Управление большими системами»: Сборник трудов.-T.l. — Липецк, ЛГТУ,2008.С.23-30.

22. Епифанов A.C. Использование интерполяции и экстраполяции для анализа законов функционирования сложных систем. Материалы второй международной конференции "Управление развитием крупномасштабных систем MLSD'2008". 2008. - С.232-235. ISBN 9785-91450-019-8

23. Епифанов A.C. Оценка сложности законов функционирования дискретных систем на основе спектра параметров. // Доклады академии военных наук. №5(34). Сарат., 2008 C.50-55.ISSN 1728-2454

24. Епифанов A.C. Анализ геометрических образов законов функционирования автоматов / Управление большими системами. Выпуск 24. М.: ИПУ РАН, 2009. С.81-98. ISSN 1819-2467

25. Епифанов A.C. Анализ фазовых картин дискретных динамических систем с использованием спектра динамическихпараметров. // «РАДЮЕЛЕКТРОНШ I КОМП'ЮТЕРШ СИСТЕМИ», Харюв,№5,2009. С.111-116.ISSN 1814-4225

26. Епифанов A.C. Анализ дискретных динамических систем, заданных в форме числовых структур.// «РАДЮЕЛЕКТРОНШ I КОМПТОТЕРН1 СИСТЕМИ», Харюв,№6,2009.С. 118-122. ISSN 1814-4225

27. Епифанов A.C. Классификация функций алгебры логики по показателям спектра динамических параметров. Компьютерные науки и информационные технологии: Материалы Между нар. науч. конф. -Саратов: Изд-во Сарат.ун-та,2009.С.88-91 ISBN 978-5-292-03927-3

28. Епифанов A.C. Построение и анализ математических моделей интегральных схем в геометрической форме. Компьютерные науки и информационные технологии: Материалы Междунар.науч.конф. -Саратов: Изд-во Сарат.ун-та,2009.С.91-95 ISBN 978-5-292-03927-3

29. Епифанов A.C. Синтез и анализ законов функционирования программируемых логических интегральных схем. Материалы третьей международной конференции "Управление развитием крупномасштабных систем MLSD'2009". 2009. - С.306-308. ISBN 9785-91450-037-2

30. Епифанов A.C. Автоматная интерпретация фрагментов последовательности ДНК. / Информационные технологии и системы (ИТиС'08):сборник трудов конференции. М.: ИППИ РАН, 2009. -463с. ISBN 978-5-901158-11-1 С.318-323.

31. Епифанов A.C. Метод диагностирования интегральных схем на основе декомпозиции геометрических образов автоматов.// Доклады Академии Военных Наук. №5(40) , 2009. С.37-41. ISSN 1728-2454

32. Епифанов A.C. Анализ операций совмещения геометрических образов законов функционирования автоматов. // «РАДЮЕЛЕКТРОНШ I КОМП'ЮТЕРШ СИСТЕМИ», Харюв,№5,2010.С.219-223. ISSN 18144225.

33. Епифанов A.C. Оценка сложности и классификация маршрутов по сложности на основе спектра параметров.// «РАДЮЕЛЕКТРОНН1 I КОМП'ЮТЕРШ СИСТЕМИ», Харюв,№7,2010.С.180-184. ISSN 18144225.

34. Епифанов A.C. Метод оценки сложности законов функционирования автоматов на основе дискретных riv-функций. Научно-тех. журнал «Информационно-управляющие системы на железнодорожном транспорте», №4(83), Харьков, 2010, с. 119-122. ISSN 1681-4886

35. Епифанов A.C. Методы интерполяции законов функционирования автоматов. Материалы 7-й научно-технической Конференции "Мехатроника, автоматизация, управление " (МАУ-2010). Санкт-Петербург-2010. С. 167-170 ISBN 978-5-91995-003-5

36. Епифанов A.C. Анализ геометрических образов поведения автоматов. Материалы Дев'ятого М1жвуз1вского науково-практичного семшару "КОМБ1НАТОРН1 КОНФИГУРАЦИИ ТА IX ЗАСТОСУВАННЯ", 16-17 апреля 20Юг.,Кировоград. С.56-60. ISBN 978-966-8876-19-6.

37. Епифанов A.C. Автоматная интерпретация целочисленных последовательностей. // Изв. Сарат. ун-та. Новая серия. Сер. Математика, Механика, Информатика. 2010. - Т. 10,вып.4.С.58-64.

38. Епифанов A.C. Синтез и анализ (Н,т,с1(Н))-автоматов. Материалы Седьмой Международной конференции "Автоматизация проектирования дискретных систем", 16-17 ноября 2010г., Минск. -Минск: ОИПИ HAH Беларуси, 2010. 386с. С.113-120. ISBN 978-9856744-63-4.

39. Иванов H.H., Михайлов Г.И., Руднев В.В., Таль A.A. Конечные автоматы: эквивалентность и поведение. Наука, М., 1984, с. 192.

40. Каллман Р., Фалб П., Арбиб М. Очерки по математической теории систем. Мир, М., 1971.

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

42. Конечные автоматы: эквивалентность и поведение. М.: Наука, 1984. 192с.

43. Кудрявцев В.Б., Алёшин C.B., Подколзин A.C. Введение в теорию автоматов. -М.: Наука. -1985. -320с.

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

45. Лупанов О.Б. Асимптотические оценки сложности управляющих систем. М.: Изд-во МГУ, 1984.

46. Мелихов А.Н. Ориентированные графы и конечные автоматы. М.: Наука, 1971.410с.

47. Минский М.Л Вычисления и автоматы. Перев. с англ. Овсиевича Б.Л. и Розенблюма Л.Я. -ML: Мир. -1971. -366с.

48. Моисеев H.H. Математика ставит эксперимент/ Н.Н.Моисеев,-М. :Наука, 1979.-224с.

49. Мур Э. Умозрительные эксперименты с последовательными машинами / Автоматы. Сб. статей под ред. К. Шеннона и Д. Маккарти, ИИЛ, М., 1956, с. 179-213.

50. Отказоустойчивые информационно-управляющие системы на программируемой логике./Под ред.Харченко B.C., Скляра В.В. -Национальный аэрокосмический университет «ХАИ»,Научно-производственное предприятие «Радий», 2008, 380с.

51. Поспелов Д.А. Логико-лингвистические модели в системах управления. М.:Энергоиздат, 1981 ,с.232.

52. Проблемы математической логики. Сложность алгоритмов и классы вычислимых функций. М.: Мир. 1970.

53. Рвачев В.Л. Об аналитическом описании некоторых геометрических объектов. ДАН СССР, Т. 153, № 4, 1963. с.765-767.

54. Резчиков А.Ф., Твердохлебов В.А. Техническое диагностирование мехатронных систем / // Мехатроника, автоматизация, управление. -2003. № 2. - С. 2-6.

55. Савелов A.A. Плоские кривые. Москва Ижевск, 2002. 294с.

56. Смирнов А.К., Твердохлебов В.А. Управление жизиенными циклами сложных систем. Саратов: Изд-во Сарат. ун-та, 2000. 110с.

57. Сперанский Д.В. Эксперименты с линейными и билинейными конечными автоматами. Изд-во Сарат. ун-та, 2004. 144с.

58. Сперанский Д.В. Лекции по теории экспериментов с автоматами.М.:-ИНТУИТ,2010г.

59. Твердохлебов В.А. Методы интерполяции в техническом диагностировании // Проблемы управления. №2, 2007. С.28-34.

60. Твердохлебов В.А. Геометрические образы законов функционирования автоматов Саратов: Изд-во «Научная книга», 2008. - 183 с. ISBN 9785-9758-0924-7

61. Твердохлебов В.А. Техническое диагностирование в геометрической интерпретации задач, моделей и методов / Материалы Международной конференции «Автоматизация проектирования дискретных систем»,т. 1, Минск, 1995, с. 97.

62. Твердохлебов В.А. Дискретное пространство для образов поведения конечных автоматов / Теоретические проблемы информатики и ее приложений. Изд-во Сарат. ун-та, вып. 5, 2003, с. 163-174.

63. Твердохлебов В. А. Геометрические образы конечных детерминированных автоматов / Известия саратовского университета (Новая серия) том 5, вып.1, 2005,141-153.

64. Тверд охлебов В. А., Пономаренко А. В. Классификация конечных автоматов по свойствам функций переходов и выходов // Проблемы точной механики и управления : сб. науч. тр. Саратов : СГТУ, 2004. С. 16-25.

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

66. Хиббард Т.Н. Точные верхние границы длин минимальных экспериментов, определяющих заключительное состояние, для двух классов последовательностных машин. Кибернитический сборник(новая серия). 1966, вып. 2. С. 7-23.

67. Хопкрофт Д.,Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений. Перев. с англ. Васылык О.И., Саит-Аметова М., Ставровского А.Б. Изд.дом "Вильяме", М.-СПб-Киев, 2002, с.528.

68. Яблонский C.B. Введение в дискретную математику. Наука, М., 1988.90. http://www.ncbi. nlm.nih.gov/protein/29683 7271 ?report=genpept91.www.fl-live.ru92.www.oeis.org93 .www.mathcurve.com