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

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

ДЗУГКОЕВА АННА АЛЬБЕРТОВНА

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

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

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

Владикавказ - 2007 г

003161353

Работа выполнена на кафедре "Информационные системы в экономике" Северо-Кавказского горно-металлургического института (государственного технологического университета)

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

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

Ведущее предприятие:

докт техн наук, профессор Пагиев Казбек Хазбиевич

докт физ мат. наук, профессор Анатолий Георгиевич Кусраев докт техн. наук, доцент Елена Александровна Хадзарагова

Кабардино-Балкарский государственный университет

Защита диссертации состоится 9 ноября 2007 г в 14м час на заседании диссертационного совета Д 212 246 01 в Северо-Кавказском горнометаллургическом институте (государственном технологическом университете)

Отзывы (в двух экземплярах, заверенные печатью) просим направлять по адресу 362021, PCO-Алания, г. Владикавказ, ул Космонавта Николаева, 44, Ученый Совет СКГМИ (ГТУ)

С диссертацией можно ознакомиться в библиотеке СКГМИ (ГТУ) Автореферат разослан 8 октября 2007 г Ученый секретарь

диссертационного Совета Д 212 246 01 gc&rroP технических наук, доцент „

В.П. Алексеев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность работы.

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

Создание САПР систем логического управления (СЛУ) сопряжено с необходимостью решения большого класса оптимизационных задач, часто комбинаторной сложности, что порождает проблему уменьшения их размерности декомпозицией При решении этой и других проблем разработки САПР СЛУ наиболее эффективной моделью последних является их конечно-автоматное представление Проблемы разработки и оптимизации автоматных моделей систем управления, в том числе декомпозиционной теории их синтеза широко освящены в работах как отечественных ученных Гаврилов М А , Глушков В М, Горбатов В А , Мелихов А Н, Кузнецов О П и др , так и зарубежных Дж Хартма-ниса, Р Стирнса, Ф Хона, 3 Кохави и др

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

Ч \ / ч /

4 /

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

- разработка метода нахождения размещения состояний заданного автомата по стандартной компоненте разложения

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

- разработка алгоритмов реализации предложенных методов

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

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

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

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

- сформулирована и доказана теорема существования размещения состояний заданного автомата по стандартной компоненте разложения,

- предложен способ использования декартова произведения графоидов заданного и стандартного автоматов для нахождения эквивалентного расширения носителя графоида заданного автомата, позволяющего построить размещение по стандартной компоненте разложения,

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

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

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

Обоснованность и достоверность научных положений, выводов и рекомендаций подтверждается соответствием результатов работы внедренной САПР результатам проведенного имитационного моделирования

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

Результаты работы внедрены на НПК «Югцветметавтоматика» при разработке АСУ процессом обжига электродного производства на ОАО «Новочеркасский электродный завод», что позволило получить экономический эффект в размере 570000 руб в год Основные научные и практические результаты используются в учебном процессе СКГМИ(ГТУ) при чтении лекций и проведении практических занятий по дисциплинам «Дискретная математика» и «Теоретические основы построения САПР»

Апробация работы. Основные результаты проведенных в диссертации исследований докладывались на межкафедральном научном семинаре «Декомпозиционная теория синтеза систем логического управления», на ежегодных научно-технических конференциях СКГМИ (ГТУ) (2004-2007 гг ), Международной научно-практической конференции «Системный анализ в проектировании и управлении» (Санкт-Петербургский государственный политехнический университет), У-й Международной конференции «Устойчивое развитие горных

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

Связь с государственными программами. Основные исследования выполнялись в рамках аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы» (2006 - 2008 г.)

Публикации. Основное содержание диссертационной работы опубликовано в 5-ти печатных работах

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка использованной литературы из 87 наименований и 2 приложений. Общий объем диссертации 132 страницы, включая 49 рисунков и 4 таблицы.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении обоснована актуальность темы исследования, сформулирована цель работы, описана структура работы

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

На основе сравнительного анализа определены условия предпочтения тех или иных подходов

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

Пусть задан автомат Л графоидом А = (X,S,SJ е 5, И) и требуется найти его представление параллельным функционированием двух автоматов В = (Х,¥,Р) и С = (Х, Ж, /?), из которых один, допустим В, задан, то есть требуется найти автомат С, такой, что Ас. ВхС В этом случае, поскольку одна компонента задана, одно из искомых подстановочных разбиений л = ,5,, ,5„} (п<ц, у = \У\) должно соответствовать заданной компо-

ненте, т е.

Для построения разбиения я предлагается использовать декартово произведение й = АхВ, <3 = {Х,2,и) (г V )

Теорема Для того чтобы существовало СП-разбиение соответствующее заданной компоненте разложения В, необходимо и достаточно, чтобы С? = А х В был изоморфным продолжением А

