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

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

Калитин Денис Владимирович

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

Специальность 05.13.12 - "Системы автоматизации проектирования (промышленность)"

Автореферат диссертации на соискание учёной степени кандидата технических наук

Москва 2005 г.

Работа выполнена в Московском государственном горном университете.

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

доктор технических наук Александр Вячеславович Горбатов Официальные оппоненты:

доктор технических наук, профессор Леонид Давидович Певзнер, кандидат технических наук, профессор Валентин Викторович Нечаев.

Ведущая организация: Морской научно-исследовательский институт радиоэлектроники "Альтаир".

Защита диссертации состоится

"27" апреля 2005 г. в 14 — час. на заседании диссертационного совета Д.212.128.07 при Московском государственном горном университете по адресу: Москва, 119991, Ленинский проспект, 6.

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

Автореферат разослан марта 2005 г.

Учёный секретарь диссертационного совета доктор технических наук С.С. Кубрин

^2*33 £

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

Актуальность темы

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

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

Цель работы

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

РОС. НАЦИОНАЛЬНАЯ БИБЛИОТЕКА Г. Петербург 280 (РК _

(рк

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

Идея работы

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

Задачи исследования:

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

• Определить топологию кластеров Ск{п,к) с размерностью равной п и значностью к, а так же их суперпозицию по мультипликативной связке;

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

• Найти запрещённые фигуры вложимости графа сцепления автоматной грамматики в кластеры, являющиеся декартовым произведением кластеров размерностью п и значностью к;

• Разработать алгоритм вложения графа сцепления в кластер при минимальном сужении сигнатуры графа сцепления;

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

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

Методы исследований

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

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

Защищаемые научные положения и их новизна

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

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

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

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

Научное значение состоит в следующем:

• Развита декомпозиционная теория параллельно функционирующих управляющих автоматов с учётом минимизации их функциональной связности;

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

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

Практическая ценность заключается:

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

3

следовательно, в любых операционных средах, поддерживающихся этими процессорами.

• В эффективном внедрении разработанного программного инструментария в реальное производство цифровой аппаратуры в ГУ НПО "Специальная техника и связь" МВД РФ и ЗАО НПЦ "Альтаир" о чём имеются соответствующие акты о внедрении.

Апробация работы

Основные результаты работы были обсуждены:

• на конференциях, проводимых РАЕН, международной академией информатизации и МГГУ: "Логическое управление. Характеризационный анализ. САПР", М, 1999 г.; "Логическое управление. Характеризационный анализ. САПР", М, 2003 г., "Характеризационный анализ. Нейронные технологии. САПР", М, 2005 г.;

• на семинарах отделения "Теоретическая информатика и информационные технологии и стратегии" Международной академии информатизации.

Публикации

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

Объём и структура работы

Диссертационная работа состоит из введения, 4 глав и заключения, содержит 20 таблиц, 53 рисунка и список литературы из 83 наименований.

Основное содержание работы

Синтез параллельной декомпозиции автомата, описываемого графом переходов О^ = (V,{и,{х,У))),

где V—множество нетерминальных символов;

ХиУ- терминальные, соответственно входные и выходные, символы; и, и с V1- множество переходов,

сводится к поиску частичного декартова произведения [^С^,, включающего заданный граф переходов:

ечсПсЧ1 (1)

I

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

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

= о^сЦо^, (2)

>,1* >

где аЛ — количество переходов, в которых при вычислении /-го состояния ¿-го автомата-сомножителя, используется у]к, у ф г , состояний других автоматов-сомножителей.

В том же году проф. В.А. Горбатов решил эту проблему, которую в последующем развил его ученик проф. А.Г. Дедегкаев (1993 г.).

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

Для минимизации функциональной связности 1{Опср) будем использовать понятие бинарного отношения сцепления Ла1 в множестве нетерминальных символов {— нетерминальный символ автоматной грамматики}.

Графом сцепления = , {■<*',})} называется взвешенный граф, элементы носителя V которого взаимнооднозначно соответствуют элементам множества

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

состояние 5а, , и из состояния под воздействием вектора X,, X, ст — в состояние , —► ^, при этом * .г, и (.у, * ^):

V у

Состояния 5,, удовлетворяющие (3), называются сцепленными вектором

х„.

При представлении графа переходов О -'V .(и ,(х .у))) заданной

автоматной грамматики в виде частичного декартова произведения \\От1>1,

1.1

(¡тр< = (('.(б-'ДХТ))) каждому нетерминальному символу , исходной грамматики сопоставляется кор[еж (^,/г = 1,2....,п,б„, у„, е^), Очевидно, что имеем нарушение автоматности /-го графа переходов 6'„(,; ^ (У;.(Ь'Г(Х.У))), I е {1,2, ,«}, если при переходе из сцепленных векторами

Х_. Х\. X, с Л^ состояний

(4)

/-Й автомат-сомножитель, имеющий одинаковые значения для не 1ерминальных символов и и различные значения для состояний и

под воздействием векторов Хк и Хк переходит соответственно в состояния и

V

(5)

*„/=*/,/> (6)

(7)

Отсюда, имеем теоремы 1,2.

Теорема 1.

Если для любой пары кортежей (s„,/i = l¿,..,«) и (sh,/i = 1,2,...,п), соответствующих сцепленным нетерминальным символам sa и í4, {^..rje Rí4 исходной грамматики не найдётся разряда, в котором бы кортежи совпадали, то функциональная связность L(G„V) параллельной декомпозиции автоматной

грамматики равна нулю.

В этом случае не выполняется соотношение (6). Теорема 2.

Если для пары кортежей = 1.2,...,и) и (^,// = 1,2,...,и), соответствующих

,1 X. Х>

сцепленным нетерминальным символам sa и s6, \sa,sb)e R^, sa-*sa, sb-+sfi,

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

состояние при переходах из s„ при терминальном символе Хк и из sh - при Хк,

ХксХк, то нарушение автоматности в /-м автомате-сомножителе не

происходит

В этом случае не выполняется соотношение (7).

На основании теоремы 1 синтез параллельной декомпозиции управляющих автоматов сведён к вложению графа сцепления G^ исходной автоматной грамматики в специальный граф GK(n,k) - кластер, однозначно определяемый значностью к применяемой логики и её размерностью п соответствующего пространства Р(п,к); рассмотрим это пространство Р(п,к).

Построим кластер GK, состоящий из точек {Z,} этого пространства, каждая пара которых {2,,^} соединены ребром, если векторы Z¡, 2j имеют различные значения в каждом разряде /, z„ * zJt, / = 1,2,...,л.

Кластеры GK при и = 2 для к = 2, 3, 4 представлены соответственно на рис. 1, а, б, в соответственно. Теорема 3.

Произведение кластеров {GK,(n„kl)/i = 1,2,...,5} является кластером вида

GK{{nl,n2,...,n!\{kl,k1,...,k,))-

ПС„(и,Д) = GK{(n,/i = 1,2= 1,2,...,л)), (рис. 2). (8)

»i

(00) т 1 (01) I

„1 1 (10)

(21Г"

а) 0,(2,2)

б) 6К(2,3)

в)

Рис. 1. Вид кластеров в двумерном пространстве для 2,3,4 значной логики

11

(02)

12

101 •

101

0,(1,2)хО,(и) = ОЛ(1,1),(2,3))

