Прості сіті Петрі

Мережа Петрі з трьох елементів: безліч місць, безліч переходів та відношення інцидентності.

Умови в пункті 3 свідчать, що для кожного переходу існує єдиний елемент , що задає для нього вхідне мультимножина місць та вихідне мультимножина . Дамо визначення вхідного та вихідного мультимножини.

Будемо говорити, що -вхідні, а -вихіднімісця переходу. Таким чином, згідно з визначенням, справедливо . Далі будемо говорити, що місцеінцидентнопереходу або .

Розширимо функції і на мультимножини переходів. Нехай є безліч переходів таке, що . Тоді покладемо

.

Мережі Петрі мають зручну графічну форму уявлення як графа, у якому місця зображуються кружками, а переходи прямокутниками. Місця і переходи, причому місце з'єднується з переходом і з'єднується з для деякого натурального числа . Тут число називаєтьсякратністю дуги, яке графічно зображується поруч із дугою. Дуги, що мають одиничну кратність, позначатимуться без приписування одиниці.

Приклад. Приклад мережі

Як простий приклад розглянемо мережу, де

1. ;

2. ;

3.

У графічній формі мережу представлено на Рис.1. Мережа має чотири місця та три переходи. Ставлення задає дуги мережі. Так, наприклад, елемент задає чотири дуги: з і з з кратностями 2, з і з з одиничними кратностями. Для переходу справедливо та . Для місця можна обчислити та .

Мал. 1: Приклад графа мережі Петрі

Саме собою поняття мережі має статичну природу. Для завдання динамічних показників використовується поняттямаркуваннямережі , тобто. функції , зіставляє кожному місцю ціле число.Графічно маркування зображується як точок, званихмітками(tokens), і які у гуртках, відповідних місцям мережі. Відсутність міток дещо свідчить про нульове маркування цього місця.

Приклад. Приклад маркованої мережі.

На Рис.2 наведено приклад маркованої мережі. У початковій маркування місце має дві мітки (токена), місце - одну мітку, а місця - жодної мітки, тобто. .

Мал. 2: Приклад маркованої мережі Петрі

Мережі Петрі були розроблені та використовуються для моделювання паралельних та асинхронних систем. При моделюванні в мережах Петрі місця символізують стан системи, а перехід символізують якісь дії, що відбуваються в системі. Система, перебуваючи в якомусь стані, може породжувати певні дії, і, навпаки, виконання якоїсь дії переводить систему з одного стану до іншого.

Поточне стан системи визначає маркування мережі Петрі, тобто. розташування міток (токенів) у місцях мережі. Виконання дії в системі, в мережах Петрі визначається як спрацювання переходів. Спрацювання переходів породжує нове маркування, тобто. породжує нове розміщення міток (токенів) у мережі. Визначимо функціонування маркованих мереж, заснований на спрацюванні окремих переходів.

Іншими словами, перехід вважається збудженим (активованим) при певному маркуванні, якщо в кожному його вхідному місці є кількість міток не менше кратності відповідних дуг. Збуджений (активований) перехід може спрацювати, причому при спрацьовуванні з кожного його вхідного місця вилучається, а кожне вхідне додається кілька міток, що дорівнює кратності відповідних дуг. Якщо одночасно збуджено (активовано)кілька переходів, спрацювати може будь-який з них або будь-яка їхня комбінація. Наприклад, нехай у мережі малюнку 2 спрацюють переходи і . Отримаємо мережу представлену малюнку 3.

Мал. 3: Нова мережа з маркуванням.

Композиційний підхід до побудови мереж Петрі передбачає можливість побудови складніших мереж із менш складних складових. Для цього вводяться точки доступу, які дозволяють об'єднувати прості мережі шляхом синхронізації подій та станів (переходів та місць).

1. - ім'я(ідентифікатор) t-точки доступу;
2. - Деякий алфавіт;
3. - Помітна функція, де . Запис позначає множину всіх кінцевих і непустих мультимножин, визначених на множині .

1. - ім'я (ідентифікатор) s-точки доступу;
2. - безліч таке, що .

Введені поняття точок доступу надають можливість запровадити дві основні операції над мережами Петрі для побудови композиційних мереж:

1. Операція злиття переходів - дозволяє породжувати та описувати синхронізацію паралельних процесів (tmerge);

2. Операція злиття місць – дозволяє застосовувати до мереж операції послідовної композиції, вибору, ітерації та інші (smerge).

Мал. 4: Приклад операції злиття переходів

Мал. 5: Приклад операції злиття місць

Наведені операції мають такий зміст:

При злитті місць- визначається набір станів у мережі, які ідентифікуються як стан мережі, визначений ім'ям s-точки доступу. Злиття різних мереж проводиться так, що якщо в одній мережі досягнуто описаний стан, то в іншій мережі цей стан також досягається;

При злитті переходів– визначається алфавітподій, видимих ​​із t-точки доступу. Кожен перехід у мережі позначається або невидимою подією, або комбінацією подій з алфавіту точки доступу. Злиття по переходах проводиться так, що якщо при спрацьовуванні однієї мережі виникає деяка комбінація подій, то ця комбінація подій відбувається в другій мережі.

---