Warning: session_start(): open(C:\Windows\temp\sess_or21h8vobu050dfukq7tt8h006, O_RDWR) failed: No space left on device (28) in C:\www\lemma4.1php\login.php on line 15 Warning: session_commit(): open(C:\Windows\temp\sess_or21h8vobu050dfukq7tt8h006, O_RDWR) failed: No space left on device (28) in C:\www\lemma4.1php\login.php on line 36 Warning: session_commit(): Failed to write session data (files). Please verify that the current setting of session.save_path is correct (C:\Windows\temp) in C:\www\lemma4.1php\login.php on line 36 Сети Петри: модификации и расширения

Начнём со знакомства с понятием сети.

Определение 1 Сеть — это тройка N = (S, T, F), где

  • S — множество элементов, называемых местами (S&neq;),
  • Т — множество элементов, называемых переходами (T&neq;,ST&neq;),
  • F(S×T)(T×S) — множество дуг (отношение инцидентности) такое, что dom(F)ran(F)=ST,

где dom(F)={xST|&exists;yST ◊ (x,y)F} и ran(F)={yST|&exists;xST ◊ (x,y)F} (т.е. любой элемент сети инцидентен хотя бы одному элементу (другого типа)).

Элементы множества ST будем называть узлами сети. Множеством входов (выходов) элемента  xST называется множество x={y|  (y,x)F}   (x={y|(x,y)F}). Элементами множества входов (выходов) места сети являются его входные (выходные) переходы. Аналогично, элементами множества входов (выходов) перехода сети являются его входные (выходные) места. Для заданного множества XST узлов сети N определим множества X=xXx  и X=xXx.

При графическом представлении сети для изображения переходов используются, как правило, прямоугольники или барьеры (вертикальные черточки), мест — окружности, а дуг — направленные стрелки. На рис. 1.5 изображено графическое представление сети N = (S,T,F), где S={s1,s2,s3,s4,s5}   множество мест, T={t1,t2,t3,t4}  множество переходов, F={(s1,t1),(s1,t2),(s2,t1),(s3,t2),(s4,t3),(s4,t4),(t1,s3),(t1,s4),(t2,s2),(t2,s4),(t3,s1),(t4,s5)}  множество дуг.

Введем понятия пути и цикла сети.

Определение 2 Путем называется последовательность узлов x1...xk сети N = (S, T, F) таких, что (x1,x2),...,(xk-i,xk)F. При этом говорят, что путь x1...xk  ведет из узла x1 в узел xk. Путь, ведущий из узла x в узел y, является циклом, если ни один из узлов не появляется в нем более одного раза и (y,x)F.

Последовательность s1t1s4t4s5 является путем, a s1t1s4t3 — циклом сети, изображенной на рис. 1.5.

Рассмотрим понятие подсети.

Определение 3   Тройка N' = (S',T',F') называется подсетью сети N = (S, T, F) (обозначается NN), если SS,TT и F=F((S×T)(T×S)). Если X(ST), то (SX,TX,F(X×X)) — подсеть сети N = (S, T, F), порождаемая множеством X.

Пример сети и ее подсети показан на рис. 1.6 а и б соответственно.

Определим некоторые свойства сети.

Определение 4  Пусть N = (S, T, F) — сеть и   X=ST. Тогда:

  • N — конечная сеть, если X — конечное множество;
  • N — чистая сеть, если  xX xx=;
  • N — простая сеть, еслиx,yXx=yx=yx=y;
  • N — связная сеть, если x,yX  (x,y)(FF-1)*;
  • N — сильно связная сеть, если  x,yX(x,y)F*;
  • тройка N = (S, T, F)  — двойник сети N, если  S&hat;=T,T&hat;=S и F&hat;=F-1.

Следующая лемма дает характеризацию связности и сильной связности сети.

Лемма 1 а)  Сеть (S, T, F) связна, если и только если ее нельзя разбить на две подсети (S1,T1,F1)  и  (S2,T2,F2)с непересекающими и непустыми множествами элементов такими, что верно:  S=S1S2,T=T1T2 и  F=F1F2.

б)   Связная сеть (S, T, F) сильно связна, если и только если для каждой ее дуги (x,y) существует путь из y в x.

Сеть, изображенная на рис. 1.5, является конечной, чистой, простой и связной. Подсеть, образуемая всеми узлами, за исключением узлов t4 и s5, является сильно связной. Пример сети и ее двойника показан на рис. 1.7.
Очевидны следующие свойства двойника сети.