а)

0,(12)^,(1,4) = Ок ((1ДХ(2,.4)) б)

ООО

(23^---------101

ОЛ1,3)хОЛ1,4)= ¿Ш1МЗ,4)) С,(2,2)ХС(с(1,3)-СЛ(2Д),(2,3))

Б) г)

Рис. 2. Вид кластеров получаемых в результате произведения кластеров Исследуем свойства кластеров в зависимости от значности логик к, и размерности пространств и,.

Нетрудно доказать следующие утверждения.

Теорема 4. Мощность носителя кластера 0К(п,к) равна к":

У(0К)\ = к*. (9)

Следствие.

Мощность носителя кластера равного декартову произведению кластеров {0К(п„к,)/1= 1,2,...,«} равна '■

(ПС*М,)] = П*Г

(10)

Теорема 5 Кластер GK(n,k) является единственным в пространстве Р(п,К) и однородным степени s(G'J, равной (к -1)":

s(GK) = (k-\)\ (11)

Следствие 1. Запрещённой фигурой функциональной несвязности нетерминальных символов в пространстве Р(п,К) является звезда Q, степени

= (*-D"+1- (12)

Следствие 2. Для булевой логики, если граф сцепления G является паросочетанием (рёберно-пустым графом), то существует функционально несвязное кодирование нетерминальных символов.

Теорема 6.

Кластер GK представляющий собой декартово произведение кластеров {(Д (nrk,)/t = 1,2.....является однородным степени s(GA), равной (к, -1)" :

í(Gr)-n(*, -iy. (13)

/-1

Теорема 7. Плотность p(GK(n,K)) кластера GK{n,K) равна значности логики

к:

P(GK{n,K))-k. (14)

Доказательство. Значение каждого разряда z, кодирующего вектора Z(i), г, с Z(v ) получается путём перестановки, быть может циклической, значений к-значной логики {0, 1, 2, ..., к-1}. Следовательно, плотность кластера равна числу переставляемых значений, т.е. к, p(GK) = к.

Следствие 1. Плотность p(GK) кластера, являющегося декартовым произведением кластеров (и,,А,)//" = 1,2,...,5} равна плотности кластера-сомножителя, у которого значность логики минимальна:

p(Gk) = núak,. (15)

Коэффициентом сцепления Кщ{йК(п,К)) кластера GJn.K) называется максимальное количество вершин, общих для двух полных подграфов Fu, Fh е GK(n,K) плотности k\

K^Gy(n,K)) = k-2. (16)

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

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

Вложение одного графа в другой Ср сводиться к определению

максимальных по числу рёбер изоморфных подграфов Оа, 0о с в„ и 5р,

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

п.1. Фиксируем вершину г„с максимальной степенью графа (7,„,

) = тах ), V £ V, и ярусно упорядочиваем граф Осн, (7,( с С„ относительно

этой вершины:

1-й ярус включает вершину ,

2-й — вершины {v,l/v|l еГ\},

3-й — вершины \ун/г1 еГу/2|,... /-Й —вершины {»<#ДЙ 6Гу((( „}.

п.2. Строим вектор длины 2/ + 1, в котором каждый разряд показывает количество рёбер и вершин внутри каждого яруса и между ними.

(О ,№{) (МР],Рг) №Р2,Ш2) ........................(Мр:Ж)

где Ыр1 - число рёбер в г-м ярусе, Мв, - число вершин в г-м ярусе,

- число рёбер между г-м и (г +1)-м ярусами. п.З. В кластере определяем вершину со степенью не меньшей = который определяет 1-й ярус выделяемого в кластере О, подграфа дк.

п.4. Определяем

2-й ярус — вершины /5^ е

3-й ярус — вершины ^ е Г7,2},...,

'-й ярус — вершины ^„/^ так чтобы вектор, показывающий

количество включений рёбер и вершин подграфа ёк совпал с вектором, полученным в п.2.

п.5. Если векторы, полученные в п.2. и п.4. совпали, переходим к п.6, в противном случае к п.7.

п.6. Согласно ярусному упорядочиванию графов бч и устанавливаем изоморфизм г] между их носителями и производим его проверку. Если изоморфизм подтвердился, то граф ёсц вложим в кластер , б^ сО,. В подграф с?и добавляем рёбра графа концы которых {у,,^} закодированы векторами г(иХ г^), имеющие различные значения в каждом разряде (выполнение теоремы 1), или если в каждом разряде, в котором векторы ), имеют одинаковые значения, то в соответствующих разрядах векторов г(л0), 2{з0) то же - одинаковые значения (выполнения условий теоремы 2). п.7. Графы Ссч и , определяемый вершиной уа, не изоморфны. п.8. Переходим к п.З, выбирая в качестве уа другую вершину со степенью не меньшей з0о), если не рассмотрены все вершины, в противном случае переходим к п.9.

