Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984 (1184511), страница 22
Текст из файла (страница 22)
2. Задача достижимости нуля. 3. Задача достижимости подмаркировки. 4. Задача достижимости нуля в одной позиции. Эти теоремы и их доказательства принадлежат главным образом Хэку (116$. 5.3. Сети Петри а ограничениями В первых работах по сетям Петри, а также в некоторых современных работах сети Петри определяются в несколько более ограниченной форме, чем в определении, данном в гл.
2. В частности, иногда принимаются следующие два ограничения: Ограничение 5.1. Кратность любой позиции равна О или 1. Иначе говоРЯ, ЩРь Х(ХД) в=. 1 и 4~(Рь 0(Х;)) < 1 длЯ всех Р~ Е Р н Хх е Т. Это ограничивает входные и выходные комплекты до множеств. Ограничение 5.2. Никакая позиция не может быть одновременно входом и выходом одного и того же перехода. Х(Хх) О 0(1,) = О. Это часто формулируется как Щрь Х(Хх)) ф~(ро 0(Х,)) = — О для всех р; и Х;. Сети Петри, удовлетворяющие ограничению 5.1, называются ординарными. Сети Петри, удовлетворякивие ограничению 5.2, называипся сетями Петри беэ петель, или нерефлексивными сетями. Сети Петри, удовлетворяющие обоим ограничениям, назы- Сложность и разрешимость ваются щюстыми сои)яма Петри' >.
Зги классы сетей Петри соотносятся так, как показано на рис. 5.3. Подклассы модели обычных сетей Петри рассматривались по нескольким причинам. Основная причина заключается в том, что введение понятий сетей Петри в начале развития теории было неформальным.
Необходимость в кратных дугах и петлях при моделировании тогда отсутствовала. Кроме того, вероятно, казалось, Пети Петри дев летие.ж Ординарные сети Петри Где« «рьжв ыт дуе) Простые сети Петри Где« «ратньт ддг и петель) Рнс. 5.3. Взаимосвизи между классами сетей Петри. дуга означает внлючение; дуги своднмости будут ориентированы в противоположном направлении. что теория без этих усложнений будет проще. По мере развития теории стало ясно, что работать с более общими определениями не труднее. Использование моделей с этими ограничениями в современных работах объясняется стремлением исследователя к более простому и лаконичному изложению.
Однако зти ограничения не добавляют ничего к способности анализировать сети Петри. Рассмотрим для этих классов сетей задачу до тпжимости. Для того чтобы показать эквивалентность всех четырех классов сетей Петри, докажем следующее: Теорема 5.4. Задача достижимости эквивалентна для следующих классов сетей Петри: К Обычные сети Петри. 2.
Ординарные сети Петри. 3, Сети Петри без петель. 4. Простые сети Петри. Локазаи)ельстео. Из определений очевидны следующие сведения: К Задача до".тижимости для ординарных сетей Петри сводится к задаче достижимости для обычных сетей Петри. 2. Задача достижимостн для сетей Петри без петель сводится к задаче достнжимосгн для обычных сетей Петри. )) По аналогии с подобным поинтием в теории графов.
— Прим Ред. !24 Глава 5 3. Задача достижимости для простых сетей Петри сводится и к задаче достижимостн для ординарных сетей Петри, и к задаче достижимости для сетей Петри без петель. Покажем, что обычные сети Петри можно преобразовать в простые сети Петри таким образом, чтобы свести задачу достнжимости для обычных сетей Петри к задаче достижимости для простых сетей Петри. Это покажет, что все четыре задачи достижимости эквивалентны.
Для преобразования обычной сети Петри в простую сеть Петри используем следукицнй подход. Каждая позиция в обычной сети Петри заменяется кольцом позиций в простой сети Петри. На рис. 5.4 показан общий вид кольца позиций. Заметим, что набор фишек, помещенных в кольцо, может свободно двигаться по кольцу к любой позиции в любой момент времени; все они могут сгруппироваться в позиции р«л нли равномерно распределиться, покрывая все й, позиций кольца. Поэтому переход, для запуска которого необходимы три фишки из позиции рь может выбрать вместо всех трех из р, по одной из р,л, рса н р;л.
Аналогично переход, используюгцнй р; в качестве входа и а качестве выхода (петля). может иметь вход в рьь а выход в р;л, тем самым устраняя петлю. Формально для обычной сети Петри С, = (Р„Т„ /„О,) с маркировкой р, определим простую сеть Петри С = (Р„Т„ /, ОД с маркировкой р» следукхцим образом. Сначала для каждой позиции р~ Е Р1 определим целое й,: и,.
= гпах (4) (Р,, 1 (1 )) + 4) (Рм 0(/;))). »/~Т Сеть Петри с ограничениями С, определяется Р« =(рь»~р;Е.Рм ! (А ~ к«), Т,=Т,()(1, ь~р« „Г-Р,). Входная и выходная функции для «нормальных» переходов опре- деляются так, что ( ! если ! < 6 ( =Ф (р, 1, (1 )), ) О, в противном случае; Ф(рь„, О,(1,)) = ь м ° 1 (> если ф- (Р;, 1 (/г)) «" Ь ~ 4г (Р, /„(1 )) + + 44 (р,, О, (1,)), О, в противном случае; а для «кольцевых» переходов 1«(/пь) =(р .ь) 0,(1« „) = ( р« „)п = ! + (й ( 125 Сложность и Разрешимость Маркировка р определяется следующим образом: Рз ( Рь 1) = Рз(Р») дЛЯ Рт Ерз» р (р,. „) = 0 для 6~1.
"' «с Р»»с. 5.4. Кольцо позиций, используемое в простой сети Петри для представления позиции обычной сети Петри. Числе «; позиций, представляющих позицию рь определяется максимумом сумм кратностей позиции. Для любой маркировки р, достижимой в Сь по построению существует такая маркировка р» в С„что ~~.",р'(Рь ь) =- )ь(р,.) для всех р,. ЕР, В в частности, в любой момент времени в С можно переместить все фишки из рт ь в рьь Следовательно, можно определить маркировку р' следующим образом: р»(рт,) = р(р;) для р~ ЕР„ м(р,„)=одляй= 1, и р,' становится достижимой в простой сети Петри С тогда и только тогда, когда р достижима в С,. Е Таким образом, с точки зрения анализа обычные сети Петри и три ограниченных класса обычных сетей Петри — ординарные сети Петри, сети Петри без петель и простые сети Петри — эквивалентны, всякую сеть можно преобразовать в подобную сеть другого клас, са, сводя задачу достижимости для одной сети к задаче достижимости для другой.
Использованные в этом разделе конструкции принадлежат Хэку (11Ц. ! ше ~! Глава Б Свти Пвтра йю натела Рнс. Б.й. Своднмоеть задачи доетнжнмостн среди классов сетей Петри с различными типами ограничений. 5.4. Активность и достижимость Достижимость — важная задача сетей Петри. Другсй задачей, получившей много внимания в публикациях по сетям Петри, является активность. Как отмечено в равд. 4.1.4, активнссть связана с тупиками. Мы коснемся здесь двух задач, связанных с активностью сети Петри С = (Р, Т, Х, О) с начальной маркировкой р.
Сеть Петри активна, если активен всякий ее переход. Переход 1ь активен в маркировке р, если для всякой маркировки р' Е Й(С, р) существует последовательность Ш такая, что 1; разрешен в 6(р', о). Переход гь пассивен в маркировке р, если не существует достижимой маркировки, в которой бы он мог быть запущен. 0пределениеБ. 7. Задача активности. Активны ли все переходы 1ь6 Т? Определение 8.
8. Задача активности одного перехода. Активен ли данный переход 1; Е Т? Очевидно, что задача активности сводится к задаче активности одного перехода. Для нахождения решения задачи активности мы престо решим задачу активности одного перехода для каждого 1ь Е Е Т; если ]Т( = и, то мы должны решитып задач активности одного перехода. Сложность и раерешимаеть 127 Задачу достижимости можно также свести к задаче активности. Поскольку варианты задачи достижимости эквивалентны, мы рассмотрим задачу достижимости нуля в одной позиции.
Если перед нами стоят какие-либо другие задачи достижимости, их можно свести, как показано в равд. 5.2, к задаче достижимости нуля в одной позиции. Теперь, если мы хотим определить, может ли быть позиция ре нулевой в какой-либо достижимой маркировке для сети Петри С, = (Р» Т» 1» О,) с начальной маркировкой и» то построим сеть Петри С, = (Р„Т„Г„О«) с начальной маркировкой (е„которая будет активна тогда и только тогда, когда нулевая маркировка не будет достижима из р» Сеть Петри С, строится из С, введением двух позиций г, и г и трех переходов а» з и зе. Сначала модифицируем асе переходы Т» включая г, в качестве входа и выхода. Начальная маркировка р, будет включать фишку в г» Позиция г, — это позиция «действия», пока фишка остается в г» переходы Т, могут запускаться.
Следовательно, любая маркировка, достижимая в С» достижима также и в позициях Р, в С,. Определим переход а, так, что его входом будет г» а выход пуст. Это позволяет удалить фишку из г» запрещая запуск всех переходов в Т, и «замораживая> маркировку Р» (Заметим, что все переходы Т, находятся в конфликте и не только по определению, но и по построению могут запускаться каждый раз не более чем по одному.) Позиция г, и переход з, позволяют сети С, достичь любой достижимой маркировки, затем запуском з, заморозить сеть в этой маркировке. Далее необходимо проверить, является ли позиция ре нулевой. Введем новые позицию г, и переход ам имеющий в качестве входа р» а в качестве выхода г . Если р, может когда-либо стать нулевой, то этот переход не является активнь1м.
В действительности вся сеть будет пассивной, если в этой маркировке сработает переход з,. Следовательно, если р; может быть пустой, сеть не является активной. Если р; не может быть пустой, тогда з» всегда может быть запущен, помещая фишку в г,. В этом случае мы должны будем вернуть фишку в г, и гарантировать, что все переходы в С, активны. Необходима уверенность в том, что С, активна, даже если С, не является активной. Это обеспечивается переходом з>, который «наполняет» сеть С фишками, гарантируя тем самым, что, если фишка помещена в г, каждый переход активен. Переход зе в качестве входа имеет г„а в качестве выхода все позиции С, (все ре в С» г, и г»).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
