Стр. 37 - Параллельное программирование

ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ
35
Простые сети Петри
Сеть Петри из трех элементов: множество мест , множество переходов
и отношение инцидентности .
Определение: Простая сеть Петри. Простой сетью Петри называется набор
, где - множество мест; - множество переходов
таких, что ∅; - отношение инцидентности такое, что
• ;
• .
Условия последнего пункта показывает, что для каждого перехода суще-
ствует единственный элемент , задающий для него входное мультимно-
жество мест и выходное мультимножество . Дадим определение входному и
выходному мультимножеству.
Определение: Входное и выходное мультимножества мест и переходов.
Пусть задана сеть .
• Если для некоторого перехода имеем , то будем обозначать
;
• .
Будем говорить, что - входные, а - выходные места перехода . Таким
образом, согласно определению, справедливо . Далее, будем гово-
рить, что место инцидентно переходу , если или .
Расширим функции и на мультимножества переходов. Пусть
есть мультимножество переходов такое, что . Тогда положим
,
.
Сети Петри имеют удобную графическую форму представления в виде графа,
в котором места изображаются кружками, а переходы прямоугольниками, причем
место соединяется с переходом , если и соединяется с , если
для некоторого натурального числа . Здесь число называется кратностью
дуги, которое графически изображается рядом с дугой. Дуги, имеющие единичную
кратность, будут обозначаться без приписывания единицы.
( )
FTS N , , = ( )
n s s S ,...,
1 = ( )
n t t T ,...,
1 =
=∩ T S S TS F µ µ ×× ⊆
2 1 2 2 2 1 1 1 2 2 2 1 1 1 , , , , : , , , , , t t QtQ QtQF QtQQtQ≠⇒′′ ′ ≠′′ ′ ∈′′ ′ ′′ ′ ∀
{ } T F QtQt = ∈′′ ′ ,, |
T t ∈
F QtQ ∈′′ ′ ,,
Q′ Q ′′
( )
FTS N , , =
t F QtQ ∈′′ ′ ,,
( ) ( ) { } ( ) ( ) { }
s nt ns Q t s nt ns Q t * * * * , | , , , | , ∈ =′′ = ∈ =′ =
( ) ( ) { } ( ) ( ) { }
t ns nt s t ns nt s * * * * , | , , , | , ∈ = ∈ =
t * * t t
F ttt T t ∈ ∈∀ * * ,, :
s t t s * ∈ * t s ∈
( )⋅ * ( )* ⋅ T µ ∈Θ
kk tn tn tn++ + =Θ ...
22 11
k k tn tn tn*
2
*
2 1
*
1
* ... ++ + =Θ
* *
22
*
11
* ... kk tn tn tn++ + =Θ
s t ( ) t ns * , ∈ t s ( ) * , t ns ∈
Nn ∈ n