Конспект установочных лекций по комплексному курсу Информатика, Теория информации




Сети Петри - часть 5


Согласно определению понятия хода работы для сети Петри процесс р есть ход работы, если любой префикс р есть ход работы.

Структура действий р = (Е0, ?0, ?) называется совершенным ходом работы сети Петри N с конкретизацией b0, если справедливо одно из следующих условий:

(1)               Множество событий E0 бесконечно, и любой конечный префикс р есть ход работы сети N с исходной конкретизацией b0.

(2)               Множество событий Е0 конечно, и р есть ход работы сети N для начальной конкретизации b0 с конечной конкретизацией b1, и для b1

не существует непустого готового к передаче множества.

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

Две сети с исходными конкретизациями называются эквивалентными

(с точки зрения их работы), если они имеют одинаковые множества совершенных ходов работы.

Лемма (линеаризация процессов). Если р есть ход работы сети Петри N с исходной конкретизацией b, то каждая линеаризация р также есть ход работы N с исходной конкретизацией b.

Доказательство.

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

Обратное утверждение леммы не справедливо. Из множества последовательных ходов работы сети Петри нельзя сделать вывод о множестве не последовательных ходов работы.

Бесконечный ход работы р = (Е0, ?0, ?) сети Петри N с исходной конкретизацией b называется несправедливым по отношению вентиля а, если  одновременно выполняются следующие условия:

(1)        Множество {e

 Е0: ?(e) = a} событий, помеченных действием а, конечно.

(2)        Множество конечных префиксных процессов р1

 р, причем р1 = (Е1, ?1, ?1) с

{e

 Е0: ?(e) = a} = {e
 Е1: ?1(e) = a}

и

b0

b1,

причем вентиль а в b1




Содержание  Назад  Вперед