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

• Анишев, Петр Александрович
• кандидат технических наук
• 1984

Оглавление диссертации кандидат технических наук Анишев, Петр Александрович

- ■ ■ • ц

Введение

Глава I. Сети Петри и параллельные граф-схемы алгоритмов • • ^

§ I.I. Сети Петри.

1.1.1. Определение основных понятий

1.1.2. Классы сетей Петри

1.1.3. Расширения сетей Петри

§ 1.2. Параллельные граф-схемы алгоритмов.

1.2Л^ Определение основных понятий

1.2.2. Корректность параллельных граф-схем алгоритмов . . зх

1.2.3. Структурированные ПГСА.

1.2.4. Методы проверки ПГСА на корректность.

§ 1,3. Переход, от ПГСА к сети Петри.

1.3.1. Правила перехода.

1.3.2. Анализ правил перехода.

§ 1.4. Постановка задачи проверки ПГСА на корректность

Выводы к главе I.

Глава П. Редукция сетей Петри.

§ 2.i. Постановка задачи редукции.

2.1.1. Определение условий

2.1.2. Отличия от ранее введенных преобразований редукции

§ 2.2. Определение преобразований редукции

2.2.1.Какие вершины можно удалять?

2.2.2.Удаление избыточного перехода

2.2.3. Удаление избыточной позиции

2.2.4. Преобразование подстановки позиции

2.2.5. Замена фрагмента

§ 2.3. Анализ преобразований редукции

2.3.1; ЦЗ- эквивалентность преобразований

2.3.2. Конечность преобразований

2.3.3. Оценки сложности

2.3.4. Независимость

2.3.5. Локальность

2.3.6. однозначность

2.3.7. Нерешенные вопросы редуцирования

§ 2.4. Классы редуцируем ости сетей Петри.Ю

2.4.1. Диаграмма вложения классов редуцируемости

2.4.2. Доказательство вложений

§ 2.5. ' Алгоритм и программа редукции.Ю выводы к главе II.

Глава Ш. Анализ сетей Петри.

3.1. Декомпозиция РС- сетей.

3.1.1. Определение понятий . 1и

3.1.2. № - и условия.

3.1.3. Объединенный алгоритм проверки и условий

3.1.4. Сложность алгоритма и пути ее уменьшения

§ 3.2. Построение дерева достижимых.маркирований и использование его для анализа сети.

§ 3.3. Требования, к алгоритмам анализа сетей Петри на правильность

Выводы к главе Ш.

Глава 1У. Применение методики и особенности программной реализации.

§ 4.1. Применение разработанных методов к анализу некоторых систем взаимодействующих процессов

4.1.1. Проверка асинхронных интерпретаций параллельных микропрограмм на детерминированность

4.1.2. Проверка некоторых-свойств протоколов

4.1.3. Имитация процесса формирования и функционирования-экономических систем

V? 4.2. Представление данных и характерные особенности программы анализа ПГСА на корректность

Выводы к главе 1У.

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

Развитие устройств автоматики и вычислительной техники идет по пути усложнения в направлении от последовательной обработки к параллельной. Это обусловлено: во-первых>потребностью во все более производительных и гибких ЭВМ, а во-вторых,возросшими возможностями технологии, приводящими к удешевлению и миниатюризации аппаратуры. Такое развитие характеризуется следующими этапами: от распараллеливания по данным (например^одновременная обработка разрядов в последовательных ЭВМ классической архитектуры) через распараллеливание действий к параллельному управлению. В связи с этим возникает потребность в методах описания анализа и синтеза управления дискретными параллельными системами. Теория таких систем для последовательного случая хорошо известна и давно стала классической [13, 17, 18, 23, 38, 45, 48], однако учет фактора параллельности требует дальнейшего развития этой теории. Попыткой такого развития (в одном из аспектов) и является настоящая работа.

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

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

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