Доказательство Пусть разбиение к существует, т е (1) истинно, тогда из определения декартова произведения и (1) следует

т е между вершинами графоида А и подмножеством вершин (7 существует взаимнооднозначное соответствие , которое переводит А в О'сС Необходимость доказана

\fl,J,k{slsSa,sJ е^Д* =*,) ^а,ур{уаХк =хр)

(1)

(2)

Пусть графоид А изоморфно вложим в О, т.е. между вершинами А и с: Сг существует взаимнооднозначное соответствие г1а Размещая состояния Л в соответствии с

<->21в )->(*, (3)

получим некоторое разбиение я на множестве состояний Л. Тк С является подграфом графа С = АхВ, то разбиение к' = \т.х,22, } на множестве состояний С такое, что \//(г;а е Za), очевидно, обладает свойством подстановки и соответствует В Тогда разбиение л, построенное в соответствии с (3), так же обладает свойством подстановки и соответствует В Достаточность доказана.

Из этого, очевидно, следует, что для построения разбиения п достаточно найти изоморфное вложение А в б

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

У автоматов А и С один входной алфавит Вследствие чего, при установлении изоморфного вложения А в о, имеет место:

1*1 ** = = кг ** гф) (4>

Из определения декартова произведения следует

= Я} -> [хшХк = V 21КХк = 0))& (з,Хк = 0 2,„Хк = 0) (5)

Из (4) и (5) следует

{гш е Г,2]/3 е ГгшЦг^б?, (6)

где Ггш - окрестность единичного радиуса вершины 2Ш,

2' - множество вершин подграфа С графа б изоморфного А Каждой вершине я, соответствует д = \У\ вершин С = Ах В Обозначим подмножество, состоящее из этих вершин, через Очевидно, что если изо-

морфное вложение А в С существует, то при его определении каждой Л', будет поставлена в соответствие одна из вершин соответствующего подмножества Z,, т е граф С будет содержать по одной и только одной вершине из каждого из описанных подмножеств множества 1

= (7)

Из определения декартова произведения следует V 1,а(2юегХ21а*+*„га)-+{Хг1а = Х^ П^Ы^ с^ ) (8) Из определения изоморфного вложения следует VI,а{?ш е 2% ** ^ е ^ ) (9)

где Хг, - множество входных векторов, для которых переход из г,, определен, соответственно Т к С является подграфом С, то исходя из (8) и (9) получим

