Операции над сетями Петри

Маслаков Максим Петрович

соискатель, ассистент СКГМИ (ГТУ), г. Владикавказ

E-mail: kalbash1@mail.ru

Маслаков Денис Петрович

Аспирант, ассистент СКГМИ (ГТУ), г. Владикавказ

E-mail: d-maslakov@mail.ru

Как известно сеть Петри состоит из 4-х элементов: множество позиций Р, множество переходов Т, входная функция I и выходная функция О. Входная и выходная функции связаны с переходами и позициями. Входная функция I отображает переход tj в множество позиций I(tj), называемых входными позициями перехода. Выходная функция О отображает переход tj в множество позиций О(tj), называемых выходными позициями перехода.

Структура сети Петри определяется ее позициями, переходами входной и выходной функции.

Определение:

Сеть Петри С является четверкой С=(Р, Т, I, О), где

Р={р1, p2, ..., pn} – конечное множество позиций, n≥0;

Т={t1, t2, ..., tm} – конечное множество переходов, m≥0. Множество позиций и множество переходов не пересекаются, Р∩Т=Ø;

I: T→P^∞ есть входная функция – отображение из переходов в комплекты позиций;

О: T→P^∞ есть выходная функция – отображение из переходов в комплекты позиций.

Мощность множества Р есть число n, а мощность множества Т есть число m. Произвольный элемент Р обозначается символом рi, i=1, ..., n, а произвольный элемент Т – символом tj, j=1, ..., m.

Позиция pi является входной позицией перехода tj в том случае, если pi ÎI(tj); pi является выходной позицией, если pi ÎО(tj) [1, с. 101]

Операции над сетями Петри описанные в [3, с. 71]:

1.  Конкатенация – последовательная комбинация сетей;

2.  Объединение – композиция аналогична объединению множеств;

3.  Параллельная композиция – параллельное функционирование сетей;

4.  Пересечение – аналогична теоретико-множественному определению пересечения;

В настоящей работе вводится операция, взятия декартова произведения сетей Петри по аналогии с декартовым произведением графов и автоматов, описанная в [2, с. 162].

Для данных сетей Петри С₁=(Р₁, Т₁, I₁, О₁) и С₂=(Р₂, Т₂, I₂, О₂) декартовым произведением называется сеть Петри С=(Р, Т, I, О), где позиции и переходы C(P)=P₁ x P₂ и C(T)=T₁ x T₂ – декартово произведение множеств позиций и переходов исходных сетей, соответственно. А входная и выходная функции – I и O, далее называемая отношение смежности вершин F=(I,O), равная F=PxTÈTxP – задает множество дуг, соединяющих позиции и переходы, причем множествa {PxT}∩{TxP}=Ø. Дуга f (PxT), соединяющая позицию P(p₁p₂) с переходом T(t₁t₂), существует, если существует дуга f₁ (p₁t₁) и дуга f₂ (p₂t₂) в исходных сетях Петри, аналогично, существует дуга f (TxP), соединяющая переход T(t₁t₂) с позицией P(p₁p₂), если существует дуга f₁ (t₁p₁) и дуга f₂ (t₂p₂) в исходных сетях Петри.

Пусть заданы две сети Петри C₁ (P, T, F₁) и C₂ (S, Z, F₂) (Рис. 1). Необходимо произвести их декартово произведение.

Множество позиции данных сетей Петри Р={P₁, P₂} и S={S₁, S₂, S₃}

Множество переходов этих сетей Т={t₁, t₂} и Z={z₁, z₂}

Рисунок 1. Сети Петри C₁ (P, T, F₁) и C₂ (S, Z, F₂)

Декартово произведение множеств позиций и переходов:

V=P x S={P₁, P₂} x {S₁, S₂, S₃}=[V₁={P₁S₁}, V₂={P₁S₂}, V₃={P₁S₃}, V₄={P₂S₁}, V₅={P₂S₂}, V₆={P₂S₃}];

M=T x Z={t₁, t₂} x {z₁, z₂}=[m₁={t₁z₁}, m₂={t₁z₂}, m₃={t₂z₁}, m₄={t₂z₂}].

Отображение позиций в переходы, входная функция F(I) равна:

I (m₁)=F(t₁) x F(z₁)={P₁} x {S₁}={ P₁S₁}=V₁;

I (m₂)=F(t₁) x F(z₂)={P₁} x {S₂ S₃}={ P₁S₂}, {P₁S₃}=V₂, V₃;

I (m₃)=F(t₂) x F(z₁)={P₂} x {S₁}={ P₂S₁}=V₄;

