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




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


В таких случаях говорят о булевских сетях Петри или сетях условия-события.

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

Для целочисленной конкретизации b  сети Петри (Т0, р0, R) непустое подмножество К

 Т0 называется готовым к передаче, если для каждой ячейки р
 р0, справедливо:

| {k

 K: (р, k)
 R}| ? b(p).

Множество К вентилей по этому определению для некоторой конкретизации готово к передаче, если в каждой ячейке р находится достаточно меток, чтобы все вентили k

 K, для которых стрелка от ячейки р ведет к вентилю k, при переключении были снабжены метками. Если для каких-то ячеек предусмотрены ограничения на помещаемые туда метки, то имеет место ограничение мощности. Множество К только тогда готово к передаче, когда проходящие через вентили метки не превосходят соответствующие максимально допустимые значения. В случае булевских сетей Петри для каждой ячейки р
 Р0

и каждого вентиля k

 K требуется выполнение следующего условия для готовности к передаче множества вентилей К
 Т:

(р, k)

 R => b(p) ^ | { k
 K: (р, k)
 R}| ? 1

и дополнительно следующего условия бесконфликтности: для каждой ячейки р

 Р0

и каждого вентиля k

 K должно иметь место

(k, р)

 R => ¬b(p) ^ | { k
 K: (k, р)
 R}| ? 1.

Это условие говорит о том, что вентиль k может открыться только тогда, когда все ячейки, к которым ведут ребра из k, помечены через false. Аналогично булевские сети Петри соответствуют целочисленным сетям Петри, в которых каждая ячейка имеет мощность 1.

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


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