Дослідження дерева досяжності

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

Дерево досяжності в загальному випадку може бути нескінченним з вершинами таких типів:

– внутрішнє маркування, яке є досяжним з початкового маркування та не є тупиковим (рис. 3.15, а);

– тупикове маркування (рис. 3.15, б), з якого не може спрацьовувати ні один перехід;

– дублююче маркування m_д (рис. 3.15, в), яке відповідає вже введеному раніше у дерево маркуванню m = m_д. Якщо на шляху з початкового маркування до m_д зустрічається маркування m = m_д, то m_д стає маркуванням-циклом або циклічним маркуванням m_ц (рис. 3.15, г);

– накопичуюче маркування m_н, відповідно якому на шляху від початкового маркування існує інше маркування m таке, що m £ m_н (рис. 3.15, д).

Рис. 3.15 Типи маркувань: а – внутрішнє; б – тупикове;
в – дублююче; г – циклічне; д – накопичуюче

Нескінченність дерева можлива тільки у випадку існування накопичуючих маркувань, які породжують циклічне повторення однакових послідовностей спрацьовуючих переходів.

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

w + a = w; w – a = w; a < w.

Тоді алгоритм побудови скінченного дерева досяжності базується на наступних положеннях:

1. Послідовно обробляються вершини-маркування, які утворюються внаслідок спрацьовування переходів із початкового маркування сітки. Результатом обробки кінцевих (необроблених) вершин є їх перетворення в один з наступних типів: тупикову чи дублюючу.

2. Якщо поточне маркування m не кваліфікується як один з двох наведених типів вершин, то m стає внутрішньою. Для кожної внутрішньої вершини напідставі виконання умови збудження переходів і правила їх спрацьовування формується підмножина безпосередньо досяжних маркувань, котрі у дереві стають кінцевими вершинами.

Нові кінцеві маркування m¢ визначаються за результатами спрацьовування збуджених у m переходів за наступними правилами:

– якщо m(p_i) = w, то m¢ (p_i) = w;

– якщо на шляху з початкового маркування до m¢ існує таке маркування m², що m² < m¢ і m² (p_i) < m¢ (p_i), то m¢ (p_i) = w;

– у протилежному випадку m¢ (p_і) зберігає своє значення, отримане внаслідок спрацьовування переходу.

3. Коли всі вершини будуть оброблені, алгоритм завершується.

Побудова скінченого дерева досяжності дозволить практично використати його для дослідження властивостей сітки Петрі.

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

– в позначеннях дуг дерева використані усі переходи сітки;

– немає вершин дерева, що позначають як тупикові або накопичуючі маркування;

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

– існує хоча б один шлях повернення у вершину початкового маркування.

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

Приклад визначення та аналізу властивостей сітки Петрі. Подамо за графічним зображенням сітки на рис. 3.16 її теоретико-множинне та матричне визначення, побудуємо дерево досяжності (рис. 3.17) і визначимо властивості сітки.

Теоретико-множинне визначення сітки:

P = { p ₁, p ₂, p ₃, p ₄);

T = { t ₁, t ₂, t ₃);

F (p_i, t ₁) = 1 для і = 1, 2, 3;

F (p ₄, t ₁) = 0, F (p ₄, t ₂) = 1, F (p_i, t ₂) = 0 для і = 1, 2, 3;

F (p ₃, t ₃) = 1, F (p_i, t ₃) = 0 для і = 1, 2, 4;

H (t ₁, p ₁) = 1, H (t ₁, p_i) = 0 для і = 2, 3, 4;

H (t ₂, p_i) = 1 для і = 2, 3; H (t ₂, p_i) = 0 для і = 1, 4;

H (t ₃, p ₄) = 1, H (t ₃, p_i) = 0 для і = 1, 2, 3;

m₀(p ₁) = m₀(p ₃) = 1; m₀(p ₂) = m₀(p ₄) = 0.

Множини вхідних позицій переходів:

^· t ₁ = { p ₁, p ₂, p ₃}; ^· t ₂ = { p ₄}; ^· t ₃ = { p ₃}.

Множини вихідних позицій переходів:

t ₁^· = { p ₁}; t ₂^· = { p ₂, p ₃}; t ₃^· = { p ₄}.

Рис. 3.16. Сітка Петрі з накопиченням маркерів

Матричне подання:

Позиції p ₁, p ₃, p ₄ – безпечні, а позиція p ₂ – необмежена. Тому сітка в цілому необмежена і незберігаюча.

Переходи спрацьовують усі, але є тупикове маркування m₃, циклічне повторення маркувань m₂ ® m₄ ® m₅ та початкове маркування недосяжне з будь-якого іншого у дереві. Тому сітка нежива.

Рис. 3.17. Кінцеве дерево досяжності