Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984 (1184511), страница 40
Текст из файла (страница 40)
Когда вершина а запускается, она удаляет фишку из дуги Б и помещает фишки на дугу А и дугу В (логика И). Вершина д, с другой стороны, будет помещать фишки либо на дугу К, либо на дугу 6 (логика ИЛИ). Вершина 1 является разрешенной, когда присутствуют две фишки на дуге ? нли одна фишка на дуге К. Определение 8.1. Граф ?3СЕА есть шестерка С = (У, А, ?., Я, Б, Р), где У = (оь па, ..., п,) — множество вершин; А = (аь а„..., а,)— множество дуг; Е = (Е, ?.+): У вЂ” ~ (:», +) — входное (Е ) и выходное (Ь+) отображения логики па вершины графа; 9 = Щ, Я4): У х А -э- й? — входная (Я ) и выходная (Я') степень каждой пары Рис.
8.16. Преобразование частей графа $3С1.А в сети Петри, Модели параллельных вычислений Рис. 8.17. Сеть Петри, экаииалеитиаи графу 0СЬА, иа рис. 8,14. дуга-вершина; Я е А — начальная дуга; и е А — конечная дуга. Дуги графа определяются как упорядоченные пары множеств вершин. Первая компонента пары есть множество входных вершин, а вторая компонента — множество выходных вершин.
Начальная дуга имеет пустое множество входных вершин, а конечная дуга— пустое множество выходных вершин. Глава 8 228 Преобразование графа 1)С1.А в сеть Петри достаточно просто из-за надобности этих систем. Каждая дуга в графе 1)СЕА представляется позицией в сети Петри. Кроме того, представим вершину ч о позицией ра и двумя переходами 1„и г,.
Первый переход представляет инициирование операции, связанной с вершиной о, Грибббl ПСсЛ Сети Петри Системы с сссйисениими Р~Р- системы Гри ри Вычислений Мснечнбее иВтсмитбб МпрнирсВинные арарата Рие. 8.18. Добавление графов АНХЕЛ к иерархии моделей. а второй переход представляет завершение этой операции. Это схематично изображено на рис. 8.15 (моделирование вершин графа 1)СЕА переходами инициирования и завершения не строго обязательно, но удобно).
На рис. 8.16 показано как входная и выходная логики графов 1.1С1.А представляются эквивалентными сетями Петри. Степень больше единицы моделируется несколькими дугами между позициями и переходами в сети Петри. На рис. 8.17 граф 1.)СЕ с рис. 8.14 преобразован в эквивалентную сеть Петри. Это преобразование показывает, что мощность моделирования графов 1.1С1.А вкладывается в мощность моделирования сетей Петри. Очевидно, что сеть Петри может быть преобразована в эквивалентный граф УСЕА посредствам представления позиций дугами графа 1)С1.А, а переходов — вершинами с входной и выходной логикой И. Таким образом, эти две модели эквивалентны по своей мощности моделирования, На рис.
8.18 показана модифицированная иерархия моделей. Модели париллельнык еыииелений В.У. Системы замещения и сложения ееиторои Если вы бегло просмотрите библиографию, то заметите, что в названиях большинства ссылок упоминаются не сети Петри, а сислеляа сложения аектороа. Системы сложения векторов были введены Карпам и Миллером 1148) как математическое средство анализа систем параллельных процессов. Благодаря их простому матема-гическому определению системы сложения векторов обычно используются для формального доказательства свойств сетей Петри нли подобных систем.
Определение 8.2. Сисгпека сложения аааиороа )г есть пара )г = = (В, з), где В = (Ь„Ь„..., Ь ) — множество из т векторов, называемых базисными векторами или векторами смещения. Вектор з есть начальный вектор. Все векторы состоят из и целых величин. Элементы з неотрицательны. Множество достижимости системы сложения векторов 1г обозначается Я()г) и может быть определено рекурсивно с помощью следующего определения; , Определение 8.3. Множество достижимости Я(й) для системы сложения векторов )г = (В, з) есть наименьшее множество, для которого верно, что: 1. зЕР(И; 2.
Если х е й(У) и (х+ Ь;) - О, то (х+ Ь,) е Л(У), либо посредством следующего определения: Определение 8.4. х 6 И(У), если существует такая последовательность Ь;,, Ь;,, ..., Ььь базисных векторов, что х = з + .'5„'Ь, и ! з+,~~' Ь, ~О для всех г: О (г<- й. г — 1 У Из этих определений легко видеть, что системы сложения векторов и сети Петри эквивалентны. По данной сети Петри мы можем построить систему сложения векторов, начальным вектором которой является начальная маркировка, а базисные векторы взаимно однозначно соответствуют переходам.
1ь' компонент векторов системы сложения векторов соответствуют маркировкам п позиций сети Петри или (в случае базисных векторов) изменениям, происходящим из-за запуска соответствующего перехода. Аналогично система сложения векторов может быть преобразована в эквивалентную сеть Петри использованием позиций для компонент векторов и переходов для представления базисных век- Глава о торов. На рис. 8.19 иллюстрируется эквивалентность этих двух моделей. Фактически система сложения векторов эквивалентна сетям Петри без петель. Напомним, что в присутствии петель изменение может быть нулевым, а число фишек в позиции из петли должно быть ненулевым.
Это не уменьшает мощность системы сложения векторов, Ь1 (-1, 2, о, о) а, =<-),о,о. ц в,-ш,)„-)„ц в,=ш,-к), ц Рис. 8.19. Сеть Петри и эквивалентная ей система сложения векторов. поскольку мы видели (в разд. 5.3), что сети Петри без петель эквивалентны обычным сетям Петри. Однако для более непосредственного моделирования сетей Петри с петлями в модели, подобной системе сложения векторов, Келлер определил системы замещения векторов (15()1. Определение 8.5. Система замещения векторов состоит из начального вектора в О и т пар векторов (Уь У)), таких, что О) ~ Уь Векторы О) называются векторами проверки. Множество достижимости переопределяется так, что в принадлежит множеству достижимости, и если х входит внегои х+ У; ~ О, то х+ У;также входит в множество достижимости.
В модели системы замещения векторов явно определяется проверка на разрешение перехода от действия по запуску перехода. Эквивалентность систем замещения векторов сетями Петри (общего вида) очевидна. Добавляя системы сложения векторов и системы замещения векторов в нашу иерархию, получаем иерархию, изображенную на рис. 8.20. Важность систем сложения векторов и систем замещения векторов заключается в их простом математическом определении и полезности этого определения для доказательства математических свойств систем. Модели ласаллелвиых вычислений Системы Системы Сети ааммоения = — сложения = — Петра Велтнорой Векторос Системы с соойцениями Р/У- системы l' Гртрм Вычислений Раненные аВтоматм 'Рис.
8ЛО. Добавление систем сложении векторов и систем замежеиия векторов к иерархии моделей. Рисширпнные сипи Петри Гриапп — УСсп Системы с сппсиеппиями РГй - ситнемюп Гра~ры Вычислений Втг нами айутмитм Маркер исанние ерау~ы Рис. 8.2!. Полная иерархии моделей параллельных вычислений. ВВаркароттяает впарчм Систтны Системы замещения= аппменип Веепюрао Лектпрне | Сент и Петри 230 Глава 8 8.8. Расширенные модели сетей Петри В качестве последнего дополнения к нашей иерархии вспомним о моделях расширенных сетей Петри, изученных в гл. 7: сети Петри с областями ограничений, переходами исключающее ИЛИ, переключателями, сдерживающими дугами, приоритетами или временнычи ограничениями. Мы видели, что все эти модели эквивалентны машинам Тьюринга. Таким образом, эти модели строго включают модели сетей Петри.
Окончательная иерархия моделей изображена на рис. 8.21. 8.9. Замечания н литературе Исследования [240, 5, 178[ должны быть прочитаны в первую очередь, поскольку наиболее тесно связаны с тематикой главы. Следует также прочесть обзоры [41, 201 и работы [107, 1081. В этих статьях имеются ссылки на оригинальные работы по отдельным моделям, Модель Рнддла [258[ кажется наиболее предпочтительной для моделирования больших программных систем и заслуживает детального изучения. 8ЛО. Темы для дальнейшего изучения 1. Расширьте иерархию, приведенную на рис.
8.21, включив в нее ограниченные модели сетей Петри, обсужденные в гл. 7: сети Петри со свободным выбором и правильные сети Петри. 2. Исследуйте свойства языков, определенных классами моделей, рассмотренных в этой главе, и соотнесите их с регулярными, контекстно-свободными и контекстно-связанными языками. 3.
Определите разрешимость задачи достижимости для каждого из классов моделей, обсужденных в этой главе. 4. Расширьте работу, проделанную в этой главе, и включите модели, описанные в [2, 3, 180, 260, 271, 2841. ОБЗОР ТЕОРИИ КОМПЛЕКТОВ Теория мни»сеств используется в математике и вычислительной ' технике длительное время.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
