Введение в архитектуру компьютеров


Здесь: – переход; O – место


Иногда функцию инцидентности F как компоненту сети Петри представляют в виде двух функций: PRE: P´T ®

í0,1ý, POST : T´P> {0,1}.

Из вершины pÎP в вершину tÎT дуга ведет тогда и только тогда, когда PRE(p, t) = 1, а из вершины tÎT в вершину pÎP тогда и только тогда, когда POST (t, p) = 1. Разметка изображается точками в местах.

Разметка сети позволяет описывать ее состояние. Функционирование сети Петри происходит посредством перехода от одной разметки к другой. Изменение разметок происходит вследствие срабатывания переходов. Переход t может сработать, если для него выполнено условие

"p (M(p) – PRE (p, t) ? 0),

где M – текущая разметка. В нашем примере такому условию удовлетворяют переходы t1 и t2. Срабатывание перехода t приводит к  изменению разметки: входные места перехода теряют по одной метке, а выходные – получают по одной метке.

Разметку M сети называют достижимой из M0, если существует последовательность срабатываний переходов, в результате которой разметка сети из M0  переходит в M. Рассмотрим формальную модель программ, в основу которой положено специальное расширение сетей Петри – ПМ-сети.

Обобщенная сеть Петри – это набор (P, T, F, H, M0), где P – множество мест; T – множество переходов; F: P´T®N?{0} и H: T´P®N?{0} – функция инцидентности; M0: P®N?{0} – начальная разметка; N – множество натуральных чисел.

Определим для сетей два типа меток: плюс-метки и минус-метки, соответственно расширим область значений функции разметки: M: P®{ …, -1, 0, 1, …}. Обозначим P+ = {p| M(p)>0}, P- = {p| M (p) < 0}. Введем функционал (предикатный функционал) C: H?F®{+, -}, т. е. каждая дуга сети помечается либо плюсом, либо минусом.

Изменим в соответствии с введенными дополнениями и правила функционирования сетей. Будем считать, что одновременно в месте не могут находиться плюс- и минус-метки. В связи с этим определим операцию аннигиляции меток, т. е. операцию одновременного уничтожения равного количества плюс- и минус-меток для одного и того же места.




- Начало -  - Назад -  - Вперед -



Книжный магазин