Ч1,а(2шег'1Х11а=Х, X (Ю)

причем для истинности (10), в силу того, что (уА^ е X \Хк е Хх ), достаточно \/1,<х{г1а&2'%Х21а | = |^|) (П)

Рассуждая аналогичным образом можно показать, что

\/1,а{2ше1'^Х;1а | = |х-|) (12)

где Хг<а - множество входных векторов, по которым автомат переходит в соответственно

Если одна из вершин г1а подмножества 21 множества вершин графа С, принадлежит подграфу С, изоморфному А, то, в силу (6) подграфу С принадлежат все вершины, принадлежащие путям, для которых г1а является началом и никакие другие вершины не принадлежат С Если хотя бы для одной из указанных вершин не выполняются (7), (11), (12), то г1а г Т Таким образом, дос-

таточно перебрать к < \у\ = вариантов, чтобы найти изоморфное вложение А в С или убедиться, что таковое не существует.

Итак, установление изоморфности А и С и формирование разбиения я, предлагается проводить посредством последовательного выбора в соответствии с (6) вершин графоида б, которые удовлетворяют условиям (7), (11), (12) и, следовательно, могут содержаться в С Условия (7), (11) являются достаточными Условие (12) позволяет исключить заведомо бесперспективные построения

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

Для этого требуется найти, если он существует, такой подграф С графа Б, что.

| = |Х4 (13)

И*е хг,в = е 6 г"), (14)

(15)

где 2" - множество вершин С

Пусть С существует. Тогда, исходя из (5) (13) получим = (у*,в е г%мХк = гф))& {з,Хк = 0 -> (Уг,„ е г%:аХк = 0)) (16) Из (16) следует, что для любого г 2, П2"~ есть класс эквивалентных состояний С. Заменяя множество вершин 2, П2" одной вершиной, обозначенной я,, в силу (13) и (14) получим графоид А Следовательно О" и А эквивалентны и подмножество вершин графоида С, принадлежащих 21 П 2" соответствует вершине 5, графоида Л. Обозначив вершины этого подмножества через , получим графоид А' эквивалентный А.

Тк С является подграфом декартова-произведения б = АхВ, то очевидно, что на множестве его вершин, а, следовательно, и вершин А', существует СП-разбиение, соответствующее В, которое строится в соответствии с

Для нахождения подграфа О" воспользуемся следующими соображениями Если одна из вершин г]а (г1а е 7,) графа б, принадлежит подграфу С, то, в силу (14) подграфу принадлежат все вершины, принадлежащие путям, для которых г1а является началом и никакие другие вершины не принадлежат б" Если хотя бы для одной из указанных вершин не выполняется (13) или (15), то 2Ха <£ 2" Таким образом, достаточно перебрать к < \¥\ = ¡5, | вариантов, чтобы найти С или убедиться, что С не существует

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

При распознавании изоморфного вложения А в О (нахождении С) и при определении эквивалентного расширения носителя А (нахождении С), выбор вершин осуществляется одинаковым образом Отличаются лишь проверяемые условия Причем условия (11) и (13) совпадают, а условие (12) является частным случаем (15)

Таким образом, нахождение С и С можно объединить в один процесс, результатом которого будет нахождение или &, или С, или заключение о невозможности выделения заданной стандартной компоненты

Полученное решение может быть не единственным Различные варианты размещения по первой компоненте могут быть использованы при многокомпонентном разложении автомата То есть одна и та же стандартная компонента

(17)

может быть взята сомножителем несколько раз, если эти одинаковые компонентные автоматы установить в разные начальные состояния

Для нахождения второго разбиения я-, предлагается строить граф сцепления В соответствии с я- на Ощ наносится раскраска по первой компоненте. После чего соцветные в первой компоненте вершины соединяются. Полученный таким образом граф сцепления (Ссц) раскрашивается по второй компоненте Если Р(0С11)<д<Р{Ссц), где Р(Ссч},Р{С'а<) - плотность Осч и Ссч соответственно, то ищем новое разбиение, соответствующее заданной компоненте Если же р\ра1)>(у или, для всех существующих разбиений, соответствующих

первой компоненте, Р{С'сц ) > <7, то рассматриваются возможности сужения сигнатуры С'сц

Целью исключения некоторого ребра из сигнатуры графа является

соцветная раскраска вершин sl,sJ, а их соцветность порождает требование со-цветности вершин 5а = в,Хк и ^ = а}Хк и т д Очевидно, длина этой цепи требований зависит от выбора ребра (я,,.?,) Применение известного метода решения этой задачи связано с громоздкими процедурами возведения в степень матрицы соединений графоида и построения ряда степеней Осц

В настоящей работе нахождение оптимального варианта сужения сигнатуры Ссц основано на использовании соцветности пар несмежных вершин и

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

строить вспомогательный ориентированный граф Ор = {7.,Р), вершины которого соответствуют парам вершин графа сцепления <н<- (з,,.^)), а - множество вершин, соцветность которых дает возможность соцветной раскраски при сохранении детерминированности автоматного отображения

Основу построения графа Ср составляет множество не зацепленных в С^ пар вершин После того как, соответствующие этим парам вершины графа Ор построены, для каждой из них проверяется условие

где Л - отношение сцепленности вершин Ощ

Если это выражение истинно, то для соответствующей пары стро-

ится вершина гар и дуга , ) Если для вершины г не найдется ни одной

пары удовлетворяющей (18), то соответствующая ей ветвь построений обрывается Для построенных вершин проверяется (18) и процесс построения Ор продолжается

Для каждой построенной вершины формируются ограничения, которые накладывает на раскраску Са1 соцветность соответствующей ей пары Те формируются классы соцветности вершин Сс1<

Построение Ор продолжается до тех пор, пока пары, соответствующие вершинам Ср, не покроют все полные подграфы Ссц плотности Р>цх, где цх -

число красок в рассматриваемой компоненте спектра, или пока все ветви построений не оборвутся

После того, как искомое покрытие л = ^(з,, ), , Яр \ . ^ найдено, формируются начальные условия раскраски Саг т е множество классов соцветности

вершин, обеспечивающих возможность соцветной раскраски пар вершин, принадлежащих л

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

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

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

Пусть задан автомат графоидом и найден граф

0 = Ах А, В = (Х,У^и е У,и) Каждая вершина уц е V соответствует паре вершин графоида sl,sJ, и если:

ЗХк{в,Хк=*а,5]Хк=*р) (19)

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

димым условием соцветности вершин является соцветность вершин

В то же время, если (уц,гар)&и, то (у^у^е (/, и информация, которую несет дуга {уц,\ар) дублируется дугой Однако, удаление одной из ка-

ждой пары вершин может привести к потере информации Действительно, удалив из О все вершины, для которых, например, 1> }, мы удалим только по одной вершине из пар и Уар,Ура, но в случае, когда к ], а а > р, будут потеряны обе дуги (у,,,) и )

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

одну (уу), а соответствующие дуги заменять одной

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

лезной, в смысле выполняемых преобразований, информации Описанные преобразования проиллюстрированы на рисунках 1 а, б, в, г