п.9. Рёбра графа <7ч, не вошедшие в подграф <5,_, 0,.ц с , определяют сужение графа сцепления, реализуемое штриховкой сцепляющих входных векторов, которая реализуется двумя способами. Первый способ заключается в конкатенации вектора Хк, который взвешивает удаляемое ребро состоянием 1-го автомата-сомножителя, которым отличаются кортежи состояний ..,*,„...*,,) и 5,

Второй способ состоит в расширении разрядности выходных векторов путём введения выходного канала штриховки /(.$,), который устанавливается в соответствующее состояние на всех переходах во внутренние состояния 5„ и которые определяют сужение сигнатуры графа сцепления.

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

обладающим свойством параллельной декомпозируемое™. Суммарное

12

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

Перед применением предлагаемой параллельной стратегии проектирования параллельной декомпозиции управляющих автоматов формируется кластер, имеющий наиболее близкие параметры по вершинному и рёберному ресурсам, а так же по локальным топологическим параметрам (по степеням кластера) к параметрам вкладываемого графа сцепления. Для выполнения этого пункта формируется кластерная база знаний, имеющая реляционную структуру. Мера близости д(о<г,СС1()между кластером GK ={VK,UK)

и графом Gcli =(у^,исц\ сцепления определяется как среднеквадратичное

отклонение среднего значения степеней scp(v) графа сцепления v е У1Ц от

степени s(GK) кластера G,:

(17)

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

Разработанное математическое обеспечение проектирования минимальносвязной параллельной декомпозиции управляющих автоматов доведено до программной реализации операционных модулей "КЛАСТЕР", "БЛИЗОСТЬ", "УПОРЯДОЧИВАНИЕ", "ИЗОМОРФИЗМ", "ШТРИХОВКА-1", "ШТРИХОВКА-2", "СОМНОЖИТЕЛЬ" и управляющего модуля "ДИСПЕТЧЕР".

Разработанные модули легко преобразуются в библиотеки динамического

подключения (DLL), в компоненты объектного программирования (СОМ,

DCOM, ActivX и т.д.). Так как при создании программного кода не

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

конструкции, которые отвечают стандарту ANSI С, то использование кода

становится возможным на любых типах платформ: от специальных

13

микропроцессоров, до широко распространенных процессоров фирмы Intel, AMD и др., соответственно, и в любых операционных средах поддерживаемых этими процессорами.

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

Система содержит четыре полугазовых топки, установки подачи топлива, воздуха и установку удаления шлака. Схема полугазовой топки представлена на рис. 3, на котором числами обозначены: 1 - конвейер, 2 - плужок, 3 - входной бункер, 4 - топливо, 5 - питатель, 6 - забрасыватель, 7 - полугаз, 8 - подача воздуха, 9 - рабочая камера, 10 - шлак, 11 - слой свежезаброшенного топлива, 12- зона восстановления, 13- зона горения, 14- зона шлака, 15-колосниковая решётка.

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

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

Рис. 3. Схема полу газовой топки Рис. 4. Схема каналов управления

Система сжигания имеет следующие каналы (рис. 4), представляющие ^ собой микрооперации при проектировании управляющего автомата:

К1 - пуск и останов процесса газификации, ) К2 - индикация работы процесса газификации,

,, КЗ - пуск и останов заполнения входных бункеров,

К4 - индикация заполнения входных бункеров, К5 - пуск и останов подачи топлива в топки, Кб - индикация подачи топлива в топки, К7 - приостанов газификации в первой топке, К8 - индикация состояния канала К7, К9 - приостанов газификации во второй топке, К10 - индикация состояния канала К9, К11 — приостанов газификации в третьей топке, К12 - индикация канала К11, К13 - приостанов газификации в четвёртой топке, ? К14 - индикация состояния канала К13,

i К15 - плужок первой топки,

J К16 - плужок второй топки,

К17 - плужок третьей топки, К18 - плужок четвёртой топки, К19 - конвейер,

К20 - К23 - питатели первой,..., четвёртой топки соответственно,

К24 - К27 - забрасыватели,

К28 - КЗ 1 - клапаны подачи вторичного воздуха,

К32 - К35 - датчики верхнего уровня во входных бункерах,

К36 - К39 - датчики нижнего уровня во входных бункерах,

К40 - К43 - датчики подачи топлива,

К44 - К47 - индикация аварии установки заполнения входных бункеров, К48 - К51 - индикация аварии установки подачи топлива в печи, К52 - пуск и останов процесса управления, К53 - индикация управления,

К54 - начальные установки исполнительных элементов. На этом рис. 3,4: 1 - конвейер, 2 - плужок, 3 - входной бункер, 4 - система подачи топлива, 5 - топка, 6 - клапан подачи воздуха, 7 - общий клапан.

Перечисленное множество каналов включается во множество терминальных символов. Кроме этого во множество могут быть включены дополнительные элементы, являющиеся идентификаторами входных, внутренних и выходных каналов, введенных для получения эффективного автоматного управления. Исходя из информации, полученной от технолога, определяется причинно-следственные связи вида А~*В, которые определяют автоматную грамматику. Мощным средством оптимизации всей структуры автомата является абстрактная декомпозиция автоматов, особенно параллельная декомпозиция автоматов. Необходимость поиска когорой, с одной стороны, диктуется современными требованиями, предъявляемыми к быстродействию управления, что вызывает необходимость параллельного управления объектом, с другой стороны, повышение безотказности автоматного управления требует разбиения автомата на ряд функционально несвязных друг с другом автоматов меньшей размерности, обеспечивающих реализацию полученного автоматного оператора. Разработанные программные средства и решают эту задачу.

Фрагмент графа переходов GMp = (V„,U„), соответствующего рассматриваемому проекту, представлен на рис. 5, граф сцепления - на рис. 6.

Для синтеза параллельной декомпозиции выбираем трёхзначную логику в пространстве Р{2,3), так как кластер GK(2,3) наиболее близок согласно (17), к графу сцепления (рис. 6): a(gî,Gc,)=2.

а,

Рис. 5. Граф переходов

Л

Рис. 6. Граф сцепления

(*,)-(*,) (Л,)-(«;

(21).

021—(00) 02)—АО)

