Розширені мережі Петрі

За допомогою трьох простих розширень прості мережі Петрі стають суттєво продуктивнішими.Як показано Хопкрофтом i Ульманом, "розширені мережі Петрі” (навіть без додатково введених нижче ваг дуг) за своєю ефективністю рівні машині Тьюрінга, тобто вони можуть застосовуватись як загальна модель обчислюваності.

Розширення:

Багаторазове маркування.

Кожен вузол може мати довільну кількість маркувань (при зображенні мережі Петрі допускається маркування коротко позначати числом). Правила активізації та перемикань змінюються відповідно:

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

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

Тобто кількість маркувань одного вузла може бути як завгодно великою, але відповідне число не може бути меншим від нуля.

Дуги-заперечення

Дуги-заперечення в мережах Петрі зображаються кружечком на кінці замість стрілки (рис.3.9) i не мають дугової ваги; дуги, що були визначені раніше, розглядаються як позитивні.

Рис. 3.9. Дуга-заперечення

Вони завжди направлені тільки від деякого вузла до деякого переходу, зворотного напрямку не дозволяється. Введення дуг-заперечень зумовлює оновлені пристосування правил активізації та перемикань:

- перехід активізований тільки тоді, коли кількість маркувань кожного вхідного вузла з позитивною дугою більша або дорівнює одиниці i коли кількість маркувань кожного вхідного вузла з дугою-запереченням дорівнює нулю (на рис.3.9 перехід t активізований, якщо P₁ маркований i P₂ не маркований);

- якщо активізований перехід перемикається, то кількість маркувань ycix вхідних вузлів з позитивними дугами цього переходу зменшується на одиницю, в той час як кількість маркувань вхідних вузлів з дугами-запереченнями залишається незмінною. Числа, що відповідають кількості маркувань ycix вихідних вузлів, як i раніше, збільшуються на одиницю.

Вага дуг

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

- перехід активізований тільки тоді, коли кількість маркувань кожного його вхідного вузла більша або дорівнює відповідній вазі дуги, а для дуги-заперечення дорівнюють нулю;

- при перемиканні переходу кількість маркувань кожного вхідного вузла зменшується на вагу відповідної вхідної дуги (вона залишається незмінною для дуг-заперечень); кількість маркувань кожного вихідного вузла збільшується на вагу відповідної вихідної дуги.