2.2.4 Определение подклассов ОСП

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

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

  • N — S-сеть,  если  |t|=|t|=1  для всех  tT;
  • N — T-сеть,  если  |s|=|s|=1  для всех  sS;
  • N — X-сеть,  если N — S- и T-сеть;
  • N — FC-сеть,  если верно: (s,t)Ft×sF.

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

Теорема 17 а)   каждая S-сеть является FC-сетью;

б)  каждая T-сеть является FC-сетью;

в)   двойник S-сети является T-сетью;

г)   двойник T-сети является S-сетью;

д)  двойник X-сети является X-сетью;

е)   двойник FC-сети является FC-сетью.

На рис. 2.25 приведены примеры сетей из рассмотренных подклассов: NSS-сеть, но не T-сеть; NTT-сеть, но не S-сеть; NFCFC-сеть, но не является ни S-, ни T-сетью; N — не FC-сеть. Эти примеры дополнителько к предыдущей теореме позволяют установить факты, изображенные на рис. 2.26.

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

Определение 34   Пусть  N=(N,M0)ОСП. Тогда N называется S-СП  (T-СП, X-СП, FC-СП соответственно), если N — S-сеть (T-сеть, X-сеть, FC-сеть соответственно).

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

Определение 35   Пусть  N=(S,T,F,M0)безопасная ОСП, M[M0>  и  t1,t2T.

  • t1  и  t2 конфликтны при маркировке  M,  если  t1t2(M[t1>M[t2>t1t2);
  • t1  и  t2 могут сработать параллельно  при маркировке M (обозначается  M[{t,t'}>), если  M[t1>M[t2>(t1t2t1t2=);
  • пусть  tT  такой, что  M[t>;

конфликтное множество  перехода t при маркировке M (обозначается  cfl(t,M)) определяется как  {t'T|M[t'>¬(M[{t,t'}>)};

  • пусть  t1  и  t2  могут сработать параллельно при маркировке M;

тройка  (M,t1,t2)конфузия при маркировке M, если верно, что  cfl(t1,M)cfl(t2,M2)где  [t2>

Будем говорить, что N находится  в конфузии  при M, если существует конфузия при M.

Используя эти понятия, рассмотрим некоторые подклассы безопасных ОСП.

Определение 36  Пусть  N=(S,T,F,M0)безопасная ОСП. Тогда:

  • N — последовательная,  если  M[M0>t1,t2T ◊ (M[t1>M[t2>t1t2);
  • N — детерминированная, если  M[M0>t1,t2T ◊ (M[t1>M[t2>M[{t,t'}>));
  • N — свободная от конфузий,  если N не находится в конфузии ни при какой M из  [M0>.

Взаимосвязи между структурными и поведенческими ограничениями устанавливает следующая

Теорема 18   Пусть  N=(N,M0)безопасная ОСП. Тогда:

а)   если N — S-СП, то N — последовательная;

б)   если N — T-СП, то N — детерминированная;

в)   если N — X-СП, то N — последовательная и детерминированная;

г)   если N — FC-СП, то N — свободная от конфузий.

Как показывают контрпримеры на рис. 2.17,а, рис. 2.17,б, рис. 2.17,в, рис. 2.17,г, данная теорема неверна в обратную сторону.