— - - у

(015-

422)

а) б)

Рис. 7, Ярусно упорядоченные кластер и граф счепления Произведя вложение подграфа сцепления 5сч = (Уа1,иа1} (рис. 7,а) в кластер

Ок(2,з), т.е. построив подграф кластера 6К = (Ук,ик} (рис. 7,6), который изоморфен подграфу дк ^-изоморфизм, и имеет максимальную

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

Нетерминальные символы, не вошедшие в подграф Ссц, $$ и 1У7 кодируем неиспользованными кодами 20 и 11 соответственно.

В результате вложения графа сцепления в кластер 2,3) получены соответствия между нетерминальными символами исходной автоматной грамматики и парами нетерминальных символов (а„Д) грамматик, определяющих графы переходов (рис. 9, а) и 0П1р2 (рис. 9, б) автоматов-сомножителей, декомпозирующих исходный автомат.

10

12

(5)-($) Г-1-г',

12 22

22

21

<5>—'51 22 22

(*.)—!—г*-IV, 21 02

ф-10

01

4' = 4-г°2

-(7Г> 4" = 4т|,

11 10 Рис. 8. Штриховка терминальных символов 5,<->(а„Д), а„р,= 0.1.2:

51-(1,0), 52-(0,1), 5з -(2,2), 54-(2,1), 55-(2,0), 56-(0,0), 57-(1,1), 58 "(0,2), 5,-(0,2).

4"\т/8

0У2У7

(Л/4У7

1 \Z2V8

0У1Л/5У6

ЗУ6У8

1У7

а)

б)

Рис. 9. Автоматы-сомножители, декомпозирующие исходный автомта Минимальная связность рассмотренного проекта, согласно выражению (2), равна 6. При разработке этого проекта использовалась стратегия предельного разложения — определялись минимальносвязные коды внутренних состояний автомата управления исполнительными механизмами газового хозяйства завода.

Разработанный программный пакет автоматизированного проектирования успешно внедрён в Главном управлении НПО "Специальная техника и связь" МВД РФ и Научно-техническом производственном центре "Альтаир" при реальном проектировании систем мониторинга дорожно-транспортных ситуаций г. Москвы и Московской области и морских акваторий Российской Федерации соответственно, работающих в реальном масштабе времени и требующих высокую производительность и отказоустойчивость.

