4.2.1.       Дерево достижимости

Дерево достижимости представляет множество достижимости сети Петри. Рассмотрим, например, маркированную сеть" Петри на рис. 4.9. Начальная маркировка ее — (1, 0, 0). В этой начальной маркировке разрешены два перехода: и tz. Поскольку мы хотим рассмотреть все множества достижимости, определим новые вершины в дереве достижимости1) для (достижимых) маркировок, получающихся в результате запуска каждого из этих двух переходов. Дуга, помеченная запускаемым переходом, приводит из начальной маркировки к каждой из новых маркировок (рис. 4.10).

Это (частичное) дерево показывает все маркировки, непосредственно достижимые из начальной маркировки.

Теперь необходимо рассмотреть все маркировки, достижимые из новых маркировок. Из маркировки (I, 1,0) можно снова запустить ti (получая 1, 2, 0) и t2 (получая (0, 2, 1)); из (0, 1, 1) можно запустить t3 (получая (0, 0, 1)). Это порождает дерево, изображенное на рис. 4.11. Начиная с трех новых маркировок, необходимо повторить этот процесс, порождая новые маркировки, которые нужно

ввести в дерево, как показано на рис. 4.12. Заметим, что маркировка (0, 0, 1) пассивная; никакой переход в ней не является разрешенным, поэтому никакие новые маркировки из этой пассивной маркировки в дереве порождаться не будут. Кроме того, необходимо отметить, что маркировка (0, 1, 1), порождаемая запуском ’ tz в (0, 2, 1), была уже порождена непосредственно из начальной маркировки запуском

Если эту процедуру повторять снова и снова, каждая достижимая маркировка окажется порожденной. Однако получившееся

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

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

встречавшиеся в дереве. Такие дублирующие маркировки называются дублирующими вершинами-, никакие последующие маркировки рассматривать нет нужды — все они будут порождены из места первого появления дублирующей маркировки в дереве. Таким образом, в дереве на рис. 4.12 маркировка (0, 1, 1), получившаяся

в результате выполнения последовательности tit2tз, не будет порождать какие-либо новые вершины в дереве, поскольку она ранее встречалась в дереве в результате выполнения последовательности і2 из начальной маркировки.

Для сведения дерева достижимости к конечному представлению используется еще одно средство. Рассмотрим последовательность запусков переходов о, начинающуюся в начальной маркировке р и кончающуюся в маркировке р', р' > р.. Маркировка р' совпадает с маркировкой р, за исключением того, что имеет некоторые «дополнительные» фишки в некоторых позициях, т. е. р' = р + (р' — — р) и (р' — ^) > 0. Теперь, поскольку на запуски переходов лишние фишки не влияют, последовательность о можно запустить ^нова, начиная в р', приходя к маркировке р". Так как действие ■ последовательности переходов о добавило ;х' — фишек к маркировке р, она добавит также р' — р фишек и к маркировке р\ пожатому р" = р' + (р' — р) или р" = р + 2(р' — р). В общем можно запустить последовательность о п раз, получив в результате . Маркировку р + п(р' — р). Следовательно, для тех позиций, которые увеличивают число фишек последовательностью о, можно создать произвольно большое число фишек, просто повторяя по- J* следовательность а столько, сколько это нужно. В сети Петри на

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

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

Для построения дерева достижимости необходимы только эти операции над со.

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

Алгоритм начинает с определения начальной маркировки корнем дерева, т. е. граничной вершиной. До тех пор пока имеются граничные вершины, они обрабатываются алгоритмом.

Пусть х — граничная вершина, которую необходимо обработать.

1.   Если в дереве имеется другая вершина у, не являющаяся граничной, и с ней связана та же маркировка, р[х] = рГ«/], то вершина х — дублирующая.

2.   Если для маркировки jx[jc] ни один из переходов не разрешен (т. е. 6(цЫ, tj) не определено для всех I j £ Т), то х — терминальная вершина.

3.   Для всякого перехода tj£T, разрешенного в ц [х] (т. е. 6(у>Ы, t j) определено), создать новую вершину z дерева достижимости. Маркировка ц[г], связанная с этой вершиной, определяется для каждой позиции р; следующим образом:

а)   Если (іЫ і == о, то p[z] г = со.

б)   Если на пути от корневой вершины к х существует вершина у с цГу] < 6 (plxj, tj) и fx[«/l;< 6 (цЫ, tj)i, TO fikle = 0).

в)   В противном случае ц[г]{ = i)(|i[x], tj)t.

Дуга, помеченная tj, направлена от вершины х к вершине z. Вершина х переопределяется как внутренняя, вершина г становится граничной.

Когда все вершины дерева — терминальные, дублирующие или внутренние, алгоритм останавливается.

На рис. 4.14 представлено дерево достижимости для сети Петри на рис. 4.9. Дерево достижимости сети Петри с рис. 4.15 изображено на рис. 4.16.

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

Лемма 4.1. В любом бесконечном направленном дереве, в котором всякая вершина имеет только конечное число непосредственно

последующих вершин, существует бесконечный путь, исходящий из корня.

