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

Напомним, что сеть Петри — это кортеж N=(S,T,F,W,M0). Далее, в СП N маркировка — это мультимножество над S и шаг — это непустое конечное мультимножество над T. Пусть M(N) обозначает множество всех маркировок, а Y(N) — множество шагов СП N. Шаг Y может сработать при маркировке M, если

sS ◊ tYF(s,t)M(s).

Срабатывание шага Y   при маркировке M  порождает маркировку M'  следующим образом:

sS ◊ M'(s)=M(s)-tYF(s,t)+tYF(t,s).

Введем понятие СП, эквивалентной РСП.

Определение 52  Пусть CN =(S,T,F,Σ,C,G,E,I) — РСП. Тогда СП N =(S*,T*,F*,W*,M0*)  называется  эквивалентной CN, если

(а)  S*=TE;

(б)  T*=BE;

(в)  F*=((s,c),(t,b))(S*×T*)|ϵ(t,s)b(c)0((t,b),(s,c))(T*×S*)|ϵ(t,s)b(c)0;

(г)  ((s,c),(t,b))F*(S*×T*) ◊ W*((s,c),(t,b))=(ϵ(t,s)b(c)),

      ((t,b),(s,c))F*(T*×S*) ◊ W*((t,b),(s,c))=(ϵ(s,t)b(c));

(д)  (s,c)S* M0*(s,c)=(I(s))(c).

Дадим некоторые пояснения.

(а) В СП имеется место для каждой элемента-фишки РСП. Это означает, что каждое место p  в РСП разбивается на столько мест в СП, сколько цветов в C(p). Поэтому и после такого преобразования можно различать фишки, которые имеют разные цвета, Таким образом, фишки утрачивают свой цвет, но они размещаются в разных местах.

(б) В СП имеется место для каждого элемента-связывания РСП. Это означает, что каждый переход t  в РСП делится на столько переходов в СП, сколько связываний в B(t). Напомним, что все элементы в B(t)  удовлетворяют предохранителю G(t).

(в) В СП имеется дуга из места (s,c) в переход (t,b), если и только если верно, что (E(s,t)b(c)0), т.е. если и только если срабатывание перехода t со связыванием b удаляет по крайней мере одну c-фишку из места s. Аналогично, имеется дуга из перехода (t,b) в место (s,c), если и только если верно, что (E(t,s)b(c)0), т.е. если и только если срабатывание перехода t со связыванием b добавляет по крайней мере одну c-фишку в место s.

(г) В СП кратность E*((s,c),(t,b)) дуги из места (s,c) в переход (t,b) определяется как E(s,t)b)(c), т.е. числом c-фишек, которые удаляются из места s при срабатывании перехода t со связыванием b. Аналогично, в СП кратность E*((t,b),(s,c)) дуги из перехода (t,b) в место (s,c) определяется как E(t,s)b)(c), т.е. числом c-фишек, которые добавляются в место s при срабатывании перехода t со связыванием b.

(д) В СП начальная маркировка места (s,c) определяется как (I(s))(c), т.е. числом c-фишек в I(p).

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

Теорема 34  Пусть CN  РСП и N  эквивалентная СП. Тогда:

(а)   M(CN) = M(N), M0=M0*;

(б)Y(CN) = Y(N);