г)

Рисунок 1

В полученном таким образом графе £>* вершины, не имеющие исходящих дуг, соответствуют парам состояний, совместное размещение которых не приведет к неоднозначности переходов в соответствующем компонентном автома-

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

Т к граф Б* так же как граф сцепления отражает некоторые свойства заданного графоида, то между их элементами можно установить некоторое соответствие

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

Максимальная длина пути, для которого вершина гц является началом, равна степени зацепленности пары вершин s,,sJ

Контуры в графе Б* соответствуют замкнутым последовательностям пар состояний автомата, описанным во второй главе

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

В графе £>* контуру автономного функционирования автомата длины п соответствует ~ контуров длины и, если п нечетное, и ^ контуров, один из которых длины остальные - длины и, если п четное В этом случае контур длины определяет раскраску вершин соответствующего контура в ^ краски

Для пар вершин графоида, соответствующих вершинам графа £>*, образующим контур справедливо утверждение: если одна из этих пар соцветна, то необходимым условием сохранения детерминированности переходов в соответ-

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

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

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

Если граф такой что

где Г уу - обратное транзитивное замыкание

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

Использование графа £)* для определения ограничений, накладываемых на раскраску вершин графоида соцветностью пар сцепленных вершин, проиллюстрируем на примере автомата А = (X, графоид которого изобра-

жен на рисунке 2 На рисунке 3 приведен соответствующий ему граф ¿>* К,уп е У,и), полученный в результате описанных выше преобразований

Рисунок 2 Рисунок 3

Пусть, например, требуется определить возможно ли совместное размещение состояний и 55, и, если да, то при каких условиях В графе £)* находим соответствующую вершину у15 Вершина у15 отображается в у24, у24 отображается в у,3 Если 5], 55 соцветны и 5,, 53 соцветны, то 53, - соцветны, что не накладывает дополнительных ограничений, т к отображение вершины у35 пусто Таким образом, для соцветности и «5 требуется соцветность ^,

Для формализации процесса порождения ограничений, которые накладывает соцветность пары вершин на раскраску графоида, предлагается использовать вспомогательный неориентированный граф 2 = , носитель которого совпадает с носителем графоида, а сигнатуру задает отношение соцветности, те (5,,)е/?, если ,^ соцветны

Построение графа 2 начинается с задания его носителя В графе В* вершина уу, соответствующая паре состояний автомата, для которой требуется определить ограничения, взвешивается единицей и строится соответствующее ребро в графе Z После этого единицами взвешиваются все вершины со-

ставляющие отображение уу и строятся соответствующие ребра в графе 2 Затем единицами взвешиваются все не взвешенные вершины, принадлежащие

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

В результате в графе 2 будут построены ребра, соответствующие вершине V и всем вершинам, принадлежащим путям, для которых уц является началом Т.к отношение соцветности транзитивно, то компоненты связности графа 2 дополняются до полных подграфов Вершины графа £>*, соответствующие построенным при этом ребрам графа X, взвешиваются единицами, и описанная выше процедура повторяется

Процесс продолжается до тех пор, пока не окажется, что все взвешенные вершины графа £>* отображаются во взвешенные вершины, и все компоненты связности графа 2 являются полными подграфами, или пока плотность графа Z не превысит заданное ограничение с;

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

Превышение плотности графа 2 над ограничением д означает, что подстановочного разбиения, в котором состояния в, и sJ размещены в одном блоке, и

максимальное количество элементов в блоке не превышает д, не существует Тот же вывод можно сделать, без каких-либо построений, для пар состояний, соответствующих вершинам графа £>*, из которых существует путь в вершину , так как для их соцветности требуется соцветность 5,,

Описанные вершины взвешиваются нулями и, при повторном использовании графа £>*, процесс построения графа 2 прекращается, если в нем будет построено ребро, соответствующее взвешенной нулем вершине, что позволит избежать заведомо бесперспективных построений

При использовании графа />*, дата размещения состояний по последней компоненте разложение, вершины графа £)*, соответствующие парам состоя-

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

Используя описанный метод, можно определить для каждого из подмножеств множества 5 мощности 1 < г < д, может ли оно являться блоком СП-разбиения и, если да, то какие это накладывает ограничения на размещение остальных состояний автомата В результате этого будет получено множество <2 всех подмножеств множества состояний автомата, которые могут быть блоками СП-разбиения, с соответствующими каждому из этих подмножеств ограничениями

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

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

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

Процесс формирования множества <2 предлагается проводить поэтапно Определяя на каждом г-ном этапе элементы множества <2, исходя из ограниче-

