2.2.3 Тупики, ловушки, кластеры

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

Начнем с рассмотрения некоторых вспомогательных понятий.

Пусть M — множество маркировок M сети N таких, что ОСП (N,M) жива. По определению свойства живости, если (N,M) жива и L достижима из M, то ОСП (N,L) также жива. Поэтому, каждая маркировка, достижимая из маркировки, принадлежащей множеству M, также принадлежит M. Будем называть это множество маркировок стабильным.

Множество M маркировок сети  стабильно, если MM[M>M. Элемент стабильного множества будем называть  стабильным предикатом. Из данного определения легко видно, что для того чтобы определить, является ли предикат стабильным, достаточно для каждого перехода t проверить следующее условие:

(MMM[t>L)LM.

Рассмотрим множество мест {s1,s2} сети, показанной на рис. 2.23. Для каждого перехода t данной сети верно

(M({s1,s2})=0M[t>L)L({s1,s2})=0.

Таким образом, маркировка M({s1,s2})=0 является стабильным предикатом для данной сети. Тогда стабильное множество состоит из маркировок, которые не маркируют ни место s1, ни место s2. Такой предикат позволяет судить о живости сети: если существует достижимая маркировка M, которая не маркирует множество {s1,s2}, тогда ни переход t1 и ни переход t2 не могут сработать ни при какой маркировка из множества [M>. Это означает, что соответствующая ОСП не является живой. Предикат M({s1,s2})=0 стабилен, поскольку при срабатывании переходов t1 и t2 фишки удаляются из места s1 и места s2 соответственно и добавляются место s2 и место s1 соответственно. Это означает следующее: (s1,s2)(s1,s2). Непустые множества мест, удовлетворяющие такому свойству, называются  тупиками.

Определение 30   Пусть  N=(S,T,F)сеть. Тупиком  сети N называют множество мест  RS,  если  R  и  RR.

Иногда пустое множество будем назвать  квазитупиком.

Утверждение 6  Объединение тупиков сети N также является тупиком сети N.

Доказательство. Следует из определения 30. □

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

Утверждение 7   Пусть R — тупик. Тогда множество маркировок M, удовлетворяющих свойству  M(R)=0, стабильно.

Доказательство. Непосредственно следует из определения 30. □

Утверждение 8   Пусть M — мертвая маркировка сети N. Тогда множество R мест сети N, которое не маркируется M, — тупик.

Доказательство. Так как M — мертвая маркировка, то каждый переход сети имеет по крайней мере одно немаркированное входное место при M. Поэтому R содержит каждый переход сети. Следовательно, верно, что RR. Поскольку по определению, сеть включает по крайней мере один переход, то множество R не пусто. Тогда R — тупик. □

Следующее утверждение устанавливает связь между тупиками и поведением ОСП.

Утверждение 9   Каждый тупик живой ОСП изначально маркирован (т.е. маркируется начальной маркировке).

Доказательство. Пусть R — тупик и sR. Согласно утверждению 4, (живость влечет S-живость) место s и, следовательно, тупик R маркируются при некоторой маркировке M, достижимой из начальной маркировки. Предположив обратное, т.е. R не маркируется начальной маркировкой, в силу утверждения 7, придем к противоречию. □

Теперь введем понятия ловушки. Для этого сначала рассмотрим ОСП на рис. 2.23. Имеем следующее:

(M({s3,s4})>0M[t>L)L({s3,s4})>0.

Таким образом, предикат M({s3,s4})>0 стабилен, поскольку при срабатывании переходов t4 и t5 фишки удаляются из места s3 и места s4 соответственно и добавляюся к месту s4 или месту s3 соответственно. Это означает следующее: {s3,s4}{s3,s4}. Непустые множества мест, удовлетворяющие такому свойству, называются  ловушками.

Определение 31   Пусть  N=(S,T,F)сеть. Ловушкой сети N называется множество мест  QS,  если  Q  и  QQ.

Иногда пустое множество будем назвать  квазиловушкой.

Утверждение 10   Объединение ловушек сети N также является ловушкой сети N.

Доказательство. Следует из определения 31. □

Рассмотрим ряд интересных структурных свойств тупиков и ловушек.

Утверждение 11

а)   Каждый тупик сети N содержит уникальную максимальную ловушку (которая может быть квазиловушкой).

б)   Тупик сети N содержит маркированную ловушку, если и только если его максимальная ловушка маркирована.

Доказательство. Справедливость пунктов а) и б) следует из утверждений 6 и 10. □

Из определения ловушки Q имеем, что любой переход, входное место которого принадлежит Q, содержит в Q свое выходное место. Когда такой переход срабатывает, он забирает фишку из ловушки и тут же возвращает ее в ловушку, т.е. фишка, попав в ловушку не может покинуть ее. Следующее утверждение говорит о том, что если ловушка маркирована при некоторой маркировке M, то он остается маркированной при всех маркировках, достижимых из M.

Утверждение 12   Пусть Q — ловушка. Тогда множество маркировок M, удовлетворяющих свойству  M(Q)>0стабильно.

Доказательство. Непосредственно следует из определения 31. □

Для того чтобы тупик всегда был маркированным, достаточно обеспечить, чтобы он включал изначально маркированную ловушку — ловушку, маркированную при начальной маркировке, Поскольку, в силу утверждения 13, такая ловушка всегда остается маркированной и, следовательно, тупик тоже. Ниже приведено достаточное условие для M-живости.

Утверждение 13   Если каждый тупик сети N включает изначально маркированную ловушку, то  (N,M0)  M-жива.

Доказательство. Предположим обратное, т.е. некоторая достижимая маркировка является мертвой. Согласно утверждению 8, множество R мест, которое не маркируется M, — тупик. Поскольку R не маркируется M, он не содержит ловушек, маркированных при M. Так как маркированные ловушки остаются маркированными, R не содержит изначально маркированных ловушек. □

В дальнейшем нам понадобится понятие кластера.

Определение 32   Пусть x — узел сети. Тогда кластер для x, обозначаемый как  [x], — это минимальное множество узлов такое, что верно:

  • x[x];
  • если место s принадлежит  [x],  то множество s• включается в  [x];
  • если переход t принадлежит  [x],  то множество •t включается в  [x].

На рис. 2.24 показаны кластеры сети, изображенной на рис. 2.23.

Кластеры обладают следующим свойством.

Утверждение 14   Пусть N — сеть. Множество  {[x] ||xузел в N} — разбиение узлов в N.

Доказательство. Пусть N=(S,T,F). Из определения кластера [x] узла x следует, что

y[x](x,y)E,

где E=((F(S×T))(F(S×T))-1)*. Имеем, что E — рефлексивное, симметричное и транзитивное замыкание отношения F(S×T) и, значит, отношение эквивалентности. Результат следует из того факта, что класс эквивалентности узла x — это [x].   □