Важным с .вой с тв ом, которому должно удовлетворять описание управляющей системы, является корректность. Корректное описание соответствует такой системе, в которой при реализации взаимодействующих процессов никогда не настудает ситуаций, приводящих к зависанию процессов, взаимной блокировке двух и более процессов и т.п. Свойство корректности обеспечивает, например, обязательное завершение начавшегося вычисления и инвариантность его результата от соотношения продолжительностей времен срабатывания операторов. Как обеспечить корректность описания параллельной системы управления? Методы теории конечных автоматов, которые служал основой для проектирования устройств управления дискретными системами^ ограничены рассмотрением последовательных процессов. Их возможности оказываются недостаточными для создания способов обеспечения корректной работы системы взаимодействующих процессов. Вопросы теории параллельных процессов исследованы достаточно полно £26, 30, 35, 36, 37, 46, 60]?однако созданию практических алгоритмов анализа на корректность должного внимания до настоящего времени не уделялось. Использование сетей Петри для такого анализа отражено в работах [50-52, 55, 56J, связанных с декомпозицией и редукцией сетей Петри.

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

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

Выбор таких средств должен основываться на сравнительном анализе различных моделей параллельных вычислений. Подробный анализ таких моделей дается в £60j .В нашем случае в качестве модели были выбраны сети Петри [62] , при этом были учтены следующие соображения:

I) поведение управляемой системы удобно описывать в терминах событий и условий, что соответствует "событиям" - срабатываниям переходов и "условиям" - значениям функции маркирования в сети Петри;

2) существует формальное отображение параллельной граф-схемы алгоритма управления в сеть Петри, моделирующую поведений системы £2-5] ;