ний накладываемых на раскраску вершин графоида соцветностью вершин подмножеств мощности г, рассматривая при этом только те подмножества (б'), для которых найдется г подмножеств мощности г-1 (5'"*1), таких, что е Б* и возможность совместного размещения элементов определена на предыдущем этапе После р<д этапов множество Q будет найдено

Тогда задача построения СП-разбиения сводится к нахождению такого подмножества множества 0, элементы которого являются непересекающимися подмножествами с непротиворечивыми ограничениями, и их объединение есть множество состояний автомата

С этой целью строится вспомогательный граф О = {Р,Н) вершины, которого соответствуют элементам множества £>, и (р,,ру) е Н если соответствующие подмножества могут быть блоками одного СП-разбиения Максимально полные подграфы графа О задают разбиения на множестве состояний автомата А, обладающие свойством подстановки Максимально полный подграф графа <7 мощность, которого меньше или равна заданному ограничению на число состояний в искомой компоненте разложения, задает искомое разбиение

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

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

Рисунок 4 ЗАКЛЮЧЕНИЕ

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

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

- сформулирована и доказана теорема существования размещения состояний заданного автомата по стандартной компоненте разложения,

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

-23- проведен анализ графа условий соцветности вершин и обоснована предпочтительность его использования при решении задачи сужения сигнатуры графа сцепления,

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

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

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

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

1 Дзугкоева А А Частные задачи разложения графа в декартово произведение Труды молодых ученных, Вл науч центр РАН, 2006 № 4, с 13-20 Владикавказ

2 Дзугкоева А А Исследование процедур расщепления запрещенных фигур раскраски графа сужением его сигнатуры Известия высших учебных заведений Северо-Кавказский регион Технические науки, 2007 №4, с 21-26 Ростов-на-Дону

3 Дзугкоева А А Разложение автоматных графоидов (функций на графах) в декартово произведение стандартных компонент Приборы и системы Научтех-литиздат, 2007, №9, с 14-16, Москва

-244 Дзугкоева А А , Пагиев КХ Использование СП-разбиений в САПР систем логического управления Сборник научных трудов СООАНВШРФ, № 5, 2007, с 68-73 Владикавказ

5 Дзугкоева А А Имитационная модель системы автоматизированного проектирования абстрактного этапа реализации устройств управления на стандартных составляющих Труды молодых ученных, Вл науч центр РАН, 2007 № 4, с 28-32 Владикавказ

Зак №124 Тир 100 объем 1 п л

Подразделение оперативной полиграфии СКГМИ(ГТУ) г Владикавказ, ул Космонавта Николаева 44

ВВЕДЕНИЕ.

ГЛАВА 1. СОСТОЯНИЕ ПРОБЛЕММЫ И ОБЗОР МЕТОДОВ

АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ.

1.1 .Моделирование систем управления.

1.2.Методы автоматизированного проектирования систем логического управления.

ГЛАВА 2 НАХОЖДЕНИЕ РАЗМЕЩЕНИЯ ПО СТАНДАРТНОЙ

СОСТАВЛЯЮЩЕЙ.

2.1. Нахождение изоморфного вложения графоида заданного автомата в декартово произведение графоидов заданного и стандартного автоматов.

2.2. Расширение носителя графоида заданного автомата.

2.3. Формирование подмножеств соцветных вершин на основе функционально несвязных пар состояний автомата.

ГЛАВА 3. ПОСТРОЕНИЕ ГРАФА УСЛОВИЙ СОЦВЕТНОСТИ ВЕРШИН ГРАФОИДА ЗАДАННОГО АВТОМАТА И НАХОЖДЕНИЕ РАЗМЕЩЕНИЯ ЕГО СОСТОЯНИЙ ПО КОМПОНЕНТАМ РАЗЛОЖЕНИЯ.

3.1. Нахождение системы ограничений на размещение состояний автомата

3.2. Нахождение нестандартной компоненты разложения.

ГЛАВА 4. РАЗРАБОТКА СИСТЕМЫ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ АБСТРАКТНОГО ЭТАПА РЕАЛИЗАЦИИ УСТРОЙСТВ УПРАВЛЕНИЯ НА

СТАНДАРТНЫХ СОСТАВЛЯЮЩИХ И ЕЁ ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ.

4.1. Состав и функционирование системы проектирования.

4.2. Имитационная модель системы проектирования.

4.3. Примеры решения задач проектирования с использованием разработанной САПР.

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

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

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

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

- разработка метода нахождения размещения состояний заданного автомата по стандартной компоненте разложения.

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

- разработка алгоритмов реализации предложенных методов.

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

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

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

Научная новизна:

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

- сформулирована и доказана теорема существования размещения состояний заданного автомата по стандартной компоненте разложения.

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

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

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

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

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

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

Результаты работы внедрены: на НПК «Югцветметавтоматика» при разработке АСУ процессом обжига электродного производства на ОАО «Новочеркасский электродный завод», что позволило получить экономический эффект в размере 570000 руб. в год. Основные научные и практические результаты используются в учебном процессе СКГМИ(ГТУ) при чтении лекций и проведении практических занятий по дисциплинам «Дискретная математика» и «Теоретические основы построения САПР».

Апробация работы. Основные результаты проведённых в диссертации исследований докладывались на межкафедральном научном семинаре «Декомпозиционная теория синтеза систем логического управления», на ежегодных научно-технических конференциях СКГМИ (ГТУ) (2004-2007 гг.), Международной научно-практической конференции «Системный анализ в проектировании и управлении» (Санкт-Петербургский государственный политехнический университет), V-й Международной конференции «Устойчивое развитие горных территорий: проблемы и перспективы интеграции науки и образования», г. Владикавказ.

Связь с государственными программами. Основные исследования выполнялись в рамках аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы» (2006 - 2008 г.)

Публикации. Основное содержание диссертационной работы опубликовано в 5-ти печатных работах.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка использованной литературы из 87 наименований и 2 приложений. Общий объем диссертации 132 страницы, включая 49 рисунков и 4 таблицы.

Выводы

Описана возможность использования предложенных во 2-й и 3-й главах методов для создания системы автоматизированного проектирования абстрактного этапа реализации устройств управления на стандартных составляющих.

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

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

ЗАКЛЮЧЕНИЕ

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

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

- Сформулирована и доказана теорема существования размещения состояний заданного автомата по стандартной компоненте разложения.

- Предложено использование декартова произведения графоидов заданного и стандартного автоматов для нахождения эквивалентного расширения носителя графоида заданного автомата позволяющего построить размещение по стандартной компоненте разложения. Разработан алгоритм построения такого расширения.

- Проведён анализ графа условий соцветности вершин и обоснована предпочтительность его использования при решении задачи сужения сигнатуры графа сцепления.

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

- Предложен метод нахождения размещения состояний автомата по компонентам разложения, основанный на нахождении множества таких подмножеств множества состояний автомата, совместное размещение элементов которых не приведёт к недетерминированности переходов в компонентном автомате.

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

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

1. Инан К.М., Варайя П.П. Алгебры дискретно-событийных моделей // ТИИЭР, т. 77, № 1, январь 1989.

2. ЗиглерБ.П. Представление динамических систем на основе дискретно-событийных описаний: Интеллектуальное управление на базе событий // ТИИЭР, т. 77, № 1, январь 1989.

3. Райтер Р., ВальранЖ.С. Распределённое имитационное моделирование дискретно-событийных систем // ТИИЭР, т. 77, № 1, январь 1989.

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

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

6. Варшавский В.И. и др. Поведение автоматов в периодических случайных средах и задача синхронизации при наличии помех. Сб. «Проблемы передачи информации», 1,1965.

7. Варшавский В.И., Мараховский В.Б, Песчанский В.А. О задаче голосования в цепи автоматов. Изв. АН СССР. Техн. Кибернетика, № 4,1968.

8. Гаврилов М.А. Построение релейных устройств и конечных автоматов из блоков. Изв. АН СССР. Техн. Кибернетика, 1963.

9. Гаврилов М.А. Об уточнении оценки для определения числа состояний при композиции конечных автоматов. Автоматика и телемеханика, № 11,1964.

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

11. Глушков В.М. Введение в кибернетику. Киев, Изд-во АН УССР, 1964.

12. Глушков В.М. О применении абстрактной теории автоматов для минимизации микропрограмм. Изв. АН СССР. Техн. кибернетика, № 1,1964.

13. Глушков В.М. Теория автоматов и формальные преобразования микропрограмм. Кибернетика, № 5,1965.

14. Горбатов В.А. Схемы управления ЦВМ и графы. М.: Энергия, 1971.

15. Горбатов В.А., Дедегкаев А.Г. Запрещённые фигуры при параллельной декомпозиции автоматов / В кн.: Оптимизация дискретных систем управления. ГВЦ Госплана СССР, 1972.

16. Горбатов В.А., Дедегкаев А.Г. Метод расщепления запрещённых фигур при построении параллельной декомпозиции систем / Сб. Прикладные вопросы теории систем и системотехники. М.: МДНТП, 1973.

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

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

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

20. Горбатов В.А., Останков Б.Л., Фролов С.А. Регулярные структуры автоматного управления. М.: Машиностроения, 1980.

21. Горбатов В.А. Информационная математика. -М.: Наука, 1997.

22. Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика. М.: Мир, 1997.

23. Горбатов В.А., Крылов А.В., Федоров Н.В. САПР систем логического управления. М.: Энергоизат, 1988.

24. Горбатов В.А., Смирнов М.И., Хлытчиев И.С. Логическое управление распределёнными системами. -М.: Энергоиздат, 1991.

25. Горбатов В.А. Синтез микропрограммных автоматов по временным диаграммам их функционирования. Цифровая вычислительная техника и программирование, вып. 5 -М.: Сов. радио, 1969.

26. Горбатов В.А. Оценки при выборе направления вычислений в задачах синтеза конечных автоматов // Изв. АН СССР. Техническая кибернетика. 1970. -№4.

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

28. Лазарев В.Г. О синтезе микропрограммных автоматов. Сб. «Проблемы передачи информации», 1965,1,2.

29. Лазарев В.Г., Пийль Е.И. Уменьшение числа состояний одного класса конечных автоматов. ДАН СССР, 1962,143, № 5.

30. Мелихов А.Н. Некоторые операции над графами // Изв. АН СССР. Техн. кибернетика, № 6, 1964.

31. Мелихов А.Н., Дворянцев Ю.А. Разложение графов и конечных автоматов относительно операции умножения // Кибернетика, № 3, 1965.

32. Мелихов А.Н., Бернштейн JI.C., Карелин В.А. Разложение графов и конечных автоматов по операции суммирования // Изв. АН СССР. Техн. кибернетика, № 2,1968.

33. Мелихов А.Н., Дворянцев Ю.А. Теоретико-множественные и алгебраические операции над конечными автоматами // Изв. АН СССР. Техн. кибернетика, №3,1967.

34. Мелихов А.Н., Бернштейн JI.C., Карелин В.А. О декомпозиции абстрактных автоматов // Кибернетика, № 3,1969.

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

36. Мелихов А.Н., Бернштейн JI.C. Последовательная декомпозиция конечных автоматов. Изв. АН СССР. Техн. кибернетика, 1968, № 3.

37. Мелихов А.Н., Бернштейн JI.C. Абстрактная декомпозиция конечных автоматов. Сб. «Вычислительные системы». Труды I Всесоюзной конференции по вычислительным системам, вып. 3. Программирование на вычислительных средах. Новосибирск, 1968.

38. ПийльЕ.И. О кодировании внутренних состояний конечного автомата. Изв. АН СССР. Техн. кибернетика, 1965, № 2.

39. Пийль Е.И. Способ размещения внутренних состояний асинхронного конечного автомата. Сб. «Проблемы передачи информации», 1964, вып. 17.

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

41. Поспелов Д.А. Логические методы анализа и синтеза схем. Л. - М.: Энергия, 1964.42.3ахаров В.Н., Поспелов Д.А., Хазацкий В.Е. Системы управления. Задание. Проектирование. Реализация. Издание второе. М.: Энергия, 1977.

42. Поспелов Д.А. Большие системы. Ситуационное управление. М.: Знание, 1975.

43. Arbib М.А. Turing machines, finite automata and neural nets. JACM, 1961, № 4.

44. Quine W.V. Way to simplify truth functions. Amer. Math. Monthly, 1955, 62.

45. Миллер P. Теория переключательных схем.: Наука, 1970, т. 1, т. 2,1971. 47.Sechu S. Mathematical models of sequential machines. IRE Convent. Record,1959,7, part 2.

46. Hartmanis J. Symbolic analysis of a decomposition of information processing machines. Inform, and Control, № 2,1960.

47. Hartmanis J. On the state assignment problem for sequential machines I, IRE Trans. On Electronic Computers, EC-10, № 2,1961.

48. Hartmanis J. Minimal feedback realization of sequential machines. IEEE Trans., EC-15,№6,1966.

49. Hartmanis I., Stearns R.E. Pair algebra and its application to automata theory. Inform. and Control, 7, № 4,1964.

50. Hartmanis I., Stearns R.E. Algebraic structure theory of sequential machines. Prentice Hall, Inc., Englewood, Cliffs, New Jersey, 1966.

51. Huffman D.A. Synthesis of sequential switching circuits. J. Franklin Institute, 257, №4,1954.

52. Huffman D.A. The design and use of hazard-flue switching networks. JACM, №4,1957.

53. Таль A.A. Анкетный язык и абстрактный синтез минимальных последова-тельностных машин // Автоматика и телемеханика, № 6, т. XXV, 1964.

54. Таль А.А. Абстрактный синтез последовательностных машин по ответам на вопросы первого типа анкетного языка. «Автоматика и телемеханика, т. 26, № 4,1965»

55. К. Nabuyuki, A. Tadashi, Y. Noriyoshi. An extension of pair algebra. Bull. Fac. Eng. Hiroshima Univ., vol. 22, № 2,1974.

56. Yoli M. The cascade decomposition of sequential machines /1, IRE Trans. On Electronic Computers, EC-10, N4,1961.

57. Yoli M., Gansburg A. On homomorphic images of transition grafs /1. Franklin Inst, 278, N5, 1964.

58. Kohavi Z. Secondary state assignment for sequential machines. IRE Trans., EC-13, №3.

59. Kohavi Z., Smith E.J. Decomposition of sequential machines. IEEE. Conf. Rec. Switch. Circuit theory and logic design, Ann. Arbor, Mich.,, 1965.

60. Кузнецов О.П. Параллельная декомпозиция автоматов с разделением входов // Автоматика и телемеханика, № 3,1969.

61. Дедегкаев А.Г. Некоторые свойства автоматных операторов, не допускающих параллельную декомпозицию. В кн.: Оптимизация дискретных систем управления. - ГВЦ Госплана СССР, 1972.

62. Дедегкаев А.Г. Алгоритмы разложения микропрограммного автомата. В кн.: Автоматизированные системы проектирования . -МДНТП, 1977.

63. Дедегкаев А.Г. Уменьшение связности графа зацепления автоматного графоида. - В кн.: Оптимизация дискретных систем управления. - МДНТП, 1979.

64. Дедегкаев А.Г. Расщепление запрещённых фигур параллельной декомпозиции абстрактных автоматов оптимальным расширением памяти. В кн.: Разработка и внедрение систем автоматизированного проектирования в машиностроении. - Ижевск, ИМИ, 1983.

65. Использование зависимой раскраски графов при построении декомпозиции автоматных операторов. В кн.: Логическое управление в промышленности -Ижевск, ИМИ, 1984.

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

67. Баранов С.Н., Скляров В.А. Цифровые устройства на программируемых БИС с матричной структурой. М.: Радио и связь, 1986.

68. Девятков В.В. Реализация конечных автоматов на сдвиговых регистрах. Автоматика и телемеханика, 1968, № 11.

69. Девятков В.В. Реализация конечных автоматов на двух циклических автономных автоматах. Автоматика и вычислительная техника, 1969, № 5.

70. Девятков В.В. Методы реализации конечных автоматов на сдвиговых регистрах. «Энергия», 1974.

71. Ларин Л.К., Осинский Л.М., Экономичное кодирование состояний конечного автомата, Кибернетика, 1966, № 3.

72. Ларин Л.К., Осинский Л.М., Автоматы с последовательной однородной структурой. Техническая кибернетика, 1969, № 1.

73. Горбатов В.А., Грехнёв В.А., Метечко В.И. Проектирование регулярных управляющих автоматов. В сб. Автоматизированные системы проектирования, М., МДНТП им Ф.Э. Дзержинского, 1975.

74. Грехнёв В.А. Проектированиеуправляющих автоматов на композиции сдвиговых регистров и распределителей. В сб.: Общая теория систем и интеграция знаний, М., МДНТП им Ф.Э. Дзержинского, 1976.

75. Грехнёв В.А. Повышение регулярности логических устройств цифровой автоматики. Логическое управление в промышленности, М., МДНТП им Ф.Э. Дзержинского, 1977.

76. Останков Б.Л. Оптимизация систем управления на основе регулярных и квазирегулярных МЭП. Оптимизация дискретных систем управления, М., МДНТП им Ф.Э. Дзержинского, 1979.

77. Горбатова М.В. Быстродействующий алгоритм раскраски вершин графа / В кн.: Логическое управление в промышленности. Ижевск: ИМИ, 1984.

78. Бондаренко Н.Н., Братолюбов В.Г. Низковольтные преобразователи для гальванотехники и электрохимических станков. М.: Энергоатомиздат, 1987.

79. Бахвалов Л.А. Моделирование систем. Высшее горное образование, М.: Изд. МГГУ, 2006.

80. Харари Ф. Теория графов. -М.: Мир, 1973.

81. Дзугкоева А.А. Частные задачи разложения графа в декартово произведение. Труды молодых ученных, Владикавказ, Вл. науч. центр РАН, № 4,2006.

82. Дзугкоева А.А. Исследование процедур расщепления запрещённых фигур раскраски графа сужением его сигнатуры. Известия высших учебных заведений Северо-Кавказский регион. Ростов-на-Дону, Технические науки, №4, 2006

83. Дзугкоева А.А Разложение автоматных графоидов (функций на графах) в декартово произведение стандартных компонент. Приборы и системы. М.: Научтехлитиздат, №9,2007.

84. Дзугкоева А.А., Пагиев К.Х. Использование СП-разбиений в САПР систем логического управления. Сборник научных трудов СООАНВШРФ, Владикавказ, № 5,2007.

85. Дзугкоева А.А. Имитационная модель системы автоматизированного проектирования абстрактного этапа реализации устройств управления на стандартных составляющих. Труды молодых ученных, Владикавказ, Вл. науч. центр РАН, № 4,2007.