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

Структурная эквивалентность

Структура ЭСС представляется ее базовой сетью. Таким образом, структурная эквивалентность ЭСС основывается на стандартном понятии изоморфизма двудольных графов.

Определение 12  Пусть  N1=(B1,E1,F1,C1)  и  N2=(B2,E2,F2,C2)ЭСС. Будем говорить, что  N1  и  N2 структурно эквивалентны (обозначается  N1N2), если и только если существует биекция  α:XN1XN2  такая, что:

  • x,yXN1    xB1α(x)B2;
  • (x,y)F1(α(x),α(y))F2;
  • α(C1)=C2.

Рассмотрим в качестве примера две ЭСС, изображенные на рис. 2.2,а и рис. 2.2,б. Легко видеть, что независимо от начальных состояний этих сетей структурная эквивалентность между ними не имеет места. Итак, структурная эквивалентность, можно сказать, является в некотором смысле слишком сильной эквивалентностью.

Эквивалентность по пространству состояний

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

Пусть Σ — алфавит. Тогда тройка G=(V,Y,vin)граф с Σ-помеченными дугами, если V — множество вершин, YV×Σ×V — множество Σ-помеченных дуг и vin — начальная вершина. Определим множество rlab(G)={σΣ|(v,σ,v')Y}. Далее, пусть Σ1,Σ2 — алфавиты. Тогда G1=(V1,Y1,v1) — граф с Σ1-помеченными дугами и G2=(V2,Y2,v2) — граф с Σ2-помеченными дугами. Будем говорить, что G1 и G2  изоморфны  (обозначается G1lisom¯G2), если существуют биекции α:V1V2 и β:rlab(G1)rlab(G2) такие, что

  • α(v1)=v2;
  • v,v'V1σrlab(G1)     [(v,σ,v')Y1(α(v),β(σ),α(v'))Y2].

Теперь рассмотрим понятие графа состояний ЭСС N.

Определение 13   Пусть  N=(B,E,F,cin)ЭСС. Графом состояний ЭСС  N (обозначается  CGN) называется граф  (V,Y,vin) с UN-помеченными дугами такой, что  V=CN,Y={(c1,u,c2)|c1[u>c2}  и  vin=cin.

Рассмотрим в качестве примера ЭСС вместе с ее графом состояний, изображенные на рис. 2.3.

Таким образом, CGN представляет пошаговое поведение ЭСС N. Одним из наиболее известных свойств графа CGN является следующая

Теорема 2  Пусть  NЭСС и  CGN=(V,Y,vin). Далее, пусть  u1  и  u2два непустых и непересекающихся подмножества множества  EN. Тогда:

  • если  v1, v2, v3, v4различные вершины из  V  такие, что  (v1,u1,v2), (v2,u2,v4), (v1,u2,v3)Y, то  (v3,u1,v4), (v1,u1u2,v4)Y;
  • если  v1  и  v4вершины из  V  такие, что  (v1,u1u2,v4)Y, то существуют вершины  v2  и  v3такие, что  (v1,u1,v2), (v2,u2,v4), (v1,u2,v3), (v3,u1,v4)Y.

Графически эта теорема может быть проиллюстрирована на рис. 2.4.

Следовательно, данная теорема сводится к так называемому свойству "ромба".

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

Определение 14   Пусть N = (B, E, F,  cin)  — ЭСС. Последовательным графом состояний ЭСС N  (обозначается  SCGN) называется граф (V , Y ,vin)  с  UN-помеченными дугами такой, что  V=CN, Y={(c1,u,c2)|c1[u>c2|u|=1и  vin=cin.

Последовательный граф состояний ЭСС, показанной на рис. 2.3, изображен на рис. 2.5.

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

Построение 1.  Пусть N=(B,E,F,cin) — ЭСС и CGN=(V,Y,vin). Граф G'=(V',Y',vin') получен из CGN посредством удаления из Y всех дуг (c1,u1,c2) таких, что |u1|>1.

Очевидна следующая

Лемма 6  G'=SCGN.

Теперь рассмотрим построение в другую сторону, т.е. графа CGN из графа SCGN.

Построение 2.  Пусть N=(B,E,F,cin) — ЭСС и SCGN=(V,Y,vin).

  1. Положим i=0 и G0=(V0,Y0,v0)=(V,Y,vin).
  2. Если существуют дуги (c1,u1,c2),(c2,u2,c4) и (c1,u2,c3) в Gi такие, что дуга (c1,u1u2,c4) еще не принадлежит Gi, то переходим к шагу 3, иначе переходим к шагу 6.
  3. Пусть (c1,u1,c2),(c2,u2,c4) и (c1,u2,c3) три дуги, удовлетворяющие условию шага 2. Положим, что граф Gi+1 является результатом добавления к графу Gi дуги (c1,u1u2,c4).
  4. i:=i+1.
  5. Переходим к шагу 2.
  6. Положим G'=Gi.

В силу теоремы 2, очевидна следующая

Лемма 7  G'=CGN.

Теперь определим эквивалентности двух ЭСС по их пространствам состояний и по их последовательным пространствам состояний.

Определение 15  Пусть  N1  и  N2ЭСС. Тогда:

  • N1  и  N2 эквивалентны по пространству состояний (обозначается  N1N2), если  CGN1lisom¯CGN2;
  • N1  и  N2 эквивалентны по последовательному пространству состояний (обозначается  N1N2), если  SCGN1lisom¯SCGN2.

Оказывается, эквивалентность по пространству состояний и эквивалентность по последовательному пространству состояний различают те же самые пары ЭСС.

Теорема 3  Пусть  N1  и  N2ЭСС. Тогда

N1N2N1N2.

Доказательство того, что из N1N2 следует N1N2, вытекает непосредственно из леммы 7. И тогда доказательство в обратную сторону очевидно.   □

Симуляционная эквивалентность

Теперь перейдем к еще одному способу сравнения двух ЭСС, называемому отношением взаимной симуляции. Для этих целей необходимо рассмотреть так называемые активные события двух систем.

Пусть N=(B,E,F,cin) — ЭСС. Множество всех активных событий ЭСС N (обозначается ev¯(N)) определяется следующим образом: ev¯(N)=uUN{e|eu}.

Определение 16  Пусть  N1=(B1,E1,F1,c1)  и  N2=(B2,E2,F2,c2)ЭСС. Тогда  N1  и  N2 симуляционно эквивалентны (обозначается  N1N2),  если существуют биекции  α:CN1CN2  и  β:ev¯(N1)ev¯(N2)  такие, что  α(c1)=c2  и  c,c'CN1u(2E1\)    [c[u>c'  в  N1α(c)[β(u)>α(c')  в  N2] .

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

Определение 17  Пусть  N1=(B1,E1,F1,c1)  и  N2=(B2,E2,F2,c2)ЭСС. Тогда  N1  и  N2 последовательно симуляционно эквивалентны (обозначается  N1N2), если существуют биекции  α:CN1CN2  и  β:ev¯(N1)ev¯(N2)  такие, что  α(c1)=c2  и  c,c'CN1eE1    [c[e>c'  в  N1α(c)[β(e)>α(c')  в  N2].

Оказалось, что симуляция и последовательная симуляция как меры эквивалентности приводят к одному и тому же результату.

Теорема 4  Пусть  N1  и  N2ЭСС. Тогда

N1N2N1~N2.

Очевидно, что последовательная симуляционная эквивалентность и эквивалентность на последовательных состояниях совпадают.

Теорема 5  Пусть  N1  и  N2ЭСС. Тогда

N1~N2N1N2.

Суммируя все результаты этого пункта относительно различных эквивалентностных понятих ЭСС, получим следующее

Следствие 1  Пусть  N1  и  N2ЭСС. Тогда

N1N2N1~N2N1N2N1N2.

Отметим, что ЭСС N1 и N2 эквивалентны (обозначается N1˜N2), если и только если имеет место хотя бы одно (и, следовательно, все) из указанных выше соотношений. Полезно заметить, что структурная эквивалентность двух ЭСС влечет все другие их эквивалентности, но обратное не всегда имеет место.