I (m₄)=F(t₂) x F(z₂)={P₂} x {S₂ S₃}={ P₂S₂}, {P₂S₃}=V₅, V₆;

Отображение переходов в позиции, выходная функция F(O) равна:

O (m₁)=F(t₁) x F(z₁)={P₂} x {S₂ S₃}={ P₂S₂}, { P₂S₃}=V₅,V₆;

O (m₂)=F(t₁) x F(z₂)={P₂} x {S₁}={ P₂S₁}=V₄;

O (m₃)=F(t₂) x F(z₁)={P₁} x {S₂ S₃}={ P₁S₂}, { P₁S₃}=V₂,V₃;

O (m₄)=F(t₂) x F(z₂)={P₁} x {S₁}={ P₁S₁}=V₁;

На основании выше проведенных вычислений получаем сеть Петри, являющуюся произведением C₁ (P, T, F₁)и C₂ (S, Z, F₂) (Рис. 2).

Также рассмотрено матричное представление декартова произведения сетей Петри.

Матрица входной функции сети Петри D^- есть матрица строки которой являются позициями сети, а столбцы переходами сети Петри, на пересечении i-ой строки с ј-ым столбцом ставится единица, если i-ая позиция входит в ј-ый переход, ноль в противном случае.

Рисунок 2. Сеть Петри, являющаяся произведением сетей Петри

C₁ (P, T, F₁) и C₂(S, Z, F₂)

Матрица выходной функции сети Петри D⁺ есть матрица строки которой являются переходами сети, а столбцы позициями сети Петри, на пересечении i-ой строки с ј-ым столбцом ставится единица, если i-ый переход входит в ј-ую позицию, ноль в противном случае.

Матрица D^- определяет входы в переходы, а D⁺ - выходы. Матричная форма представления сети Петри С (P, T, D^-, D⁺) эквивалентна стандартной форме представления сетей Петри, но позволяет дать определения сети в терминах векторов и матриц [2, с. 106].

Пусть даны сети Петри C₁ (P, T, F₁) и C₂ (S, Z, F₂) (Рис. 3).

Рисунок 3. Сети Петри C₁ (P, T, F₁) и C₂(S, Z, F₂)

Произведем декартово произведение представленных сетей.

Множество позиции данных сетей Петри Р={P₁, P₂} и S={S₁, S₂, S₃}

Множество переходов этих сетей Т={t₁, t₂} и Z={z₁, z₂, z₃, z₄}

Декартово произведение множеств позиций и переходов:

V=P x S={P₁, P₂} x {S₁, S₂, S₃}=[V₁={P₁S₁}, V₂={P₁S₂}, V₃={P₁S₃}, V₄={P₂S₁}, V₅={P₂S₂}, V₆={P₂S₃}];

M=T x Z={t₁, t₂} x {z₁, z₂, z₃, z₄}=[m₁={t₁z₁}, m₂={t₁z₂}, m₃={t₁z₃}, m₄={t₁z₄}, m₅={t₂z₁}, m₆={t₂z₂}, m₇={t₂z₃}, m₈={t₂z₄}].

Строим матрицы входной и выходной функций, D^- и D⁺ соответственно, для сети Петри C₁ (P, T, F₁):

Для сети Петри C₂ (S, Z, F₂):

Теперь строим матрицы D^- и D⁺ для C (V, M, F) - произведения двух сетей C₁ (P, T, F₁)и C₂(S, Z, F₂). Матрицы входной D^- и выходной функций D⁺ искомой сети Петри C (V, M, F) получились путем перемножения матриц входной и выходной функции D^- и D⁺ сетей Петри C₁ (P, T, F₁) и C₂ (S, Z, F₂), соответственно (Рис. 4).

На основании полученных матриц входной D^- и выходной D⁺ функций строим сеть Петри C (V, M, F), являющуюся произведением C₁ (P, T, F₁) и

C₂ (S, Z, F₂) (Рис. 5).

Рисунок 4. Матрицы входной D^- и выходной функций D⁺ искомой сети Петри C (V, M, F)

Рисунок 5. Произведение сетей Петри C₁ (P, T, F₁) и C₂(S, Z, F₂) (рисунок 3)

Список литературы:

1.Захаров Н.Г., Рогов В.Н. Синтез цифровых автоматов: учеб. пособие. Ульяновск: УлГТУ, 2003. - 135 с.

2.Мелихов А.Н. Ориентированные графы и конечные автоматы: монография. М.: Наука, 1971. – 416 с.

3.Питерсон Дж. Теория сетей Петри и моделирование систем: Пер. с англ. М.: Мир, 1984. - 264 с.