Лемма 2  Пусть N = (S, T, F) — сеть и  N&hat;— ее двойник. Тогда

  • N&hat;  — сеть;
  • N&hat;&hat;=N.

Маркировки и последовательности срабатываний

Рассмотрим понятие маркировки сети. Пусть N множество натуральных чисел и N+ множество положительных натуральных чисел.

Функция M:SN называется маркировкой. Понятно, что маркировка может быть рассмотрена как мультимножество над множеством мест S. Кроме того, если места сети упорядочены s1,...sn  (n1), то маркировка может быть представлена в виде вектора (M(s1),...,M(sn)). Графически маркировка M изображается в виде M(s) фишек (черных точек) в месте s (см рис. 1.8). Нулевая маркировка сопоставляет каждому месту сети 0.

Пусть M — маркировка сети N. Место s называется маркированым при M, если M(s) > 0. Множество мест R маркировано, если хотя бы одно место из R маркировано. Общее количество фишек для множества мест R обозначается как M(R), т.е. M(R)=sRM(s). Ограничение маркировки M на множество мест R обозначается как M|R.

Переход tT  разрешен (может сработать, готов к срабатыванию) при маркировке M, если st  M(s)>0. Обозначим через En(M) множество переходов, готовых к срабатыванию при маркировке M. Срабатывание перехода t при маркировке M порождает новую маркировку М' (обозначается как M [t> M'), где

sS ◊ M'(s)={M(s)-1,  st\t,M(s)+1,st\t,M(s),  иначе.

Таким образом, при срабатывании перехода t сети N из каждого его входного места удаляется по одной фишке и в каждое его выходное место добавляется по одной фишке. Маркировка называется мертвой, если ни один переход не может сработать при ней.

В качестве примера рассмотрим сеть, показанную на рис. 1.8, и ее маркировку (2,1,0, 0, 0). Переход t1 разрешен при этой маркировке. Срабатывание перехода t1 при маркировке (2,1, 0,0,0) порождает новую маркировку M = (1,0,1,1,0). Маркировка (0,1,1,0,0) этой сети является мертвой.