Доказательство. Начнем с корня в вершине х0. Поскольку имеется только конечное число непосредственно следующих за х0 вершин, но общее число вершин в дереве бесконечно, по крайней мере одна из непосредственно следующих за х0 вершин должна быть корнем бесконечного поддерева. (Если бы все поддеревья с корнями, непосредственно следующими за х0, были конечными, то и дерево с корнем х0 было бы конечным.) Выберем вершину %ь непосредственно следующую за х0 и являющуюся корнем бесконечного поддерева. Теперь одна из непосредственно следующих за ней вершин также является корнем бесконечного поддерева, выберем в качестве такой вершины х2. Продолжая таким же образом, получим бесконечный путь в дереве х0, xlt х2, ... . □

Лемма 4.2. Всякая бесконечная последовательность неотрицательных целых содержит бесконечную неубывающую подпоследовательность.

Доказательство. Возможны два случая:

1. Если какой-либо элемент последовательности встречается бесконечно часто, то пусть х0 является таким элементом. Бесконечная подпоследовательность х0, х0, х0, ... является бесконечной неубывающей подпоследовательностью.

2. Если никакой элемент не встречается бесконечно часто, тогда всякий элемент встречается только конечное число раз. Пусть х0 — произвольный элемент последовательности. Существует самое большее х0 целых, неотрицательных и меньших, чем х0 (О,..., х0—1), причем каждый из них присутствует в последовательности только конечное число раз. Следовательно, продвигаясь достаточно долго по последовательности, мы должны встретить элемент Хи Хі х0. Аналогично должен существовать в последовательности х2, х2 > хи и т. д. Это определяет бесконечную неубывающую подпоследовательность х0, хи х2... .

В обоих случаях бесконечная неубывающая последовательность существует. □

Лемма 4.3. Всякая бесконечная последовательность п-векторов над расширенными неотрицательными целыми (неотрицательные целые плюс символ <о) содержит бесконечную неубывающую подпоследовательность.

Доказательство. Доказываем индукцией по п, где п — размерность векторного пространства.

1.   Базовый случай (п — 1). Если в последовательности имеется бесконечное число векторов (ю), то они образуют бесконечную неубывающую последовательность. В противном случае бесконечная последовательность, образованная удалением конечного числа векторов (ю), имеет по лемме 4.2 бесконечную неубывающую подпоследовательность.

2.   Индуктивное предположение. (Допустим, что лемма верна для п, докажем ее справедливость для п + 1.) Рассмотрим первую координату. Если существует бесконечно много векторов, имеющих в качестве первой координаты о, тогда выберем эту бесконечную подпоследовательность, которая не убывает (постоянна) по первой координате. Если только конечное число векторов имеют ю в качестве первой координаты, то рассмотрим бесконечную последовательность целых, являющихся значениями первых координат. По лемме 4.2 эта последовательность имеет бесконечную неубывающую подпоследовательность. Она определяет бесконечную подпоследовательность векторов, которые не убывают по своей Первой координате.

В любом случае мы имеем последовательность векторов, не- ,убывающих по первой координате. Применим индуктивное предположение к последовательности n-векторов, которая получается В результате отбрасывания первой компоненты п + 1-векторов. Полученная таким образом бесконечная подпоследовательность является неубывающей по каждой координате. □

Докажем следующую теорему.

Теорема 4.1. Дерево достижимости сети Петри конечно. Доказательство. Доказательство проводим от противного. Допустим, что существует бесконечное дерево достижимости. Тогда

по лемме 4.1 в нем имеется бесконечный путь х0, хи х2, ..., исходящий из корня х0. (Число вершин, следующих за каждой вершиной в дереве, ограничено числом переходов т.) Тогда |і[х0], [а[*і], |а[х2],..— бесконечная последовательность n-векторов над N U {оі}, а по лемме 4.3 она имеет бесконечную неубывающую подпоследовательность |і[х,0] < |4*іЛ <    . Но по построению мы не можем иметь |і[х£] = [л[ху], поскольку тогда одна из вершин была бы дублирующей и не имела следующих за собой вершин. Следовательно, мы имеем бесконечную строго убывающую последовательность |і[х,0]С • Но по построению, так как |.і[хг] < < jj[хj], нам следовало бы заменить по крайней мере одну компоненту |а[хг£], не являющуюся о, на со в |і[Ху]. Таким образом, [x[x, J имеет по крайней мере одну компоненту, являющуюся со, |х[х,-,] имеет по крайней мере две ожомпоненты, а ц[х^ ] имеет по крайней мере п со-компонент. Поскольку маркировки n-мерные, ] имеет во всех компонентах со. Но тогда |і[х,-я+і] не может быть больше \і[хіп\. Пришли к противоречию, что доказывает, что наше допущение относительно существования бесконечного дерева достижимости неверно. □

Построение дерева достижимости было впервые описано Карпом и Миллером [148]. Используемый здесь вариант алгоритма был предложен Келлером [150]. Доказательство конечности, данное здесь, взято у Хэка [111], который принял за основу доказательство Карпа и Миллера [148].

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