(в)  M1,M2M(CN),YY(CN) M1[YCNM2M1[YNM2.

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

(а) Согласно определениям понятий маркировок СП и РСП, имеем, что M(CN)=TEMS и M(N)==SMS*. В силу определения 52(а), верно S* = TE. Тогда получили, что M(CN) = M(N), M0=M0*.

Теперь покажем, что M0=M0*. Из определения начальной маркировки РСП следует, что

(s,c)TE ◊ M0(s,c)=(I(s))(c).

Согласно определению начальной маркировки СП, имеем, что

s*S* ◊ M0*(s*)=I*(s*).

Это, в силу определения 52(а), эквивалентно

s*TE* ◊ M0*(s,c)=I*(s,c).

По определению 52(д), верно

(s,c)TE ◊ M0(s,c)=(I(s))(c).

(б) Из определений понятий шагов СП И РСП имеем, что Y(CN) состоит из всех непустых и конечных мультимножеств из BEMS, а Y(N) — из всех непустых и конечных мультимножеств из TMS*. В силу определения 52(б), верно, что T*=BE. Тогда получили, что Y(CN) = Y(N).

(в) Сначала покажем следующее: M1[YCNM1[YN.

Из определения условия готовности к срабатыванию шага в РСП имеем M1[YCN, если и только если верно

sS   (t,b)YE(s,t)bM1(s).

Далее, из определения условия готовности к срабатыванию шага в СП имеем M1[YCN, если и только если верно

s*S*  t*YE*(s*,t*)bM1(s*).

Это, в силу определения 52(а) и 52(б), эквивалентно

(s,c)TE ◊ (t,b)YE*((s,c),(t,b))M1(s,c).

Согласно определению 52(в) и 52(г) и расширению E*  из A*  к S*×T*T*×S*, имеем

(s,c)TE ◊  (t,b)Y(E*(s,t)b)(c)M1(s,c).

Это эквивалентно

sScC(s)TE   (t,bY)(E*(s,t)b)(c)(M1(s))(c).

Тогда верно

 sS   (t,b)YE(s,t)bM1(s).

Рассуждая аналогичным способом, получим, что M1,M2M(CN),YY(CN)   M1[YCNM2M1[YNM2.

Также можно идти в обратном направлении, т.е. конструировать для произвольной СП эквивалентную РСП. При этом следует выполнить следующие действия:

  • сохранить сетевую структуру (т.е. места, переходы и дуги);
  • каждому месту s  сопоставить множество цветов E(s) = {e};
  • каждому переходу сопоставить замкнутое выражение true  как выражение перехода;
  • каждой дуге a  сопоставить E(a)'e  как выражение дуги;
  • каждому месту s  сопоставить I(s)'e  как инициализацию места.

Можно конструировать РСП произвольным образом. Произвольному множеству мест СП может быть сопоставлено одно место конструируемой РСП. При этом вводится цвет для каждого места СП, и таким образом можно различать фишки, хотя все они будут располагаться в одном месте. Аналогично, произвольному множеству переходов СП может быть сопоставлен один переход конструируемой РСП. При этом используется переменная типа, которая имеет элемент для каждого перехода СП. Получаем таким образом элемент-связывание, т.е. возможность сработать для каждого перехода. Рассмотрим формальное определение такого конструирования. Под разбиением некоторого множества будем понимать деление этого множества на компоненты — непустые попарно различные подмножества, объединение которых дает исходное множество. Разбиение называется конечным, если оно состоит из конечного числа компонент. В приведенном ниже определении запись (vt*:t*) означает, что выражения E*(s*,t*) и E*(t*,s*) включают переменную vt* типа t*. Легко показать, что сконструированный ниже кортеж удовлетворяет свойствам определения 51.

Определение 53  Пусть  N=(S,T,A,W,M0) — СП и SS, TT  два конечных разбиения множеств S и T соответственно. Тогда CN = (Σ*,S*,T*,A*,N*,C*,G*,E*,I*)  называется эквивалентной РСП относительно этих разбиений, если

(a)  Σ*=SSTT;

(б)  S* = SS,

(в)  T* = TT,

(г) A*  = { (s*,t*)(S*×T*)|&exists;ss*&exists;tt* ◊ (s,t)F } {(t*,s*)(T*×S*)|&exists;ss*&exists;tt* (t,s)F};

(д)  a*=(x1,x2)A* N*(x1,x2)=(x1,x2);

(е)s*S* C*(s*)=p*;

(з) t*T* ◊  G*(t*)=true;

(ж)  (s*,t*)A*(S*×T*)   E*(s*,t*)=ss*W(p,(vt*:t*))'p,
 (t*,s*)A*(T*×S*) ◊  E*(t*,s*)=ss*W((vt*:t*),p)'p;

(и)  s*S* ◊  I*(s*)=ss*M0(s)'s.

Дадим некоторые пояснения.

(а)  Для каждой компоненты c  множеств SS  и TT  определяется множество цветов, которое также обозначается как c. Множество цветов c  имеет цвет для каждого элемента в компоненте c. Множество цветов не имеет неявно определенных операций и функций.

(б)  В РСП строится место для каждой компоненты из SS. Это означает, что всем местам из SS  сопоставляется одно место в РСП.

(в)  В РСП строится переход для каждой компоненты из TT. Это означает, что всем переходам из TT  сопоставляется один переход в РСП.

(г)  В РСП строится дуга из места s* в переход t*, если и только если одно из мест СП, которому соответствует s*, имело дугу в один из переходов СП, которому соответствует t*. Такую дугу обозначим как (p*,t*). Она уникальна, что следует из конструирования A*. Аналогично, в РСП строится дуга из перехода t* в место p*, если и только если один из переходов СП, которому соответствует t*, имело дугу в одно из мест СП, которому соответствует s*. Такую дугу обозначим как (t*,p*).

(д)  Функция вершин отображает каждую дугу (x1,x2)A* в (x1,x2), где x1 — начало, а x2 — конец дуги.

(е)  Каждому месту s* сопоставляется множество цветов s*, которое соответствует SS-компоненте, из которой s* конструируется. Это означает, что в РСП существует столько различных цветов для s*, сколько элементов в SS-компоненте s*, т.е. цвет для каждого места в СП был отображен в s*. Неформально говоря, цвета позволяют различать фишки, хотя они и находятся в одном месте.

(ж)  Функция выражений переходов сопоставляет замкнутые выражения true.

(з) В РСП каждая дуга из места s* в переход t* имеет выражение с одной переменной vt* типа t*. Это означает, что в РСП существует столько различных связываний для t*, сколько элементов в TT-компоненте t*, т.е. связывание для каждого перехода в СП было отображено в t*. Означивание выражения E*(s*,t*) для связывания vt*=t дает в РСП фишку цвета t* для каждой фишки, которую переход t  в СП удаляет из места s. Неформально говоря, срабатывание в РСП перехода t* со связыванием vt*=t удаляет те же самые фишки из места s*, что и срабатывание в СП перехода t из всех мест SS-компоненты s*. Однако в РСП все эти фишки находятся в одном месте s* и каждая из них несет информацию о месте в СП, которому соответствует эта фишка. Дуги из переходов в места определяются аналогично.

(и) Место s* в РСП изначально содержит фишку цвета s  для каждой фишки изначально маркированного места s  в СП. Это означает, что все фишки в местах SS-компоненты s* собираются в РСП в месте s* и содержат информацию о том, из какого места фишка пришла.

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

Теорема 35  Пусть N — СП и CN* — эквивалентная РСП относительно произвольных двух конечных разбиений. Тогда

(а)   M(N) = M(CN), M0=M0*;

(б) Y(N) = Y(CN);

(в)  M1,M2M(N),YY(N) ◊  M1[YNM2M1[YCNM2.

Доказательство. Аналогично доказательству теоремы 34.