1. Мережі Петрі - математичний апарат для моделювання
Мережі Петрі - математичний апарат для моделювання динамічних дискретних систем. Описано в дисертаційній роботі Карла Петрі Kommunikation mit Automaten на здобуття ступеня доктора наук в 1962 році. Мережа Петрі являє собою двочастковий орієнтований граф, що складається з вершин двох типів - позицій і переходів, з'єднаних між собою дугами. Вершини одного типу не можуть бути з'єднані безпосередньо. У позиціях можуть розміщуватися мітки (маркери), здатні переміщатися по мережі.
Рис.1 Приклад мережі Петрі. Білими кружками позначені позиції, смужками - переходи, чорними кружками - мітки.
Подія в мережі Петрі - це спрацьовування переходу в мережі, при якому мітки з вхідних позицій цього переходу переміщаються у вихідні позиції. Події відбуваються миттєво, або різночасно, при виконанні деяких умов.
Мережі Петрі розроблялися для моделювання систем з паралельними взаємодіючими компонентами. Мережі Петрі вперше запропонував Карл Адам Петрі lt; # justify gt; 2. Мережі з інгібіторної дугами
Одним з найвідоміших розширень класу мереж Петрі є мережі Петрі з інгібіторної дугами. Це мережі, в яких крім звичайних дуг можуть бути присутніми так звані інгібіторні, що позначаються стрілками з наконечниками у вигляді чорних крапок (Мал. 2).
Інгібіторна дуга завжди веде від позиції до переходу. Перехід може спрацювати тільки тоді, коли у всіх позиціях, які пов'язані з ним інгібіторної дугами, відсутні фішки. Таким чином, за допомогою цих моделей можна здійснювати перевірку позиції на порожнечу. Відомо, що мережі Петрі з інгібіторної дугами еквівалентні машинам Тьюринга. Таким чином, для них нерозв'язні всі основні алгоритмічні проблеми: зупину, обмеженості, досяжності, жвавості та ін.
Розглянемо, яким чином можна вводити нелокальні перевірки пам'яті в мережах активних ресурсів. Спочатку нам потрібно ряд допоміжних тверджень. Теорема 1. Для будь-якої мережі Петрі з інгібіторної дугами існує еквівалентна їй мережа, в якій кожній позиції інцидентне не більше однієї інгібіторної дуги.
Рис.2 Побудова мережі, в якій кожній позиції інцидентне не більше однієї інгібіторної дуги.
Доказ: Як доказ розглянемо наступне перетворення.
Нехай у вихідній мережі позиції p інцідентни два інгібіторні дуги - (p, t1) і (p, t2). Перетворимо вихідну мережу, замінивши в ній позицію p на дві позиції - p1 і p2 з такими ж наборами звичайних дуг, що і у вихідній позиції p. Додамо інгібіторні дуги (p1, t1) і (p2, t2).
(Приклад перетворення зображений на Рис. 2. Тут і далі для ілюстрації перетворень ми розглядаємо в якості вихідної мережі (ліворуч) схему, що включає всі можливі зв'язки моделируемого синтаксичного елемента з іншими компонентами системи. У даному випадку розглядається позиція і дві інцідентние їй інгібіторні дуги, а також повний набір всіляких різних пов'язаних з ними елементів. Так, з позицією пов'язані два переходу -вхідний і вихідний. З переходами, в які ведуть інгібіторні дуги, можуть бути пов'язані вхідні і вихідні позиції.)
В якості результуючої мережі (праворуч) зображена мережу після перетворень. Переходи і позиції без підписів відповідають таким же по розташуванню переходам і позиціям вихідної мережі.
Початкову розмітку отримаємо з вихідної розмітки M, помістивши в p1 і p2 по M (p) фішок.
Очевидно, що через повного збігу початковоїрозмітки і набір звичайних дуг розмітки p1 і p2 завжди будуть збігатися.
Теорема 2. Для будь-якої мережі Петрі з інгібіторної дугами існує еквівалентна їй мережа, в якій кожному переходу інцидентне не більше однієї тінгібіторной дуги.
Доказ: Як доказ розглянемо наступне перетворення.
По-перше, додамо в мережу вимикач - нову позицію key з дугами (key (s), s) і (s, key (s)) для кожного переходу s. Таким чином, будь-який перехід мережі може спрацювати тільки тоді, коли в позиції key є фішка. У початковій розмітці в позицію-вимикач помістимо одну фішку.
Нехай у вихідній мережі переходу t інцідентни два інгібіторні дуги - (t, p1) і (t, p2). Перетворимо вихідну мережу, замінивши в ній перехід t на три переходи - t1, t2 і t3. У переходу t1 той же набір вхідних дуг, що і у t, і немає вихідних; у переходу t2 - той же набір вихідних дуг, що і у t, і немає вхідних; у переходу t3 немає вхідних дуг, а безліч вихідних дуг відповідає безлічі вхідних дуг вихідного переходу t. Додамо нову позицію p (з нульовою початковою розміткою) і три нові дуги - (t1, p), (p, t2) і (p, t3). Вихідні інгібіторні дуги (t, p1) і (t, p2) перетвори...