3) сеть Петри можно рассматривать как расширение понятия абстрактного автомата и представить эквивалентным автоматом £llj или композицией автоматов [I2J ; следовательно;методы синтеза устройств управления могут в какой-то мере использовать опыт синтеза конечных автоматов;

4) сети Петри имеют наглядное графическое представление,что позволяет при разработке и программировании алгоритмов анализа сетей использовать опыт, накопленный при создании матобеспечения для решения задач теории графов; это касается как вопросов представления сетей в памяти ЭВМ [443» так и использования классических алгоритмов таких,как определение сильной связности графа и т.п. [8"] ;

5) математическая теория сетей Петри достаточно хорошо развита> имеются много работ как jjimc в стране,так и за рубежом, в которых исследуются различные вопросы, связанные с анализом сетей и их применением для моделирования; не ставя своей целью дать обзор таких работ (имееются по крайней мере две монографии по сетям Петри [53, 62 см.также обзор [42])отметим те,которые в большей степени повлияли на наши исследования [50-52, 55,56j;

6) кроме того в терминах сетей Петри можно представлять другие модели параллельных вычислений.

Под сетями Петри понимаются в общем случае,так называемые; обобщенные сети Петри, это такие сети, у которых значение маркирования в каждой позиции-ноль или натуральное число и дуги связывающие позиции и переходы могут иметь кратность большую единицы. Такая оформление диссертации уже было закончено, когда вышла книга: Котов В.Е. Сети Петри.- М.: Наука, 1984.

• - I общность для наших целей является черезмерной в силу следующего: исходным заданием для синтеза асинхронного устройства управления « должно быть удобное и наглядное описание системы взаимодействий*: между операторами. Как показал опыт проектирования микропрограммных автоматов, таким представлением является граф-схема алгоритма (ГСА) [13,25 3* Поэтому представляется целесообразным ввести аналогичный способ описания системы асинхронно взаимодействующих операторов - параллельные граф-схемы алгоритмов (ПГСА), которые являются расширением обычных граф-схем, широко используемых при описании дискретного управления. Параллельная граф-схама хотя и обладает всей необходимой информацией, но в явной форме не отражает поведения управления системой, а потому не дает наглядного представления о внутренней управляющей логике, йети Петри и будут тем средств ом^ которое призвано моделировать управление в ПГСА, а для такого моделирования вполне достаточно ординарных сетей Петри, который являются подклассом обобщенных сетей. К достоинствам ординарных сетей следует отнести то, что алгоритмы анализа таких сетей более просты (по сравнению с алгоритмами анализа обобщенных сетей), имеют меньшие оценки сложности; кроме того применение ординарных сетей позволяет ( в силу компактного представления в памяти ЭВМ) анализировать (в том числе и на корректность) системы с большим числом элементов.

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

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

1. Пределить правила написания ПГСА так, чтобы при соблюдении этих правил граф-яхема получалась заведомо корректной. Проблема корректности, таким образом, сводится к проверке соблюдения определенных правил написания. Этот подход состоит в распространении идей структурного программирования на случай параллельных граф-схем £66, 693 •

2. Найти в ПГСА все конфигурации, приводящие к некорректности.

3. Перейти от ПГСА к ординарной сети Петри, сводя проверку ПГСА на корректность к анализу соответствующей сети Петри на свойство живости и безопасности,

В диссертации для проверки ПГСА на корректность применяется третий из перечисленных подходов. Хотя переход сети не уменьшает экспоненциальную вычислительную сложность проверки на корректность, он (этот переход) имеет кроме ранее перечисленных достоинств использования сетей Петри для моделирования еще одно. А именно, сложность анализа сети Петри можно существенно уменьшить, сократив сеть: применением эквивалентных преобразований (правил редукции). Эквивалентность понимается как сохранение свойств живости и безопасности в отличие от работ [31-32] , где эквивалентные преобразования приводят к сетям, порождающим один и тот же язык, или от работ С27, 43которых сети считаются эквивалентными, если они приводят к тому же конечному автомату. Поскольку целью диссертации является разработка приемлемых по времени методов анализа на кор/-ректность, то для достижения этой цели были разработаны эквивалентные преобразования редукции (сокращения) исходного описания. На основании этих преобразований созданы практические (с полиномиальной сложностью при степени полинома 2*3) алгоритмы редукции ординарных сетей Петри. Имеющиеся в литературе £50 -52 3 преобразования для аналогичных целей обобщенных сетей Петри нас не удовлетворяют по следующим причинам: во-первых,из-за высокой сложности, а во-вторых, в силу того, что применение преобразований^определенных в £50-52 ];не сохраняет [6] свойство безопасности ординарных сетей Петри.

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

Диссертация состоит из введения, четырех глав и заключения.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Анишев, Петр Александрович

Основные результаты работы.

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

2. Определен язык описания, и найдены условия корректности структурированных ПГСА.

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

4. Доказана теорема, позволяющая сводить задачу проверки ПГСА на корректность к анализу соответствующей ординарной сети Петри на живость и безопасность.

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

7. Доказана теорема, на основе которой построен объединенный алгоритм анализа (путем декомпозиции) сетей Петри свободного выбора на свойства правильности и хорошей сформированности.

8. Выделены задачи, решение которых позволит повысить эффективность алгоритмов анализа.

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

10. С целью практической"реализации методики разработаны, написаны и отлажены программы анализа ПГСА на корректность. Программы написаны на языке ПЛ/1 и имеют квадратичные оценки по времени и памяти. Практическая эффективность данной работы подтверждена использованием указанных программ в ряде организаций.

Заключение

Список литературы диссертационного исследования кандидат технических наук Анишев, Петр Александрович, 1984 год

1. Анисимов H.A. Средства формального описания сервиса и протоколов сетей ЭВМ с использованием сетей Петри.- Владивосток:

2. Б.Ц., 1983. 32с. - (препринт/ ИАПУ ДВНЦ АН СССР).

3. Анишев П.А. Анализ на детерминированность граф-схем с арбитрами. XII обл.научно-техн. конф. посвященная Дню радио и связиста, 20-22 апр. 1978: тез.докл. Новосибирск, 1978, с.5-6.

4. Анишев П.А. Моделирование параллельных граф-схем сетями Петри. Тез. докл. Ш Всесоюз. семинара " Моделирование дискретных управляющиях и вычислительных систем". Свердловск,1981, с.7-8.

5. Анишев П.А. О детерминированности параллельных граф-схем.- В кн.: Вопросы теории и построения вычислительных систем (Вычислительные системы, вып. 73). Новосибирск, 1978, с.40-52.

6. Анишев П.А. Один способ анализа корректности граф-схем алгоритмов. Программирование, 1981, № I, с. 20-28.

7. Анишев П.А. Редукция сетей Петри. В кн.: Архитектура вычислительных систем с программируемой структурой (Вычислительные системы, Вып. 82). Новосибирск, 1980, с.41-54,

8. Анишев П.А. Редуцируемость сетей Петри. Программирование,1982, Ш 4, с.36-43.

9. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. - 536 с.

10. Ачасова С.М. Анализ асинхронной интерпретации параллельных микропрограмм. В кн.: Однородные вычислительные системы из микро-ЭВМ (Вычислительные системы, Вып. 97). Новосибирск,1983, с.28-52.

11. Бандман 0.JI. Асинхронная интерпретация параллельных микропрограмм. Кибернетика, 1983, № 5, с.17-23.

12. Бандман О.Л. Минимизация сетей Петри при синтезе асинхронного параллельного управления. В кн.: Однородные вычислительные системы (Вычислительные системы, вып. 90). Новосибирск, 1981, с. 3-21.

13. Бандман О.Л. Синтез асинхронного управления параллельными процессами. Кибернетика, I98u, te I, с.42-47.

14. Баранов С.И. Синтез микропрограммных автоматов. Л.: Энергия. Ленинградское отделение, 1974. - 216 с.

15. Брукс Ф.П. Как проектируются и создаются программные комплексы. М.: Наука, 1979. - 152 с.

16. Виленкин С.Я., Гольденберг Р.И., Розенблит С.И. язык управления заданиями для вычислительных комплексов с централизованным управлением. - Программирование, 1982, 112 2, с. 35-44.

17. Вычислительные сети и сетевые протоколы/Дэвис Д., Барбер Д., Прайс У., Соломонидес С.-М,: Мир, 1982. 563 с.

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

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

20. Дэвис Д., Барбер Д. Сети связи для вычислительных машин.- М.: Мир, 1976. 680 с.

21. Есикова Т.Н. Алгоритм построения множества достижимых маркирований для анализа сетей Петри. В кн.: Однородные вычислительные системы из микро-ЭВМ (Вычислительные системы, Вып.97) Новосибирск, 1983, с.28-52.

22. Есикова Т.Н. Анализ устойчивости взаимодействия элементов ТПК с использованием сетей Петри. В кн.: Территориально-производственные комплексы: планирование и управление/ Отв. ред. А.Г. Аганбегян. - Новосибирск, Наука, 1984, гл.9,с.205-224.

23. Есикова Т.Н. Использование сетей Петри для имитации процесса формирования и функционирования ТПК. В кн.: Программно-целевые ТПК: предплановые исследования, Новосибирск, 1982,с.123-146.

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

25. Зиновьев Э.В., Стрекалов A.A. Устранение конфликтных ситуаций при управлении доступом процессов к информационным ресурсам в вычислительных системах и сетях:(Препр.докл.)/ Под общ. ред.Э.А.Якубайтиса. Рига: Б.И., 1983.- 70с. - В надзаг.:

26. АН Латв. ССР, Ин-т электроники и вычислительной техники; ИЭВТ-Р20.

27. Калужнин Л.А. Об алгоритмизации математических задач. Проблемы кибернетики, 1959, вып.2, с. 51-67.

28. Карп P.M., Миллер P.E. Параллельные схемы программ. В кн.: Кибернетический сборник, нов.сер., вып.13. М.: Мир, 1976,с. 5-61.

29. Кнут Д. Искусство программирования для ЭВМ. т.З. Сортировка и поиск. М.: Мир, 1978. - 844 с.

30. Кораблин Ю.П. Проблема корректности граф-схем параллельных алгоритмов. Программирование, 1978, № 5, с.45-52.

31. Котов В.Е. Алгебра регулярных сетей Петри. Кибернетика, 1980, № 5, с.10-18.160t

32. Котов B.E. Алгебра регулярных сетей Петри,- Новосибирск, 1978, 40 с. - (Препринт/АН СССР, Сиб. отд-ние, ВЦ; 98).

33. Котов В.Е., Черкасова JI.A. Структурированные сети. Кибернетика, 1981, № 4, с.33-41.

34. Кочетова A.A., Скоробогатов В.А., Хворостов П.В. Язык описания структурной информации ОГРА 3.0. - В кн.: Машинные методы обнаружения закономерностей, анализа структур и проектирования (Вычислительные системы, вып.92). Новосибирск, 1982, с.70-79.

35. Криницкий H.A. О параллельных алгоритмах. Программирование, 1983, № 4, с.9-15.

36. Криницкий В.Н., Криницкий H.A. Анализ коллективов алгоритмов. Программирование, 1982, № 2, с.3-17.

37. Кутепов В.П., Кораблин Ю.П. Язык граф-схем параллельных алгоритмов. Программирование, 1978, № I, с.3-12.

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

39. Лингер Р., Миллс X., Уитт Б. Теория и практика структурного программирования. М.: Мир, 1982. - 406 с.

40. Математическое обеспечение автоматизированного проектирования (информационный обмен/отв. ред. Чистов В.П. Свердловск: УНЦ АН СССР, 1982. - 76 с. - В надзаг.: АН СССР, Уральский науч.центр, ин-т математики и механики.

41. Методы параллельного микропрограммирования / П.А.Анишев, С.М. Ачасова, О.Л.Бандман, С.В.Пискунов, С.Н.Сергеев; под ред. О.Л.Бандман. Новосибирск: Наука, 1981. - 180 с.

42. Никонов В.В., Псарский Ю.Е. Сети Петри. Теория. Применение.-Зарубежная электроника, 1984, Ш 4, с.28-59.

43. Плакс Т.П. Синтез параллельных программ на вычислительных моделях. Программирование, 1977, № 4, с.55-63.

44. Попков В.К'. Представления графов. Новосибирск, 1980,- 36с.-(Препринт/АН СССР, Сиб. отд-ние, ВЦ; 241).

45. Поспелов Д.А. Логические методы анализа и синтеза схем. М.: Энергия, 1968. - 328 с.

46. Элементы параллельного программирования / В.А.Вальковский, В.Е. Котов, А.Г. Марчук, Н.Н.Миренков; Под ред. В.Е.Котова,-М.: Радио и связь, 1983.- 239с.

47. Якубайтис Э.А. Архитектура вычислительных сетей. М.: Статистика, 1980. - 279 с.

48. Якубайтис Э.А. Синтез асинхронных конечных автоматов. Рига: Зинатне, 1970. - 325 с.

49. Andre С., Boeri Р., Marin J. Syntese et Realisation des

50. Е- Ур(и.-Мс?и£ gimtd-baneeCy «- Re vue- ^ Systems LogîgpiesVFrancaise d*Automatique Informatique Recherche

51. Opérationnelle, 1976, vol. 10, N* 4, Avril, p.67-86.

52. Berthelot G. PreuVe de non blocage de programmes parallèles par reduction de reseaux de Pétri.- 1-st European Conference on Parallel and Distributed Processing. Toulouse, France, February 14, 16, 1979» p.251-259.

53. Berthelot G., Roucairol G. Reduction of Petri-Kets.- Lecture Uotes in Computer Sciences, 1976, N* 45, p.202-209.

54. Berthelot G. Verification de reseaux de Petri.- Thèse de £eme cycle Université Pierre et Marie Curie. Paris, Janvier 1978,-VIII, 212, 8 p.

55. Brams G.W. Réseaux de Petri: Théorie et pratique.- Paris etc.: Masson, 1985.- Vol. 1. Théorie et analyse. 1983. VIII, 184.; Vol. 2. Modélisation et applications. 1983. 159 p.

56. Commoner F., Holt A.W., Even S., Phuelli A. Marked directed graphs.-J. Computer and Sysdlen Sciences, 1971, v.5, p.511-523.

57. Hack M. Analysis of production schemata by Petri nets. MACTR-94.- Cambridge (Mass.): M.I.T. Project MAC, 1972.-119 p.

58. Hack M. Corrections to analysis of production schemata by Petri net. Computation Structure Note 17.- Cambidge (Mass.): M.I.T. Project MAC, 1974.-11 p.

59. Hack M. Petri net languages, teohnical report 159.-Cambridge (Mass.): M.I.T. Laboratory of Computer Science (formerly Project MAC), 1976. 128 p.

60. Jones N.D., Landweber L.H., Lien Y.E. Complexity of some problems in Petri-nets.- Theoretical Computer Science, 1977» BT* 4, p. 277-299.

61. Jump J.R. Asynchronous Comtrol Arrays.- IEEE Transactions on Computers, 1974, vol. c-23, K* 10, p. 1020-1029.

62. Lipton R.J., Snyder L., Zalcstein Y. A Comparative Study of Models of Parallel Computation. In: 15th Annual Symp. on Switching and Automata Theory, 1974, p. 145-"'55.

63. Patil S.S. An asynchonous logic array. MAC thechnical memorandum 62.- Cambrigre (Mass.): M.I.T. Project MAC, 1975. 30 p.

64. Peterson J.L. Petri nets. Computing Surveys, 1977» vol.9,3, 225-252 p.65* Peterson J.L. Petri net theory and the modeling of systems. Englewood Cliffs (N.J.): Prentice-Hall, 1981.-290 p.

65. Pétri C.A. Kommunikation mit Automaten. -Bonn Univ., 1962,89 P.

66. Rackoff C. The covering and boundedness problems for vector addition systems. Theoretical Computer Science, 1978, H* 6, p. 223-231.

67. Toneseu I. A general formula for the asymptotic number of labeled conneced graphs and digraphs,* Revue roumaine de mathématiques pures et appliquées» 1978, t. XXIII, Bf* 4, p. 617-623.

68. Valette R., Diaz M. Top-down formal Specification and Verification of parallel control systems. Digital Proc., 1979, v. 4, H* 3-4, p. 181-1991. Указатель обозначений

69. А множество вершин сети Петри

70. А* множество выходов для множества вершин

71. А множество входов для множества вершин1А1 мощность множества А1. А)* А.А;д)+ А . • A j и. раз, ^ "i

72. AM6j ^ k-oe размещение в FC- сети

73. AM6J| число MGf- размещений FC- сети

74. ASM ^ г-ое SM- размещение в FC- сети

75. АвМ| число $М - размещений в FC- сети1. В оператор начала в ПГСА- бинарные отношения на множестве переходов сети1. С контур в графе

76. С константа в оценках сложности

77. CP сети полученные из корректных ПГСА

78. ЕС класс сетей, содержащих контуры

79. F оператор разветвления в ÏÏTCA

80. PC класс сетей свободного выбора G) - параллельная граф-схема алгоритма

81. JSJ+ реверсивно-дуальная сеть Петри j N. - число позиций сети N Н+ -множество {0,-1,2;.}и,О1. ОР1. ОРИ от ррм 1. Р>*> г я