Последовательность переходов σ=t1t2...tnT* называется последовательностью срабатываний, если существуют маркировки M1,M2,...,Mn такие, что Mi[ti>Mi+1 для всех 1i<n. В этом случае говорят, что маркировка Mn  достижима из маркировки M1 посредством последовательности срабатываний σ (обозначается M1[σ>Mn). В случае пустой последовательности срабатываний  ε имеем M [ε > М для любой маркировки M. Будем писать M [* > М' и говорить, что маркировка М' достижима из маркировки M, если M[σ>M для некоторой последовательности срабатываний σ. Множество маркировок, достижимых из M, обозначается как [M >. Если M[t1>M1[t2>M2... для бесконечной последовательности переходов σ=t1t2..., то σ — бесконечная последовательность срабатываний. В этом случае будем писать M[σ>. Будем говорить, что последовательность σ переходов разрешена при маркировке M, если M[σ>M для некоторой маркировки М' (если σ конечна) или M[σ> (если σ бесконечна).

Переход сети называется мертвым при маркировке M, если он не может сработать при любой маркировке, достижимой из M. Место сети называется мертвым при маркировке M, если оно не маркировано (не содержит фишек) при любой маркировке, достижимой из M.

Утверждение 1  Конечная или бесконечная последовательность  σ  переходов разрешена при маркировке М, если и только если любой конечный префикс  σ  разрешен при M.

Доказательство.
() : Непосредственно следует из определения разрешенной последовательности переходов.
() : Если σ конечна, то результат очевиден. Рассмотрим случай, когда σ бесконечна. Пусть σ=t1t2.... Возьмем i1. Покажем, что ti может сработать при некоторой маркировке, достижимой посредством последовательности срабатываний t1t2...ti-1. Пусть τ=t1t2...ti. Так как τ — конечный префикс последовательности σ, то τ разрешена при M, по предположению индукции. Поэтому существуют маркировки M1,M2,...,Mi такие, что M[t1>M1[t2>...[ti-1>Mi-1[ti>Mi. Результат следует из того, что ti  может сработать при Mi-1.    □

Заметим, что для каждой конечной последовательности σ переходов сети существует маркировка, при которой σ разрешена. Например, если σ имеет длину k, то можно взять маркировку, которая сопоставляет k фишек каждому месту сети.

Матрица инцидентности сети

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

Определение 5  Пусть N = (S, T, F) — сеть. Матрица инцидентности  M : (S,T){-1,0,1}  сети определяется следующим образом:

M(s,t)={0,((s,t)F(t,s)F)((s,t)F(t,s)F),-1,(s,t)F(t,s)F,1,(s,t)F(t,s)F.

Если перенумеровать места {s1,...,sn} и переходы {t1,...,tm} сети, то M(si,tj) обозначает запись в i-ой строке и j-ый столбец матрицы инцидентности M. Столбец S{-1,0,1} матрицы М, связанный с переходом  t, обозначается t. Аналогично, строка T{-1,0,1} матрицы M связанная с местом  s, обозначается s.

Матрица инцидентности сети, показанной на рис. 1.5, выглядит следующим образом:

 

t1

t2

t3

t4

s1

-1

-1

1

0

s2

-1

1

0

0

s3

1

-1

0

0

s4

1

1

-1

-1

s5

0

0

0

1

Запись M(s, t) соответствует изменению маркировки места  s, вызванному срабатыванием перехода  t. Следовательно, если переход  t  может сработать при маркировке  M  и верно, что  M [t > М', то также верно, что  М' = M + t.

Как отмечено выше, переход t1 сети на рис. 1.5 разрешен при маркировке (1,1,0,0,0) и его срабатывание порождает маркировку  М' = (0, 0,1,1, 0). Также верно, что (1,1,0,0,0) + (-1, -1,1,1, 0) = (0,0,1,1,0). Для того чтобы обобщить этот факт, нам понадобится следующее

Определение 6  Пусть N = (S, T, F) — сеть и  σ  — последовательность переходов сети. Вектор Париха  σ:Tпоследовательности  σ  отображает каждый переход t из T в количество включений t в  σ.

Например, вектор Париха для последовательности t2,t4.t2,t1 — это (1,2,0,1), тогда как вектор Париха для последовательности t1 — это (1,0,0,0).

Теперь рассмотрим следующий факт: для каждого перехода  t  верно, что t = М  t, и поэтому если  M [t > М', то  М' = M + M  t (где  M  и  М'  взяты как столбцы). Следующая лемма обобщает этот факт для произвольной последовательности срабатываний.

Лемма 3  Пусть  N=(S,T,F)сеть. Для произвольной конечной последовательности срабатываний такой, что M[σ> M', верно

M=M+ M σ.

Доказательство. Будем доказывать индукцией по длине |σ| последовательности σ.

|σ| = 0. Тогда верно, что M = M'. Имеем, что σ0, что доказывает результат.

|σ| > 0. Тогда σ=τt для последовательности τ и перехода t. Пусть M[τ > L[t > M'. Тогда имеем:

M'      = L + t (по определению t),

          = L+ M  t (по определению t),

          = M+ M τ+ M  t (по индукционному предположению),

          = M+ M  (τ+t)

          = M+ M  τt (по определению вектора Париха),

          = M+ M  σ (поскольку σ=τt ).   □ 

В сети на рис. 1.5 для последовательности σ=t1t3t2t4 имеем, что (1,1,0,0,0)[σ>(0,1,0,0,1). Используя матрицу инцидентности данной сети (см. выше) и вектор Париха (1,1,1,1) последовательности σ, легко проверить справедливость леммы.

Из леммы 3 следует, что маркировка, достижимая посредством последовательности срабатываний, зависит только от количества включений каждого перехода в данную последовательность, а не от порядка, в котором следуют переходы.

Далее покажем, что если последовательность σ разрешена при маркировке M, то она разрешена при любой другой маркировке большей, чем M.

Лемма 4  Пусть N = (S,T,F) — сеть и M, L — маркировки сети.

а)  Для некоторой конечной последовательности переходов верно

M[σ>M'(M+L)[σ>(M'+L),

б)  Для некоторой бесконечной последовательности переходов верно

M[σ>(M+L)[σ>.

Доказательство.

а) Будем доказывать индукцией по длине |σ| последовательности σ.

|σ| = 0. Очевидно.

|σ| > 0. Пусть σ=τt для последовательности τ и перехода t. Кроме того, предположим, что M[τ>M''[t>M'. Тогда, по предположению индукции, имеем, что (M+L)[τ>(M''+L). Так как t может сработать при M'', то t может сработать при (M'' + L), согласно правилу срабатывания перехода. По лемме 3, имеем, что (M''+L)[t>(M''+L+Mt). Поскольку вновь, по лемме 3, верно, что M'=M''+Mt, то имеем, что (M''+L)[t>(M'+L). Результат (M+L)[σ>(M'+L) следует из того, что σ=τt.

б) Используя утверждение 1, достаточно показать, что каждый конечный префикс σ разрешен при маркировке M + L. Вновь, по утверждению 1, верно, что каждый конечный префикс σ разрешен при маркировке M. Результат следует из пункта а).    □

Последовательность срабатываний не предоставляет полной информации о причинной зависимости между переходами сети. Например, если последовательность t1t2 разрешена при маркировке M, то это не означает, что во всех последовательностях срабатываний t2 всегда следует за t1. Понятно, что в случае, когда множества t1t2 и t1t2 различны, то переходы t1, t2 могут срабатывать параллельно, и последовательность t2t1 разрешена при M. Следующая лемма устанавливает более общее условие, при котором включения переходов в последовательностях срабатываний могут быть переставлены.

Лемма 5  Пусть  N=(S,T,F)сеть и U, V — различные подмножества переходов сети такие, что  UV=. Далее, пусть σ — (конечная или бесконечная) последовательность переходов такая, что  A(σ)UV, A(σ)={tT|t=σ(i)  для некоторого  i}. Тогда:

а)  если — конечная последовательность срабатываний, то

M[σ>M'M[σ|Uσ|V>M';

б)  если σ — бесконечная последовательность срабатываний и σ|U — конечная последовательность, то

M[σ>MM[σ|Uσ|V>;

в)  если σ — бесконечная последовательность срабатываний и σ|U — бесконечная последовательность, то

M[σ>M[σ|U>.

Доказательство.

а) Сначала покажем справедливость следующего утверждения: если L[v>K[u>L' для произвольных маркировок L, K, L' и переходов uU и vV, то L[u>K'[v>L' для некоторой маркировки K'. Так как uU, vV и UV=, то uv=.

Покажем следующее:

L(s)1 для каждого места sv,

L(s)1 для каждого места su,

L(s)2 для каждого места svu.

Предположим, что sv. Тогда имеем, что L(s)1, поскольку v может сработать при L.

Предположим, что su. Тогда имеем, K(s)1, поскольку u может сработать при K. Так как uv=, то верно, что sv. Таким образом, срабатывание перехода v не может увеличить число фишек в месте s, т.е. L(s)K(s). Следовательно, имеем L(s)1.

Предположим, что svu. Тогда имеем, что K(s)1, поскольку u может сработать при K и su. Так как sv и sv, то верно, что K(s)=L(s)-1. Следовательно, имеем L(s)2.

Таким образом, u может сработать при L, поскольку L(s)1 для всех мест su. Пусть L[u>K'. Покажем, что v может сработать при K'. Далее, пусть sv. Если su, то верно, что K'(s)L(s)1. Если su, то имеем, что K'(s)L(s)-1 и L(s)2, поскольку K'(s)1. Таким образом, маркировка K' маркирует каждое место в v, и поэтому v может сработать при K'.

Последовательности uv и vu имеют идентичные вектора Париха. Согласно лемме 3, обе последовательности приводят из маркировки L в одну и ту же маркировку L', что показывает корректность утверждения.

Далее, рассмотрим конечную последовательность срабатываний σ такую, что M[σ>M'. По утверждению, перестановка смежных элементов v u в σ, где vV и uU, дает другую последовательность срабатываний τ такую, что M[τ>M'. Так как U и V — различные множества и каждый переход, включенный в σ, принадлежит множеству UV, то τ — это последовательность вида σ|Uσ|V, что доказывает результат.

б) Пусть σ', σ'' — последовательности такие, что σ=σ'σ'', и только переходы из V включены в σ''. Такие последовательности существуют, поскольку σ|U — конечная последовательность, по предположению.

Пусть M[σ'>M'[σ''>. Применив пункт а) к последовательности σ', получим M[σ'|Uσ'|V>M'. Так как никакой переход, включенный в σ'', не принадлежит U, то имеем, что σ|U=σ'|U. Кроме того, поскольку никакой переход, включенный в σ'', не принадлежит V, то верно, что σ|V=σ'|Vσ''. Так как σ'' разрешена при M', то σ|Uσ|V разрешена при M.

в) Согласно утверждению 1, достаточно показать, что каждый конечный префикс τ последовательности σ|U разрешен при M. Рассмотрим конечный префикс τ' последовательности σ|U и соответствующий конечный префикс τ последовательности σ такие, что τ'=τ|U. По пункту а), последовательность τ|Uτ|V и, в частности, ее префикс τ|U=τ разрешены при M.    □