Заключение

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

Основные выводы и научные результаты работы:

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

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

3. Исследованы свойства кластеров и найдена характеризация их структур, оформленных в виде реляционной базы знаний.

4. Предложена эффективная процедура вложения в кластер графа сцепления при минимальном сужении его сигнатуры.

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

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

6. Созданное математическое обеспечение проектирования минимальносвязной параллельной декомпозиции управляющих автоматов доведено до программной реализации на основе использования стандарта ANSI С, что позволило легко преобразовать её разработанные модули в библиотеки динамического подключения (DLL), в компоненты объектного программирования (COM, DCOM, ActivX и т.д.) при синтезе параллельной декомпозиции управляющих автоматов с допустимой мощностью нетерминальных символов до 4096 со скоростью обработки одного нетерминального символа в среднем до 0,1 с.

7. Разработанный программный инструментарий успешно внедрён в Главном управлении НПО "Специальная техника и связь" МВД РФ и Научно-техническом производственном центре "Альтаир" при реальном проектировании систем мониторинга дорожно-транспортных ситуаций г. Москвы и Московской области и морских акваторий РФ соответственно, работающих в реальном масштабе времени и требующих высокую производительность и отказоустойчивость, о чём имеются соответствующие акты о внедрении.

Основные положения диссертации опубликованы в следующих работах:

1. Калитин Д.В. Применение k-значных логик при разработке систем управления технологическими процессами систем обогащения, Информационная математика №1, Физматлит, М.2001, с. 150-153;

2. Калитин Д.В. Характеризация функциональной несвязности не1ерминальных символов автоматных грамматик в k-значных логиках, Информационная математика №1(3), Физматлит, М.2003, с. 33-36;

3. Калитин Д.В. Вложение графа в кластер функциональной несвязности нетерминальных символов автоматной грамматики, Информационная математика №1(3), Физматлит, М.2003, с. 36-38;

4. Горбатов A.B. Калитин Д.В. Минимизация функциональной связности нетерминальных символов автоматных грамматик в k-значных логиках, Информационная математика №1(3), Физматлит, М.2003, с. 38 -44;

5. Горбатов A.B., Калитин Д.В. Проектирование слабосвязанных параллельных декомпозиций автоматов управления энергосберегающими технологиями, Информационная математика №1(4), Физматлит, М.2004, с. 46-56;

6. Горбатов А.В, Калитин Д.В. Кодирование минимальносвязных нетерминальных символов автоматной грамматики. Информационная математика №1(5), АСТ-Физматлит, М.2005, с. 36-48.

Подписано в печать 24.03.05 Формат 60x90/16 Объём 1 пл. Тираж 100 экз. Заказ №963

Типография МГТУ. Ленинский пр., 6

ош-о 5. &

РНБ Русский фонд

2005-4 39688

Введение.

Глава 1. Подходы к проблеме проектирования параллельной декомпозиции управляющих автоматов (ПДУА).

1.1. Синтаксический подход.

1.2. Семантический подход.

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

1.4. Расширение терминальных символов.

1.5. Вычисление сложности функциональной декомпозиции.

1.6. Выводы по первой главе.

Глава 2. Параллельная стратегия синтеза предельной параллельной декомпозиции автоматов.

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

2.2. Кластеры, их структура и свойства.

2.3. Параллельная стратегия синтеза связной предельной параллельной декомпозиции в трёхзначной логике.

2.4. Выводы по второй главе.

Глава 3. Параллельная стратегия проектирования минимальносвязной ПДУ А.

3.1. Произведение кластеров, их структура и свойства.

3.2. Технология параллельной стратегии проектирования минимальносвязной ПДУ А.

3.3. Программный инструментарий параллельной стратегии проектирования минимальносвязной ПДУА и его внедрение.

3.4. Выводы по третьей главе.

Глава 4. Автоматизированное проектирование реальных минимальносвязных ПДУА.

4.1. Трёхзначный однородный нейрон сотовой структуры и его проектирование.

4.2. Автоматизированное проектирование автоматного управления системой сжигания твёрдого топлива в плотном слое.

4.3. Автоматизированное проектирование логической компоненты системы мониторинга морской акватории.

4.4. Выводы по четвёртой главе. 131 Заключение. 132 Литература.

Повышение производительности и безотказности цифровых бортовых систем, систем жизненного обеспечения горного, морского, космического базирования и других информационно-вычислительных комплексов определяет необходимость автоматизированного проектирования параллельно функционирующих управляющих автоматов с ослабленной, в пределе минимальной, связностью. [2, 10, 12-26] Эта проблема, как проблема проектирования параллельной декомпозиции управляющих автоматов, впервые была поставлена Дж. Хартманисом (1961 г.), для решения которой им был предложен специальный алгебраический аппарат разбиений внутренних состояний автомата (нетерминальных символов) со свойством подстановки (СП-разбиений). Развитие этого аппарата совместно с Р. Стирнсом привело к созданию алгебры пар, явившейся математической основой результатов, связанных с построением параллельной декомпозиции автоматов. Недостатками этого подхода являются комбинаторный перебор возможных разбиений и малая доля автоматов, обладающих свойством подстановки и процедура, основанная на алгебре пар, по существу, является процедурой не проектирования, а распознавания свойства подстановки автомата, которая, быть может, только на последнем шаге преобразования даст отрицательный результат, т.е. что автомат не обладает свойством подстановки и не может быть построен. [6, 15, 42, 44, 50]

