Warning: session_start(): open(C:\Windows\temp\sess_er0o6rongv3chj85vdhemad1n4, 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_er0o6rongv3chj85vdhemad1n4, 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 Сети Петри: модификации и расширения

Определение дискретно-временной СП

Рассмотрим ряд понятий, связанных со структурой и поведением дискретно-временной СП (ДВСП). Под ДВСП понимается СП, где с каждым переходом связана целочисленная временная длительность его срабатывания.

Напомним, что N — множество натуральных чисел и N+ — множество положительных натуральных чисел.

Определение 40   Дискретно-временная СП (ДВСП) — это кортеж  DTN=(S,T,F,W,M0,D),  где  N=(S,T,F,W,M0) — СП и  D:TN+ — временная функция, сопоставляющая каждому переходу натуральное число, соответствующее временной длительности его срабатывания.

Неформально говоря, для каждого перехода t значение D(t) определяет длительность срабатывания t, т.е если t срабатывает в момент времени x, то фишки из входных мест перехода t "уходят" в момент времени x и появляются в выходных местах перехода t в момент времени x + D(t).

Для этой модели характерен принцип раннего срабатывания переходов, т.е. если переходы могут сработать при заданной маркировке, то они должны сработать при этой маркировке, если только им не помешают конфликтные с ними переходы (т.е. переходы, имеющие общие входные места с рассматриваемыми переходами). Таким образом, предполагается правило максимального шага срабатывания, т.е. в любой момент времени срабатывает максимальное множество готовых к срабатыванию переходов (максимальный шаг). При этом считается, что никакой переход не может срабатывать параллельно с самим собой. Также запрещается, чтобы переход начинал второе свое срабатывание, не закончив первое. Например, если на рис. 3.1 в момент времени x две фишки появятся в месте s, то одна из них должна уйти в момент времени x, а другая — в момент x + D(t) = x + 2, как результат двух последовательных срабатываний перехода t1.

Определение 41   Состоянием в ДВСП называется пара  q=(M,A)где M  маркировка базовой сети и  A:TN — функция, сопоставляющая каждому переходу натуральное число, соответствующее текущей временной длительности срабатывания перехода. Начальное состояние в DTN  это пара  q0=(M0,0).

Неформально говоря, для состояния q=(M,A) запись A(t)>0 показывает количество временнных тактов с начала срабатывания перехода t. Запись A(t)=0 говорит о том, что переход t не срабатывает в состоянии q.

Определение 42    Пусть  DTN=(S,T,F,W,M0,D) —  ДВСП и  q=(M,A) — состояние в DTN.

  • UT — шаг в состоянии  q (множество готовых к срабатыванию в состоянии q переходов), если
    • tU    A(t)=0;
    • U=A0;
    • F(U)=tUF(t)M.
  • максимальный шаг в состоянии q, если U  шаг в q и не существует шага  U'  в q, строго содержащего U. Множество всех максимальных шагов в состоянии q обозначается как  MS(q).

Рассмотрим правило срабатывания (максимального) шага.

Определение 43    Пусть  q=(M,A) — состояние в DTN и U  (максимальный) шаг в q. Срабатывание  U в состоянии q в момент времени x приводит к состоянию  q'=(M',A')  в момент x  + 1 (обозначается  q[U>q'), где   

  • M'=M-F(U)+tUD(t)=1F(t)+tT\U0<A(t)=D(t)-1F(t) и
  • tT A'(t)=1,tUD(t)>1;A(t)+1,tT\U0<A(t)<D(t)-1;0,иначе.

