Теория вычислительных процессов

3.1. Если m[х](p)=w, то m[z](p)=w.

3.2. Если на пути от корневой вершины к x существует вершина y с m[y]<m' (где m' - маркировка, непосредственно достижимая из m [х] посредством запуска перехода t) и m[y](p)<m'(p), то m[z](p)=w. (В этом случае последовательность запусков переходов, ведущая из маркировки m [y] в маркировку m', может неограниченно повторяться и неограниченно увеличивать значение маркировки в позиции p.) В противном случае m [z](p)=--m'(p).

4. Строится дуга с пометкой t, направленная от вершины x к вершине z. Вершина х становится внутренней, а вершина z - граничной.

Такая обработка алгоритмом граничных вершин продолжается до тех пор, пока все вершины дерева не станут терминальными, дублирующими или внутренними. Затем алгоритм останавливается.

Важнейшим свойством алгоритма построения конечного дерева достижимости является то, что он за конечное число шагов заканчивает работу.

Пример 4.5. Конечное дерево достижимости сети Петри.

Сеть Петри:

Конечное дерево достижимости:

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

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

Доказательство. Пусть x0 корневая вершина. Поскольку имеется только конечное число непосредственно следующих за x0 вершин, но общее число вершин в дереве бесконечно, по крайней мере, одна из непосредственно следующих за x0 вершин должна быть корнем бесконечного поддерева. Выберем вершину x1 непосредственно следующую за x0 и являющуюся корнем бесконечного поддерева. Теперь одна из непосредственно следующих за ней вершин также является корнем бесконечного поддерева, выберем в качестве такой вершины x2. Если продолжать этот процесс бесконечно, то получим бесконечный путь в дереве - x0,x1,x2,…,xn,… .

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

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

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

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

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

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

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

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

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

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

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

Теорема 4.1. Дерево достижимости сети Петри конечно.

Доказательство. Докажем методом от противного. Допустим, что дерево достижимости бесконечно. Тогда по лемме 4.1 (и так как число вершин, следующих за каждой вершиной в дереве, ограничено числом переходов m) в нём имеется бесконечный путь x0,x1,x2,… , исходящий из корня x0. Тогда m [x0], m [x1], m[x2],… -- бесконечная последовательность n-векторов. над NatИ{w}, а по лемме 4.3 она имеет бесконечную неубывающую подпоследовательность m[x_k0]Јm[x_k1]Јm[x_k2]Ј….. . Но по построению дерева достижимости m[x_i]№m[x_j] (для i№j), поскольку тогда одна из вершин была бы дублирующей и не имела следующих за собой вершин. Следовательно, это бесконечная строго возрастающая последовательность m[x_k0]<m[x_k1]<m[x_k2]….. . Но по построению, так как m[x_i]<m[x_j] нам следовало бы заменить по крайней мере одну компоненту m [xj], не являющуюся w, на w в m [xj]. Таким образом, m [xk1] имеет по крайней мере одну компоненту, являющуюся w, m [xk2] имеет по крайней мере две m-компоненты, а m [xkn] имеет по крайней мере n m-компонент. Поскольку маркировки n-мерные, m [xkn] имеет во всех компонентах w. Но тогда у m [xkn+1] не может быть больше m [xkn]. Пришли к противоречию, что доказывает теорему.

4.4.2.2 Анализ свойств сетей Петри на основе дерева достижимости

Анализ безопасности и ограниченности. Сеть Петри ограниченна тогда и только тогда, когда символ w отсутствует в ее дереве достижимости.

Присутствие символа w в дереве достижимости (m[х](p)=w для некоторой вершины x и позиции p) означает, что для произвольного положительного целого k существует достижимая маркировка со значением в позиции p, большим, чем k (а также бесконечность множества достижимых маркировок). Это, в свою очередь, означает неограниченность позиции p, а следовательно, и самой сети Петри.

Отсутствие символа w в дереве достижимости означает, что множество достижимых маркировок конечно. Следовательно, простым перебором можно найти верхнюю границу, как для каждой позиции в отдельности, так и общую верхнюю границу для всех позиций. Последнее означает ограниченность сети Петри. Если граница для всех позиций равна 1, то сеть Петри безопасна.

Анализ сохранения. Так как дерево достижимости конечно, для каждой маркировки можно вычислить сумму начальной маркировки. Если эта сумма одинакова для каждой достижимой маркировки, то сеть Петри является сохраняющей. Если суммы не равны, сеть не является сохраняющей. Если маркировка некоторой позиции совпадает с m, то эта позиция должна был исключена из рассмотрения.

Анализ покрываемости. Задача покрываемости требуется для заданной маркировки m' определить, достижима ли маркировка m"іm'. Такая задача решается путём простого перебора вершин дерева достижимости. При этом ищется такая вершина х, что х, что m[x]іm'. Если такой вершины не существует, то маркировка m' не является покрываемой. Если она найдена, то m [x] определяет покрывающую маркировку для m' Если компонента маркировки m [x], соответствующая некоторой позиции p совпадает с m, то конкретное её значение может быть вычислено. В этом случае на пути от начальной маркировки к покрывающей маркировке имеется повторяющаяся последовательность переходов, запуск которой увеличивает значение маркировки в позиции p. Число таких повторений должно быть таким, чтобы значение маркировки в позиции p превзошло или сравнялось с м'(p).

Анализ живости. Переход t сети Петри является потенциально живым, тогда и только тогда, когда он метит некоторую дугу в дереве достижимости этой сети.

Доказательство очевидно.

Ограниченность метода дерева достижимости. Как видно из предыдущего, дерево достижимости можно использовать для решения задач безопасности, ограниченности, сохранения и покрываемости. К сожалению, в общем случае его нельзя использовать для решения задач достижимости и активности, эквивалентности. Решение этих задач ограничено существованием символа m. Символ m означает потерю информации: конкретные количества фишек отбрасываются, учитывается только существование их большого числа.

4.4.2.3 Матричные уравнения

Другой подход к анализу сетей Петри основан на матричном представлении сетей Петри и решении матричных уравнений. Альтернативным по отношению к определению сети Петри N в виде (P,T,I,O) является определение сети N в виде двух матриц D? и D+, представляющих входную и выходную функции I и O. Пусть каждая из матриц D? и D+ имеет m=кTк строк (по одной на переход) и n=кP столбцов (по одному на позицию).

Матричный вид сети Петри N=(P,T,I,O) задаётся парой (D?,D+), где

D?[k,i] = ^#(pi,tk) - кратность дуги, ведущей из позиции pi в переход tk.

D+[k,i] = #^(pi,tk) - кратность дуги, ведущей из перехода tk в позицию pi,

для произвольных 1ЈkЈm, 1ЈiЈn.

Пусть e[k] -- m-вектор, k-тый элемент которого равен 1, а остальные равны 0. Переход t_k, 1ЈkЈm, в маркировке m разрешен, если mіe[k]ЧD^-?. Результатом запуска разрешённого перехода tk в маркировке m является следующая ниже маркировка m':

m'=m - e[k]ЧD^- + e[k]ЧD⁺==m + e[k]ЧD,

где D=(D+ - D?) -- составная матрица изменений.

Размещено на Allbest.ru