Для устранения этих недостатков японскими учёными К. Нобуёки, А. Тадаши, Е. Нориоши (1974 г.) [7] было предложено расширение алгебры пар до алгебры троек, четвёрок, ., n-ок, но аппарат расширенных алгебр не устранил недостатки алгебры пар. Модификации этого подхода, проведённые отечественным учёными (70-е годы) А.Н. Мелиховым, О.П. Кузнецовым, В.Г. Лазаревым, Е.И. Пийль, Э.Б. Ершовой и др. так же не привели к положительным результатам. [3, 4, 5, 9, 38-56, 57]

Цель работы

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

Идея работы

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

Задачи исследования:

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

• Определить топологию кластеров с размерностью равной п и значностью к, а так же их суперпозицию по мультипликативной связке;

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

• Найти запрещённые фигуры вложимости графа сцепления автоматной грамматики в кластеры, являющиеся декартовым произведением кластеров размерностью п и значностью к;

• Разработать алгоритм вложения графа сцепления в кластер при минимальном сужении сигнатуры графа сцепления;

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

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

Методы исследований

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

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

Защищаемые научные положения и их новизна

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

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

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

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

Научное значение состоит в следующем:

• Развита декомпозиционная теория параллельно функционирующих управляющих автоматов с учётом минимизации их функциональной связности;

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

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

Практическая ценность заключается:

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

• В эффективном внедрении разработанного программного инструментария в реальное производство цифровой аппаратуры в ГУ НПО "Специальная техника и связь" МВД РФ и

ЗАО НПЦ "Альтаир" о чём имеются соответствующие акты о внедрении.

Апробация работы

Основные результаты работы были обсуждены:

• на конференциях, проводимых РАЕН, международной академией информатизации и МГГУ: "Логическое управление. Характеризационный анализ. САПР", М, 1999 г.; "Логическое управление. Характеризационный анализ. САПР", М, 2003 г., "Характеризационный анализ. Нейронные технологии. САПР", М, 2005 г.;

• на семинарах отделения "Теоретическая информатика и информационные технологии и стратегии" Международной академии информатизации.

Публикации

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

Объём и структура работы

Диссертационная работа состоит из введения, 4 глав и заключения, содержит 20 таблиц, 53 рисунка и список литературы из 83 наименований.

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

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

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

Главный конструктор

ОКР "Р—С", канд. техн. наук

Заключение

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

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

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

3. Исследованы свойства кластеров и найдена характеризация их структур, оформленных в виде реляционной базы знаний.

4. Предложена эффективная процедура вложения в кластер графа сцепления при минимальном сужении его сигнатуры.

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

6. Созданное математическое обеспечение проектирования минимальносвязной параллельной декомпозиции управляющих автоматов доведено до программной реализации на основе использования стандарта ANSI С, что позволило легко преобразовать её разработанные модули в библиотеки динамического подключения (DLL), в компоненты объектного программирования (COM, DCOM, ActivX и т.д.) при синтезе параллельной декомпозиции управляющих автоматов с допустимой мощностью нетерминальных символов до 4096 со скоростью обработки одного нетерминального символа в среднем до 0,1 с.

7. Разработанный программный инструментарий успешно внедрён в Главном управлении НПО "Специальная техника и связь" МВД РФ и Научно—техническом производственном центре "Альтаир" при реальном проектировании систем мониторинга дорожно-транспортных ситуаций г. Москвы и Московской области и морских акваторий РФ соответственно, работающих в реальном масштабе времени и требующих высокую производительность и отказоустойчивость, о чём имеются соответствующие акты о внедрении.

Утверждаю"

Генеральный директор научно-технического производственного центра "Лльтаир", академик НЛ,

•4

ЖВ. Воскресенский "23" марта 2005г.

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

1. Горбатов В.А., Кафаров В.В., Павлов П.Г. Логическое управление технологическими процессами. М.: Энергия, 1978.

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

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

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

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

6. Hartmanis J., Stearns R.E. Pair algebra and its application to automata theory. — Information and Control, 1964, №7.

7. Kurose Nobuyuki, Ae Tadashi, Yoshida Noriyoshi. An extension of pair algebra/ Bull/ Fac/ Eng/ Hirosima Univ., 1974.

8. McCluskey E.J., Unger S.H. A note on the number of internal variable assignments for sequential switching circuits. — IRE Trans. On Electonic Computers, 1959.

9. Миллер P. Теория переключательных схем.: Наука,1970.

10. Оллонгрен А. Определение языков программирования интерпретирующими автоматами. М.: Мир, 1977.

11. Горбатов В.А. Семантическая теория проектирования автоматов. М.: Энергия, 1980.

