Интеллектуальный анализ выполнения бизнес-процессов в системе электронного документооборота. Матвейкин В.Г - 34 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

36
вой и т.п. В первую очередь нужно выяснить существование таких алгоритмов. Эти вопросы формулируются как массовые
алгоритмические проблемы для сетей: проблема ограниченности (существует ли алгоритм, который позволяет узнать, явля-
ется ли данная сеть ограниченной), проблема потенциальной живости переходов, проблема живости сетей, проблема устой-
чивости, проблема безопасности. Говорят, что проблема разрешима, если соответствующий алгоритм распознавания свойств
существует, в противном случае проблема неразрешима.
Большинство из перечисленных выше проблем связано с определением возможности достижения некоторых специаль-
ных разметок в сети (например, с достижением t-тупиковых разметок для данного перехода
t
), т.е. с проблемой достижимо-
сти заданной разметки. В этой проблеме ставится вопрос о существовании алгоритма, с помощью которого можно узнать
для произвольной сети
N
и произвольной разметки
M
, принадлежит ли
M
множеству
)(NR
. Ниже будет показано, на-
пример, что проблемы живости и достижимости эквивалентны в этом смысле, что решение одной из них автоматически ре-
шает другую.
Несколько особняком стоят проблемы R-включения и R-эквивалентности сетей Петри. Пусть задан класс сетей, которые
имеют одно и то же множество мест (или их множества мест изоморфны). В первом случае необходимо выяснить существо-
вание алгоритма, устанавливающего для любых двух сетей из этого класса, имеет ли место соотношение
)()(
21
NRNR ⊆
, во
втором –
)()(
21
NRNR =
.
3.2.2. Проблемы ограниченности и безопасности
Некоторое место
p
в сети
N
может оказаться неограниченным по двум причинам. Первая заключается в следующем.
Пусть свободный язык сети
)(NL
содержит последовательность срабатываний
21
ττ=τ
такую, что
))()(()()[()[(
1212221110
pMpMMMMMMM >∧≥∧τ∧τ
.
Поскольку
12
MM ≥
, то любая подпоследовательность срабатываний, начинающаяся при разметке
1
M
, может повто-
риться и начиная с разметки
. Это означает, что любая последовательность вида
n
21
ττ
также принадлежит
)(NL
, каким
бы большим не было
n
. Следовательно, разметка места
p
может безгранично расти. Например, для места
2
p
в сети на
рис. 7 существует
1
tλ=τ
, где
λ
– пустое слово, такое, что
)0)(1)(()())0,0,1,1()[0,0,0,1((
202101110
=>=∧≥∧== pMpMMMMtM
.
Однако место
4
p
не ограничено по другой причине, так как нельзя найти пару достижимых в этой сети разметок
1
M
и
таких, что
))()(()(
414212
pMpMMM >∧≥
, хотя и ясно, что последовательности срабатываний вида
nn
ttt
321
ведут к нако-
плению любого числа
n
фишек в
4
p
. Можно отметить следующую разницу в неограниченности мест
2
p
и
4
p
: в
2
p
может
быть "бесконечное" число фишек, а в
4
p
– сколько угодно большое, но конечное число фишек, так как переход
3
t
может
сработать только конечное число раз, не большее, чем число срабатываний перехода
1
t
. Таким образом, неограниченность
места
4
p
"вторична" по отношению к неограниченности места
2
p
.
Исследование проблемы ограниченности сводится к анализу графа – покрывающего дерева сети. Для любой сети такой
граф конечен и может быть построен с помощью следующей процедуры:
• Первоначально предполагается, что дерево содержит единственную вершину-корень
и не имеет дуг.
• Путь
M
– вершина дерева, которая еще не объявлена листом (т.е. вершиной, из которой не исходит ни одна дуга),
но в дереве нет исходящих из нее дуг. Возможны четыре случая:
1) ни один из переходов сети не может сработать при разметке
M
, т.е.
)(/: tFMTt •≥∈∀
. В этом случае вершина
M
объявляется листом;
2) на пути из корня дерева в вершину
M
существует вершина
M
′
такая, что
MM
=
′
. Вершина
M
объявляется
листом;
3) на пути из корня дерева в вершину
M
существует вершина
M
′
такая, что
MM
<
′
. Для любого места
p
такого,
что
)()(
pMpM
<
′
, значение, соответствующей координаты
M
заменяется на
ω
и вершина
M
объявляется ω-листом;
4) если ни один из вышеперечисленных случаев не имеет места, то
M
– внутренняя вершина дерева. Для каждого пере-
хода
Tt ∈
такого, что
)(tFM •≥
, в дерево добавляется новая вершина
)()( tFtFMM •+•−=
′
и дуга, ведущая из
M
в
M
′
, помеченная символом
t
.
Вопросы для самоконтроля
1. Для решения какого класса задач предназначены сети Петри?
2. Дайте формальное определение сети Петри.
3. Что такое разметка сети Петри?
4. Что такое место в сети Петри?
5. Что такое переход в сети Петри?
6. В каком случае переход называется потенциально живым?
7. Какая сеть Петри считается безопасной?

Страницы