Достижимость состояний посредством срабатывания максимальных шагов определяется обычным образом. Через [q0> обозначим множество всех состояний, достижимых в DTN, а через [q> — множество всех состояний, достижимых из состояния q в DTN. На рис. 3.2 представлена ДВСП и ее граф достижимых состояний. Здесь каждому состоянию (M,A) сопоставлена запись M;x,y, где M — маркировка, x=A(t1) и y=A(t2).

Лемма 14 Пусть  q=(M,A) — достижимое состояние в DTN. Тогда  M*=M+A(t)>0F — достижимая маркировка в N, т.е. M*[M0>.

Доказательство. Следует из определений правил срабатывания перехода в СП и (максимального) шага в ДВСП.     □

Замечание 1.

  • Для каждого состояния q=(M,A) из [q0> и каждого перехода  t  из  T  верно, что A(t)<D(t).
  • Если D1, то для каждого достижимого состояния q=(M,A) имеем A0, т.е. каждое достижимое состояние может быть отождествлено с его маркировкой.
  • Каждая ДВСП DTN=(S,T,F,W,M0,D), у которой D1, может быть отождествлена с СП N=(S,T,F,W,M0), переходы которой срабатывают по правилу срабатывания максимального шага (и наоборот).

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

Будем говорить, что ДВСП  DTN k-ограничена (ограничена), если существует натуральное число k такое, что для любого достижимого состояния q=(M,A) и для любого места s верно, что M(s)k; ДВСП  DTN жива, если для каждого перехода tT и каждого состояния q=(M,A)[q0> существует состояние q'=(M',A')[q> такое, что F(t)M'.

Эквивалентность ДВСП

Введем понятие эквивалентности двух ДВСП.

Определение 44  Две ДВСП называются  эквивалентными,  если для их графов достижимых состояний существует взаимно-однозначное соответствие между множествами вершин и множествами дуг с сохранением отношения инцидентности, начальных вершин и пометки дуг (при этом пометка дуг вспомогательными переходами  tˆ  и  t¯  для каждого  tT  (см. далее) не учитывается).

Теорема 27  Для каждой ДВСП с произвольной временной функцией можно построить эквивалентную ей ДВСП с единичной временной функцией.

Доказательство. Рассмотрим алгоритм построения по ДВСП с произвольной функцией D, DTN=(S,T,F,W,M0,D), эквивалентной ей ДВСП DTN'=(S',T',F',W',M0',D') с единичной функцией D'.

Для каждого перехода tT выполним следующие действия.

Если D(t)=1, то никаких действий не производится.

Если D(t)>1, то S'=StT{rt,at,ct}, T'=TtT{tˆ,t¯}. Причем если D(t)=2, то место ct и переход tˆ не вводятся. Отношение инцидентности F' и функция кратности дуг W' формируются на основе F и W соответственно с добавлением дуг, как показано здесь, где целочисленное значение около черты, перечеркивающей дугу, указывают на кратность данной дуги.

Маркировка M0' определяется следующим образом:

M0'(s)=M0(s),sSS',1,s=rt,tT,0,иначе.

Переход tT' моделирует начало срабатывания, а переход t¯T' — конец срабатывания перехода tT. Каждое срабатывание перехода tˆ моделирует тиканье часов системы. Место rt, которое изначально содержит одну фишку, запрещает повторное срабатывание перехода t в новой ДВСП до тех пор, пока предыдущее срабатывание этого перехода в исходной ДВСП не будет завершено. Число фишек в месте at — это значение A(t) в соответствующем состоянии исходной ДВСП.

Вместо формального доказательства того, что построенная ДВСП DTN' эквивалентна исходной ДВСП DTN, рассмотрим рис. 3.3, где показан результат применения данного построения к ДВСП, изображенной на рис. 3.2., и граф состояний DTN'.

Сравним графы достижимости на рис. 3.2 и рис. 3.3. Метки дуг обоих графов — множества переходов. Метка дуги графа на рис. 3.2 получается из метки соответствующей дуги графа на рис. 3.3 уничтожением всех переходов с крышкой и чертой. Чтобы получить метку дуги графа на рис. 3.3 из метки соответствующей дуги на рис. 3.2, необходимо добавить определенные вспомогательные переходы в зависимости от вершины, из которой выходит дуга.

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

Сохранение свойства живости при переходе от СП к ДВСП

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

СП N=(S,T,F,W,M0) называется свободной от параллелизма, если для всех маркировок M[M0> и двух различных переходов t, t,t' выполнено условие:

F(t)MF(t')MF(t)+F(t')>M.

Теорема 28  Пусть  N=(S,T,F,W,M0) — живая и свободная от параллелизма СП. Тогда  DTN=(S,T,F,W,M0,D) — живая ДВСП для любой временной функции  D:TN+.

Доказательство. Пусть q=(M,A) — достижимое состояние в DTN. Сначала покажем справедливость некоторых вспомогательных фактов.

Предложение А. UMS(q)|U|1.

Доказательство. Пусть t1,t2UMS(q) и t1t2. Тогда, по определению шага, имеем, что F(t1)+F(t2)M. В силу леммы 14, верно, что F(t1)+F(t2)M*[M0>. Это противоречит тому, что N свободна от параллелизма. Следовательно, верно, что |U|1.        □

Предложение Б. Для каждого q=(M,A)[M0> верно, что если A0, то MS(q)={}.

Доказательство. Предположим обратное, т.е. существует последовательность

q0[U0>q1[U1>q2...qk[Uk>qk+1

такая, что [Ai0Ui=(i=0,1,...,k-1)] и [Ak0 Uk}.

Возьмем j=max{i|1ik-1Ai0Ui&neq;}. Такое число существует, поскольку Ak0. В силу предложения А, можем предположить, что Uj={t1} и Uk={t2}. Тогда верно

(Mj,Aj)[{t1}>(Mj+1,Aj+1)[>...(Mk,Ak)[{t2}>qk+1.

По определению шага и правилу срабатывания шага, имеем следующее:

F(t1)Mj

Aj+1(t1)>0, ..., Ak(t1)>0 и

Тогда верно, что F(t1)+F(t2)Mj. В силу леммы 14, справедливо, что F(t1)+F(t2)Mj*[M0>. Это противоречит тому, что N свободна от параллелизма. □

Предложение В. M'[M>(M',0)[(M,0)>.

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

Далее, пусть tT и q=(M,A)[q0>. Если A0, то некоторое состояние q''=(M'',0) может быть достигнуто из q в DTN. Тогда имеем, что M''[M0>. Так как N жива, то существует маркировка M'[M''> такая, что F(t)M'. Используя предложение В получаем, что (M',0)[(M,0)>. Тогда верно, что (M',0)[q>. Очевидно, что {t} — максимальный шаг в (M',0). □

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

Теорема 29  Пусть  N=(S,T,F,W,M0) — живая СП, для которой выполнены следующие условия:

а)  sS    s,

б)  sSt,t's    W(s,t)=W(s,t'),

в)  s,s'S    ss'ss's's.

Тогда  DTN=(S,T,F,W,M0,D) — живая ДВСП для любой  D:TN+.

Доказательство. Предположим, что DTN не жива. Для всех состояний q[q0> определим множество

DEAD(q)={t|q'=(M',A') [q>    ¬(F(t)M')},

т.е. DEAD(q) — множество переходов t, которые мертвы в q. Более того, пусть

MAX:={q[q0>|q'[q>    DEAD(q)=DEAD(q')}.

Предложение А. q'[q>DEAD(q)DEAD(q')T.

Доказательство. Очевидно. □

Поэтому множество MAX не пусто. Поскольку DTN не жива, существует состояние q[q0> такое, что DEAD(q). Пусть q=(M,A)MAX такое, что DEAD(q).

Предложение Б. tDEAD(q)t жив в состоянии q.

Доказательство. Очевидно. □

Пусть tDEAD(q). Тогда t. В силу условия в), можем предположить, что t={s1 , ..., sn}, где n>0 и s1s2 ... sn.

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

Предложение В. Для всех q'=(M',A')[q> (1in и M'(sj)W(sj,t),M'(si)<W(si,t)) верно, что siDEAD(q)=DEAD(q').

Доказательство. Пусть t*sisi+1 ... sn. Следовательно, имеем, что si, ..., snt*. Предположим обратное, т.е. t* не мертв в q'. Тогда из состояния q' достижимо состояние q''=(M'',A'') такое, что si, ..., sn достаточно маркированы, т.е. M''(si)W(si,t), ..., M''(sn)W(sn,t). Пусть U1, ..., Uk — кратчайшая последовательность максимальных шагов, ведущая из состояния q' в состояние q'', где si, ..., sn достаточно маркированы. Если фишка удаляется из одного из мест s1, ..., si-1, скажем sr, при срабатывании перехода t**Uj (1jk), то t**srsi ... sn, т.е. последовательность U1, ..., Uj-1 ведет в состояние, где si, ..., sn достаточно маркированы, что противоречит минимальности k. Так как фишки не могут быть удалены из мест s1, ..., si-1, то в состоянии q'' места s1, ..., sn достаточно маркированы, что противоречит тому, что t мертв в q. Следовательно, t* мертв в q', т.е. siDEAD(q)=DEAD(q'). □

Далее, покажем справедливость следующего предложения.

Предложение Г. Каждый переход tDEAD(q) имеет входное место s такое, что для всех состояний q'=(M',A')[q> справедливо, что M'(s)<W(s,t).

Доказательство. Будем доказывать от противного. Допустим, что tDEAD(q) такой, что для каждого его входного места si существует достижимое из q состояние qi=(Mi,Ai), где Mi(si)W(si,t).

Покажем индукцией по j(1jn), что существует состояние zj[q>, при котором места s1, ..., sj достаточно маркированы.

j = 1. Тривиально.

j > 1. Пусть zj=(Mj*,Aj*). Если Mj*(sj+1)W(sj+1,t), то положим zj+1=zj. Пусть Mj*(sj+1)<W(sj+1,t). Тогда, в силу предложения В, верно, что s1s2 ... sj+1DEAD(q)=DEAD(zj). По предположению индукции, в состоянии q место sj+1 может быть достаточно маркировано, поэтому у места sj+1 существует входной переход, который жив в состоянии q, а значит, и в состоянии zj (поскольку qMAX). Следовательно, из состояния zj можно достичь состояние zj+1 такого, что Mj*(sj+1)W(sj+1,t). Так как верно, что s1s2 ... sj+1DEAD(q)=DEAD(zj) имеем Mj+1*(si)Mj*(si)W(si,t) для i=1,...,j.

Показали, что zn достижимо из q и в zn переход t может сработать, что противоречит тому, что t мертв в q, что доказывает справедливость предложения Г. □

Далее, пусть S0={s|q'=(M',A')[q>    M'(s)<W(s,t)} — множество всех мест, которые есть и остаются недостаточно маркированными в q. Очевидно, что множество S0 непусто и в силу предложения Г имеем следующее:

Предложение Д. DEAD(q)S0.

Далее, в случае, когда sS0, ts и q'=(M',A')[q>, имеем M'(s)<W(s,t)=F(s,t). Следовательно, tDEAD(q), что означает справедливость следующего предложения.

Предложение Е. DEAD(q)=S0.

Пусть tS0. Тогда t мертв в q, поскольку в противном случае t был бы жив и место s могло бы быть достаточно маркированным. Получили, что S0DEAD(q)S0, т.е. S0 — тупик в (S,T,F).

Рассмотрим маркировку M*=M+A(t)>0F(t), которая достижима из M0, в силу леммы 14. Имеем, что M*(s)<W(s,t) для всех sS0, поскольку в противном случае из q могло быть достижимо состояние, в котором по крайней мере одно место s из S0 содержит по крайней мере W(s,t) фишек. При маркировке M* в N все переходы tS0 мертвы, и это множество непусто, поскольку множество S0 непусто, что противоречит живости N.         □

Показанная на рис. 3.4 СП является живой. Однако она не свободна от параллелизма, а также для нее не выполнено условие в) теоремы 29 для мест s2 и s4. ДВСП, изображенная на рис. 3.4, не жива при показанной временной функции.

На рис. 3.5 показано, что в обратном направлении теорема 29 не верна, поскольку изображенная ДВСП обладает свойствами а)-в), и является живой при любой временной функции. В начальном состоянии возможен максимальный шаг U1={t1,t2}. В случае, когда d1=d2, после истечения времени d1 вновь возвращаемся в начальное состояние. Положим d1=D(t1)<d2=D(t2). Тогда фишка в месте s2 появится первой, но ничего не может произойти, пока t2 не закончит срабатывание, порождающее начальное состояние. Теперь пусть d2d1. Тогда две фишки в месте s1 появятся первыми и ничего не сможет произойти, пока t1 не закончит срабатывание, поскольку t1 не может срабатывать одновременно с самим собой. Получаем, что ДВСП жива, но в базовой СП возможна тупиковая маркировка после двух последовательных срабатываний перехода t1.