12. Горбатов В.А. Фундаментальные основы дискретной математики. М.: Наука, 1999.

13. Горбатов В. А. Дискретная математика. М.: ООО "Издательство ACT", 2003.

14. Горбатов А.В. Характеризационная теория синтеза функциональных декомпозиций в k-значных логиках. М.: ООО "Издательство ACT", 2000.

15. Huffman D.A. The synthesis of sequential switching circuits// J. of the Franklin Inst 1954. Vol. 257. №3. P. 161-190; №4. P. 275-303.

16. Питерсон Дж. Теория сетей Петри и моделирование систем. М. Мир., 1984.

17. Kochen М. Extension of moore-shannon model for relay circuits//IBM Journ. Res. and Devel. 1959. Vol. 3. №2. P. 169-186.

18. Щукин А.А. Промышленные печи и газовое хозяйство заводов, М., Энергия, 1973.

19. Андерсон Р. Доказательство правильности программ. М. Мир., 1982.

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

21. Горбатов В.А. Теория частично упорядоченных систем. М. Советское радио, 1976.

22. Кузьмин С.З. Основы теории цифровой обработки радиолокационной информации, М., Советское Радио, 1974, 432с.

23. Рякин О.М., Скворцов И.В. Логические модели абстрактных типов данных при проектировании программ на языках высокого уровня. Материалы VII симпозиума "Логическое управление в промышленности", Ижевск, 1984.

24. Рякин О.М. Модельный подход к формальному определению ошибок проектирования. Материалы VII симпозиума "Логическое управление в промышленности", Ижевск, 1984.

25. Zvi Kohavi. Secondary state assignment for sequential machines// IEEE Trans/ on Electronic Сотр. 1964. Vol. EC-13. №3. P. 193-203.

26. Гусева А.И., Кольцов Д.В. Распределённые системы: декомпозиция и синтез. Материалы 17 Международного симпозиума "Логическое управление. Интеллектуальные информационные технологии и стратегии", Москва, Международная академия информатизации, 1994.

27. Серджвик Р. Фундаментальные алгоритмы на С. Алгоритмы на графах. СПб, ООО "ДиаСофтЮП", 2003.

28. Подбельский В.В. Язык С++, М. Финансы и статистика,1996.

29. Liu С. N. A state variable assignment method for asynchronous sequential switching circuits// ACM. 1963. Vol. 10. №2. P. 209-216.

30. Стивене У. UNIX: взаимодействие процессов, СПб, Питер, 2002.

31. Кейт Г. Использование Visual С++, М. "Вильяме", 1999.

32. Черносвитов A. Visual С++ и MFC, СПб, Питер, 2000.

33. Жоффрэн И. Кодирование внутренних состояний и декомпозиция последовательностных синхронных устройств в сб. "Булева алгебра и конечные автоматы", М. Мир., 1969, 114-152.

34. Круглов В.В., Борисов В.В. Искусственные нейронные сети. М. Телеком, 2001.

35. Mealy G. Н. A method for synthesizing sequential circuits// BSTJ. 1965. Vol. 34. №5. P. 1045-1079.

36. Агафонов B.H. Синтаксический анализ языков программирования. Уч. пособие, Новосибирск, НГУ, 1981. 91 с.

37. Paul М., Unger S. Н. Minimizing the number of states in incompletely specified sequential switching functions// IRE Trans, on Electronic Сотр. 1959 Vol. EC-8. №3. P. 356-367.

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

39. Гладкий А.В. Формальные грамматики и языки. М.: Наука, 1973. 368 с.

40. Сигеру Омату, Марзуки Халидб Рубия Юсуф, Нейроуправление и его приложения, ИПРЖ "Радиотехника", М. 2000, 272с.

41. Гросс М., Лантен А. Теория формальных грамматик. М.: Мир, 1971.294 с.

42. Hartmanis J. On the State Assignment Problem for Sequential Machines I. IRE Transactions on Electronic Computers. Vol. EC-10, No.2, pp. 157-165.

43. Мартыненко Б.К. Синтаксически управляемая обработка данных. С.Пб: изд. СПбГУ, 1997. 362 с.

44. Hartmanis J. Loop-free structure of sequential machines// Information and Control, 1962. Vol. 5. №1. P. 25-43.

45. Ramamoorthy С. V., Ho G. S., Performance evaluation of asynchronous concurrent systems using petri nets, IEEE Trans. Software Eng., Vol. SE-6, №5, P. 440-449, 1980.

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

47. Языки и автоматы. Сб. переводов. М.: Мир, 1975. 358 с.

48. Greibach S.A. A note on undecidable properties of formal languages // Math. Systems Theory, 2, pp. 1-6.

49. Salomaa A. Formal languages. N.Y., 1973.

50. Stearns R. E., Hartmanis J., On the state assignment problem for sequential machinesll, IRE Trans. Elect. Comput., 1961, Vol. EC-10, №4.

51. Мартыненко Б.К. Языки и трансляции. СПб., СПбГУ,2001.

52. Hopcroft J.E., Ullman J.D. Formal languages and their relation to automata. Addison-Wesley Pub. Co., Inc. 242 p.

