Книжка по сетям Петри, страница 8

Обе сети А и В строятся добавлением разных переходов к одной и той же сети С, которая. в свою очередь, строится из сетей та и В. Она как бы кодирует объединение Я (А) О Я (В), и ниже будет использован тот факт, что Я(А! С Я(В) Я(В) =Я(А! ОЯ(В). Способ конструирования сетей С, А', В' покааан на рнс. 2.9. Предполагается, что сети А и В имеют одно и 30 то же множество мест (в противном случае добавляют. ся новые места, как в доказательстве теоремы 2В, и сопоставленные друг другу места помечается одинаковы.

ми символами) . Иэ сетей А и В убрана начальная разметка. Она устанавливается пере. ходами Г1 и гт способом, указанным на рис. 2.10. На нем показан пример, как начальнап Разметка мест Рь ° Ры Рз может быть задана с помощью дополнительного перехода и оаного места Рс с единичной начальной разметкой. Переход т, "запускает" сеть А, передав фищку из места Р»+1 В месТО Р»+з. ПОследнее является входным и вы. Рис. 2,9. ходным для всех мест сети А и служит стартовым и одновременно выключающим местом этой сети. Переход г» устанавливает также начальную разметку для сети А.

Аналогичную роль играет переход гз для сети В. Таким образом, в зависимости ОТ ТОГО, Какой иэ ПеРехОДОВ Т1. Гт СРаботаат парпыы, Сеть С функциоинруат далее как сеть А или как сеть В. Сеть А строится по сети С добавлением перехода, который "выключает" сеть А, изымая фищку из места Р„+з. Это может случиться только в том случае, если вначале первым сработал переход г, и сеть С моделирует работу сети А. Аналогично СЕть В' строится по сети С добавлением еще одного перехода гс, который выключает сеть В.

Легко видеть, что Я(С) = Я(А) Х ((О, 1, О) ) О Я(В) Х ((О, О, П) О ((О,....О. 1, О, ОЦ, где (1, О, 0), (О, 1, О), 10, 0„1) — достижимые в С разметки местр,. 1,Р,+2, Р.+з; В(А') = В(С)О Я(А) Х ((О, О, О!); В(В') = В(А) О В(В) Х ((О, О, О) > = В(С) 1.1 (В(А) О В(ВП Х((О, а, О) ) . Так как разметка ЭГ(Р„+,, р, +т, р„,з) (О, О, 0) не достижима в се. ти С, то ДО йО РО Я(А') В(В') Я(А) ~ В(В).

(:) Поскольку множество достижимых разметок сети Петри характеризует, в некотором смысле, множество возможных ситуаций (состояний) в сети и в моделируемой ею дискретной системе, проблемы Ю включения и В-эквивалентности привлекли внимание на первых же этапах исследований сетей Петри. Рис. 2Л О. 31 С практической точки зрения проблема Я-эквивалентности, например, интересна потому, что разработка различных систем оптимизирующих преобразований сетей может потребовать сохранения достижимых разметок.

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

Неоднократные попытки доказать общепринятую гипотезу о разрешимости последней. в том числе опубликованные, страдали одним общим недостатком — в доказательствах были обнаружены ошибки. Последней работой в этом ряду является статья Майра [ВЗ[, в которой приведено очередное доказательствр разрешимости проблемы достижимости.

Мы ограничимся рассмотрени. ем вопроса об эквивалентности проблемы достижимости и живости. Доказа. тельства соотватствующих теорем содержат ряд приемов, которые кеогут представлять интерес в других задачах анализа свойств сетей Петри [42, 46[. Проблема достижимости состоит в обнаружении алгоритма, с помощью которого для любой сетиВ и для любой разметки М е Р) ! Р ! можно выяснить, М Е Я (В)? Более частной представляется проблема, в которой выясняется достижимость нулевой разметки 0 = (О,..., О). )Р! Т вор ем а 2.11.

Проблема достижимости произвольной разметки сводится к проблеме достижимости нулевой разметки. Доказательство. Пусть задана сетьВи разметкаМЕй)! !. Покажеы, что Вможно преобразовать в сеть В'такую, чтоМЕЯ (В) тогда и только тогда. когда 0 Е Я (В !. Соответствующее преобразование показано на рис.

2.11. Пока место Ое содержит фишку, сеть В' функционирует точно так же, как и сеть В. После срабатывания па)юхода те место 4Ъ полУ- чает фишку. Каждое из мест Оп 1 ~)~п, п = )Р[, имеет в сети В' начальную разметку Мь (д!! =М (р!). Из этого следует, что сетьВможет достигнуть нулевой разметки только в том случае, если все места 41,..., О„и все мес. та р,,..., Р„лишатся фишек. В свою очередь зто возможно только при достижении сетью В разметки М.

Переход гезаи вершает "очистку" сети В от фишек, убирая фишку из места дь. Поэтому решение проблемы достижимости произвольной разметки в сети В можно свестн к решению проблемы достижимости нулевой разметки в сети В . С) Т е о р е м а 2.12. Проблема достижимосги разметки сводится к пр)з(элема живости сети. Д о к а з е т е л ь с т в о. В силу теоремы 2.11 Р„ достаточно показать сводимость проблемы достижимости нулевой разметки к проблеяв живости.

В свою очередь для этого достаточно показать, что для произвольной сети В можно постро- Р, ить сеть В такую, что В жива тогда и только тогда, когда в сети В не достижима нулевая Рис 2.11. разметка. Построение В' показано на рис. 2:12. 32 Сеть ДС' функционирует следующим обрезает. э До срабатывания переходов сь или любого перехода Сл 1 < С ч.п, СЕТЬ ДС' ребатавт ТОЧНО таК жв КаК И сеть ДС. Если сьсработает раньше, чем любой из переходов сп 1 <У< л, то возможны два случая.

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

Отседа следует, что для любого перехода с сети д( с-тупиковап разметка должна иметь нулевую проекцию на места р,,..., р„сети ДС. Наоборвт, если в Д(достижима нулевая разметке, то в сети д/ переходы сь, сл 1 < с' < л, являются потенциально мертвыми. Таким образом, сеть ДС жива тогда и только тогда, когда в Мне достижима нулевая разметка. П Для доказательства сводимосги проблемы живости к проблеме дости. жимасти рассьзотрим более детально свойства с-тупиковых разметок. Пусть О, — множество всех с-тупиковых раэметок сати Петри с л местами. Л е м м а 2.4. Мкозсвство Р, монотонно.

Доказательство. ПустьМ, ЕО,и Мэ <Мы Предположим, что Мт ф,Рк т.в. СущЕСтеуЮт раэМвтКа МЭ Е СС (ДС, МЭ ) И ПаопвдааатвЛЬНОСтЬ срабатыванийттакие, чтоМэ [т)Мэ, и переходс может сработать при Мэ. Но, по теореме. 1.1, переход с может также сработать при разметке Мь такой, что М1 [т ) Мч и Мч = Мз + [Мэ — М, [, т.е. М, р О,, что противоречит начальному предположению. Е) Л е м м а 2.б. МкожвствоОт максимальных элементов множества О, конечно для любой сети Петри и может быть зфб)активно построено. Д о к азател ьст во.

Иэ определений множества0, и его множества максимальных элементов следует, что с, является множеством несравнимых по отношению<векторов из(Э[". В силу леммы 2.2 множество От конечно. Его мсэкно построить следующим способом. ЗаФиксируем множество(0, ы)" всех векторов длины л, составленных из 0 и со. В этом множестве выделим подмножество Х, максимдльных с-тупиковых векторов: Х, =[МЕ[0, ш)ч ! М вЂ” с-тупиковыд и 1ГМ': М') М~ М вЂ” нес тупиковый). Ясно, что множество Х, является конечным множеством несравнимых по отношению~с-тупиковых векторов, и ано мажет быть эффективно построено, так как по теореме 2.4 можно для любого вектора из[0, со)ч выяснить, является ли сн с-тупиковым.

Если любая нулевая компонента вектора изХ,заменить нас|, то получится вакса(з, не принадлежащий Х,, так как ан не будет с-тупиковым. Таким образам, для любого вектора МЕХ, существует вектор М' М+ К (М), где К (М! Е 3)ч, причем М'является с-тупиковым, но любой вектор М" > М уже не является с- уликовым. Для каждого М Е Х, вектор К (М! может быть найден последовательной 33 проверкой на г-тупиковость векторов М,М+К,,М+К,,...,М+К(м», где 0 < К, < Кт <... С К (М» — конечнап цепь векторов из й»". Мнекество ь» можно представить кви(м+ К (М»» М Е Х,», откуда следует, что его можно эффективно построить с помощью ояисаиной процедуры поиска векторе К (М» для каждого МЕ Хп П Т е о р в м а 2.13. Проблеме живости сети Петри сводится к проблеем достижмнссти некоторой разметки Доказательство.

Пусть известно, что размвткамдостижима везти»у. Тогда, если для произвольного перехода т в множества 0» существует вектор М' такой, чтем См, то переход г ие является живым. Наоборот, если известно, что с ие является живым переходам, то существует т-тупиковая разметка М Е В (»у» такая, что ЗМ' Е О,: М < М'. Таким образом, с является потеициально мвртвыы. еСли и тоЛЬкО воли ЗМ' Е с»„ИМЕВ(»У»:М< С М'. Поскольку множество (э, конечно и меает быть эффективно построеьа, то длп устаиовлеиия того факта, чта переход т является потеициельно мертвым, достаточно установить достижимость разметки М < М Е Е О,. Так как число мрехадов в сети»У конечно; то живость сети мамка установить, противел дпп каждого пцтахода, является ли ан живым или по. таициапьно мертвым.