53. Шамашов M.A. Теория формальных языков. Грамматики и автоматы. Учебное пособие. Самара: Университет Наяновой, 1996.

54. Штернберг Л.Ф. Теория формальных грамматик. Учебное пособие.- Куйбышев: КуАИ, 1979.

55. Шамашов М.А., Штернберг Л.Ф. Синтаксический анализ автоматных языков. Куйбышев: КуАИ, 1990.

56. Кузин Л.Т. Основы кибернетики: В 2-х т. Т.2. Основы кибернетических моделей. Учеб. пособие для вузов. М.: Энергия, 1979.- 584 с.

57. Кузнецов О.П. и др. Дискретная математика для инженера. М.,1988.- 480с.

58. Донован Дж. Системное программирование. М.: Мир,1975.

59. Брой М. Информатика. Теоретическая информатика, алгоритмы и структуры данных, логическое программирование, объектная ориентация: В 4-х чч. 4.4. М.: Диалог-МИФИ, 1998.-224с.

60. Методы нейроинформатики: Сб.научн. трудов / Под ред. А.Н.Горбаня. Красноярск: КГТУ, 1998.- 204с.

61. Карпов Ю.Г., Теория автоматов, СПб. Питер, 2002.

62. Кудрявцев В.Б., Алешин С.В.,Подколзин А.С. "Введение в теорию конечных автоматов".- М.: Наука, 1985 г.

63. Sasao Т., Input variable assignment and output phase optimization of PLA's, IEEE Trans, on Comput. Vol. C-33, №10, P. 879-894, 1984.

64. Автоматы, Сборник статей под редакцией Маккарти и Шеннона, ИЛ, Москва, 1956

65. Кудрявцев В.Б., О мощностях множеств предполных классов некоторых функциональных систем, связанных с автоматами, ДАН СССР т. 151,N3,1963, с.493-496.

66. Бабин Д.Н., Вербальные подавтоматы и задача полноты, Вестник МГУ, Математика и механика, 1985, N 3, с.82-85.

67. Летичевский А.А., Условия полноты для конечных автоматов, Вычислительная математика и математическая физика, N 4,1961, с.702-710.

68. Бабин Д.Н., Разрешимый случай задачи о полноте автоматных функций, Дискретная математика, том 4, 1992, выпуск 4, с.41-56, Наука, Москва.

69. Бабин Д.Н. О полноте двухместных о.д.-функций относительно суперпозиции, Дискретная математика, том 1, 1989, вып. 4, с. 86-91, Наука, Москва.

70. Глушков В.М. Синтез цифровых автоматов, Наука, Физматлит, М., 1980.

71. Витушкин А.Г., Хенкин Г.М. Линейные суперпозиции функций. — Успехи матем. наук, 1967, т.22, вып. 1, стр.77-124.

72. Марченков С.С. Об одном методе анализа суперпозиций непрерывных функций. — Проблемы кибернетики., вып.37, М:Наука, 1980, стр.5-17.

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

74. Успенский В. А. Теория алгоритмов. М.: Наука.

75. Гэри, Джонсон. Вычислительные машины и трудно решаемые задачи. М.: Мир.

76. Савельев А.Я. Прикладная теория цифровых автоматов. Учебник для вузов-М. Высшая школа, 1987, 272с.

77. Брауэр В. Введение в теорию конечных автоматов. Перевод с английского под редакцией Ю.И. Журавлева-М. Радио и связь, 1987, 392с.

78. Каган Б.М. Электронные вычислительные машины и системы .-М. Энергоавтомиздат, 1988, 551с.

79. Савельев Н.В., Коняхин В.В. Функционально-логическое проектирование БИС.-М. Высшая школа, 1990, 156с.

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

81. Бухараев Р.Г. Вероятностные автоматы, Казань, Изд. КГУ, 1970.

82. Глушков В.М. Логическое проектирование дискретных устройств, Киев, 1987.

83. Автоматизация проектирования систем управления, Финансы и статистика, М., 1982,204 с.

84. Калитин Д.В. Применение k-значных логик при разработке систем управления технологическими процессами систем обогащения, Информационная математика №1, Физматлит, М.2001, с. 150-153;

85. Калитин Д.В. Характеризация функциональной несвязности нетерминальных символов автоматных грамматик в к-значных логиках, Информационная математика №1(3), Физматлит, М.2003, с. 33-36;

86. Калитин Д.В. Вложение графа в кластер функциональной несвязности нетерминальных символов автоматной грамматики, Информационная математика №1(3), Физматлит, М.2003, с. 36-38;

87. Горбатов А.В. Калитин Д.В. Минимизация функциональной связности нетерминальных символов автоматных грамматик в k-значных логиках, Информационная математика №1(3), Физматлит, М.2003, с. 38-44;

88. Горбатов А.В., Калитин Д.В. Проектирование слабосвязанных параллельных декомпозиций автоматов управления энергосберегающими технологиями, Информационная математика №1(4), Физматлит, М.2004, с. 46-56;

89. Горбатов А.В, Калитин Д.В. Кодирование минимальносвязных нетерминальных символов автоматной грамматики. Информационная математика №1(5), АСТ-Физматлит, М.2005, с. 36-48.