Модифікація мереж Петрі з антисипацією по позиції
We propose a modification of Petri nets with strong anticipation on a position. The extension modifies a transition rule by adding a new term that contains an integer function of the new marking in the position. The differences from classic Petri nets are found; for example, the set of markings that...
Збережено в:
| Дата: | 2023 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2023
|
| Теми: | |
| Онлайн доступ: | https://journal.iasa.kpi.ua/article/view/279774 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | System research and information technologies |
| Завантажити файл: |  |
Репозитарії
System research and information technologies| _version_ | 1866302903644323840 |
|---|---|
| author | Statkevych, Vitalii |
| author_facet | Statkevych, Vitalii |
| author_sort | Statkevych, Vitalii |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2023-05-24T21:28:17Z |
| description | We propose a modification of Petri nets with strong anticipation on a position. The extension modifies a transition rule by adding a new term that contains an integer function of the new marking in the position. The differences from classic Petri nets are found; for example, the set of markings that are reachable from a current marking by firing the enabled transition can either be empty or contain more than one marking. We consider the construction of a reachability graph and a coverability tree. We give the conditions for the existence of the coverability tree and propose the algorithm for constructing the coverability tree that generalizes the well-known classic algorithm. The main ideas and constructions are illustrated in the examples. |
| doi_str_mv | 10.20535/SRIT.2308-8893.2023.1.08 |
| first_indexed | 2025-07-17T10:28:09Z |
| format | Article |
| fulltext |
В.М. Статкевич, 2023
102 ISSN 1681–6048 System Research & Information Technologies, 2023, № 1
УДК 519.711.7
DOI: 10.20535/SRIT.2308-8893.2023.1.08
МОДИФІКАЦІЯ МЕРЕЖ ПЕТРІ З АНТИСИПАЦІЄЮ
ПО ПОЗИЦІЇ
В.М. СТАТКЕВИЧ
Анотація. Запропоновано модифікацію мережі Петрі з урахуванням сильної
антисипації по позиції. Розширення реалізовано за допомогою введення в пра-
вило запуску переходу нового доданка, який містить цілочислову функцію від
нової кількості фішок у позиції. Знайдено важливі відмінності від класичних
мереж Петрі, наприклад, множина маркувань, досяжних з поточного марку-
вання запуском дозволеного переходу, може бути як порожньою, так і містити
більше одного маркування. Розглянуто питання побудови графу досяжності та
дерева покриття. Указано умови, за яких дерево покриття існує, а для його по-
будови запропоновано алгоритм, який узагальнює відомий класичний алго-
ритм. Основні ідеї та конструкції проілюстровано на прикладах.
Ключові слова: мережа Петрі, антиcипація, умова запуску переходу, граф
досяжності, дерево покриття.
Пам’яті Юрія Вікторовича Богданського (10.06.1949–21.11.2021)
ВСТУП
Мережі Петрі, запропоновані К.А. Петрі в 1962 р., є зручним засобом для
проектування, аналізу та моделювання різних процесів та мереж [1–3]. Бага-
тьма авторами були розглянуті та досліджені різні модифікації мереж Петрі:
інгібіторні, часові, стохастичні, кольорові, неперервні та інші [1–6]. У де-
яких з цих мереж правила запуску переходу можуть відрізнятись від класич-
ного правила запуску переходу, запропонованого К.А. Петрі. Наприклад, в
інгібіторних мережах вводиться інгібіторна дуга, яка проведена від позиції
до переходу та яка забороняє запуск цього переходу, якщо в позиції наявна
фішка. Також в неперервних мережах правило запуску відрізняється від
класичного і пристосоване до ситуації, коли кількість фішок у позиції може
бути будь-яким дійсним невід’ємним числом і перехід може бути запущений
нецілу кількість разів, а саме вводиться поняття ступеня запуску переходу.
У 1992 р. Д. Дюбуа [7–9] запропонував поняття інкурсії, антисипації
або передбачення, коли новий стан об’єкта залежить не тільки від певних
попередніх станів, а і від певних майбутніх станів (сильна антисипація) або
їх оцінок (слабка антисипація). Об’єкти можуть бути різної природи: дифе-
ренціальні рівняння з неперервним часом та їх скінченно-різницеві аналоги
з дискретним часом, диференціальні рівняння звичайні та з частинними по-
хідними, клітинні автомати досліджувались, наприклад, у працях [7–12],
диференціальні рівняння з випереджальним аргументом – у працях [13–15].
У цій роботі пропонується модифікувати правило запуску переходу
класичної мережі Петрі з урахуванням сильної антисипації, а саме: ввести
новий доданок, який містить функцію від нової кількості фішок у позиції.
Якщо функція }0{}0{: NΝf , то кількість фішок у позиції також буде
цілим невід’ємним числом, як і у випадку класичних мереж Петрі. Наскіль-
Модифікація мереж Петрі з антисипацією по позиції
Системні дослідження та інформаційні технології, 2023, № 1 103
ки відомо автору, такі модифікації мереж Петрі з антисипацією в літературі
не розглядались.
ПОПЕРЕДНІ ВІДОМОСТІ
Мережею Петрі називають набір 0μ,,, WTP , де },,{ 1 mppP – скінчен-
на множина позицій, },,{ 1 nttT – скінченна множина переходів,
}0{)()( NTPPTW – вагова функція, }0{:μ0 NP – почат-
кове маркування. Для зображення мереж Петрі використовують дводольний
орієнтований мультиграф [1–3]. Перехід t називають дозволеним, якщо для
кожної вхідної позиції p виконується нерівність ),()(μ tpWp . Якщо пере-
хід t дозволений, то він може бути запущений (але не обов'язково має бути
запущеним), після його запуску нова кількість фішок у позиції p дорівнює
),(),()(μ)(μ 1 ptWtpWpp kk . (1)
Модифікуємо правило запуску переходу (1). А саме розглянемо розши-
рення класичної мережі Петрі },,{,μ,,,
10 mpp ffWTP , де функція
}0{}0{: NN
ipf відповідає позиції ip , mi 1 (також будемо вико-
ристовувати позначення
ipi ff ). Перехід t , як і раніше, називаємо дозво-
леним, якщо для кожної вхідної позиції p виконується нерівність
),()(μ tpWp . Нехай після запуску дозволеного переходу t нова кількість
фішок )(μ pnew у позиції p задовольняє рівняння запуску переходу:
))(μ(),(),()(μ)(μ pfptWtpWpp newpknew . (2)
Рівняння (2) запуску переходу узагальнює правило запуску переходу (1)
в класичній мережі Петрі. Запропоноване розширення назвемо мережею
Петрі з антисипацією по позиції.
ВИКОНАНИЯ МЕРЕЖ ПЕТРІ З АНТИСИПАЦІЄЮ ПО ПОЗИЦІЇ
Розглянемо виконання мереж Петрі з антисипацією по позиції по декількох
прикладах.
Приклад 1. Розглянемо класичну мережу Петрі, зображену на рис. 1. Її
граф досяжності зображено на рис. 1. Для функції наступного стану
22 })0{(})0{(:δ NN T , яка природним чином узагальнюється для
довільної скінченної послідовності запусків переходів [1], виконується, на-
приклад, рівність
)0,1(),μ(δ),μ(δ 120210 tttt . (3)
Рис. 1
4
3
p1
p2
t1t1 t1
t2
t1
t2
t2
(4,3)
(3,2)
(2,1)
(1,0)
2
а б
2
В.М. Статкевич
ISSN 1681–6048 System Research & Information Technologies, 2023, № 1 104
Розширимо дану класичну мережу, а саме введемо антисипацію по по-
зиції. Нехай позиціям ip відповідають функції }0{}0{: NΝif ,
2,1i ,
6,2)(;54,2)(;30,0)( 111 kkkfkkkfkkf ; (4)
5)5(};4,3{,2)(};5,4,3{,0)( 222 fkkkfkkf .
Обидва переходи 1t і 2t дозволені в початковому маркуванні.
Рівняння запуску переходу 1t з маркування 0μ згідно з рівнянням (2)
мають вигляд
))(μ(3))(μ(1)(μ)(μ 1111101 pfpfpp newnewnew ; (5)
))(μ(2))(μ(1)(μ)(μ 2222202 pfpfpp newnewnew .
Тоді 3)(μ 1 pnew , }4,3,2{)(μ 2 pnew . Аналогічні рівняння запуску 2t такі:
))(μ(2))(μ(2)(μ)(μ 1111101 pfpfpp newnewnew ; (6)
))(μ(1))(μ(2)(μ)(μ 2222202 pfpfpp newnewnew .
Тоді }5,4,2{)(μ 1 pnew , 1)(μ 2 pnew . Таким чином, на відміну від кла-
сичної однозначної функції стану T2})0{(:δ N 2})0{( N , для мережі
рис. 1 отримуємо з введенням антисипації по позиції багатозначну функцію:
)})0{((2 2
2})0{(:δ NN T ;
)}4,3(μ),3,3(μ),2,3(μ{),μ(δ 32110 t ; (7)
)}1,5(μ),1,4(μ),1,2(μ{),μ(δ 65420 t . (8)
З’ясуємо, чи виконується рівність (3), тобто як саме співвідносяться
множини ),μ(δ 210 tt і ),μ(δ 120 tt ?
Розглянемо рівняння запуску переходу 2t з маркувань ),μ(δμ 10 tk ,
3,2,1k :
))(μ(2)(μ)(μ)),(μ(1)(μ 2222111 pfpppfp newknewnewnew . (9)
Із першого рівняння отримуємо 1)(μ 1 pnew . Для другого рівняння роз-
глянемо випадки:
1) для 1k маємо ))(μ()(μ 222 pfp newnew , }5,0{)(μ 2 pnew ;
2) для 2k маємо ))(μ(1)(μ 222 pfp newnew , 1)(μ 2 pnew ;
3) для 3k маємо ))(μ(2)(μ 222 pfp newnew , }4,3,2{)(μ 2 pnew .
Таким чином, )}5,1(),4,1(),3,1(),2,1(),1,1(),0,1{(),μ(δ 210 tt .
Тепер розглянемо рівняння запуску переходу 1t з маркувань
),μ(δμ 20 tk , 6,5,4k :
Модифікація мереж Петрі з антисипацією по позиції
Системні дослідження та інформаційні технології, 2023, № 1 105
))(μ(1)(μ)(μ 1111 pfpp newknew , ))(μ()(μ 222 pfp newnew .
Для першого рівняння розглянемо випадки:
1) для 4k маємо ))(μ(1)(μ 111 pfp newnew , 1)(μ 1 pnew ;
2) для 5k маємо ))(μ(3)(μ 111 pfp newnew , 3)(μ 1 pnew ;
3) для 6k маємо ))(μ(4)(μ 111 pfp newnew , розв’язків немає.
Із другого рівняння отримуємо }5,0{)(μ 2 pnew . Отже, остаточно от-
римуємо )}5,3(),0,3(),5,1(),0,1{(),μ(δ 120 tt .
Підсумовуючи маємо, що рівність (3) у загальному випадку не викону-
ється. Множини ),μ(δ 21tt та ),μ(δ 12tt у загальному випадку різні, більш того
жодна з цих множин не обов’язково у загальному випадку має бути підмно-
жиною іншої: ),μ(δ),μ(δ 1221 tttt , ),μ(δ 12tt ),μ(δ 21tt .
Зауваження 1. Для мережі Петрі з антисипацією по позиції, яка міс-
тить m позицій, функція )})0{((2})0{(:δ
m
Tm NN .
Приклад 2. Модифікуємо умову прикладу 1, а саме: в рівності (4) по-
кладемо
6,2)(
~
;54,4)(
~
;30,0)(
~
111 kkkfkkkfkkf .
Тоді замість рівняння (5) отримуємо ))(μ(
~
3)(μ 111 pfp newnew ,
3)(μ 1 pnew , замість рівняння (6) маємо ))(μ(
~
2)(μ 111 pfp newnew ,
2)(μ 1 pnew . Таким чином, множина (7) не змінюється, а множина (8) стає
одноелементною: )}1,2(μ{),μ(δ 420 t . Інакше кажучи, із запуском пере-
ходу 2t з маркування 0μ настає маркування, визначене однозначно, як і у
випадку класичних мереж Петрі. Зазначимо, що перехід 2t у маркуванні 4μ
не дозволений.
Рівняння (9) із заміною функції 1f на 1
~
f мають такі самі розв’язки, то-
му )}5,1(),4,1(),3,1(),2,1(),1,1(),0,1{(),μ(δ 210 tt . Рівняння запуску переходу 1t
з маркування ),μ(δμ 204 t набувають вигляду ))(μ(
~
1)(μ 111 pfp newnew ,
))(μ()(μ 222 pfp newnew . Тоді 1)(μ 1 pnew , }5,0{)(μ 2 pnew . Таким чином,
),μ(δ)}5,1(),0,1{(),μ(δ 210120 tttt .
Наведений приклад показує, що в окремому випадку може виконува-
тись вкладення ),μ(δ),μ(δ 2112 tttt .
Зауваження 2. У прикладі 2 маркування )0,1( слід назвати тупиковим
за аналогією із класичними мережами Петрі, оскільки жоден перехід у ньо-
му не дозволений. У маркуванні )5,1( перехід 2t не дозволений, а перехід 1t
хоча формально і дозволений, але друге з рівнянь запуску переходу 1t
))(μ(
~
)(μ 111 pfp newnew , ))(μ(4)(μ 222 pfp newnew не має розв’язків. У
цьому і є відмінність ситуації від класичної. А саме, у мережі Петрі з анти-
сипацією по позиції перехід може бути дозволений в тому сенсі, що кількос-
ті фішок у вхідних позиціях не менші, ніж ваги відповідних дуг, але рівнян-
В.М. Статкевич
ISSN 1681–6048 System Research & Information Technologies, 2023, № 1 106
ня запуску такого переходу не має розв’язків і ),μ(δ t . Таке маркування
)5,1( назвемо некласичним тупиковим маркуванням.
Зауваження 3. Якщо у прикладі 1 у рівності (4) вибрати
6,3)(
~~
;54,2)(
~~
;30,0)(
~~
111 kkkfkkkfkkf ,
то рівніння (5) набуде вигляду ))(μ(
~~
3)(μ 111 pfp newnew і має нескінченну
множину розв’язків },8,7,6,3{)(μ 1 pnew . Отже, множина ),μ(δ t у загаль-
ному випадку зліченна.
Приклад 3. Розглянемо мережу Петрі з антисипацією по позиції, зо-
бражену на рис. 2, і нехай позиції 1p відповідає функція
}0{}0{:1 NΝf , де 0)(1 kf для }4,3{k ,
2)(1 kkf для }4,3{k , а позиції 2p відповідає
тотожно нульова функція 0)(2 kf . Рівняння за-
пуску переходу t з поточного маркування μ ма-
ють вигляд
2)(μ)(μ)),(μ(1)(μ)(μ 221111 pppfpp newnewnew . (10)
Кожний запуск переходу t додає по дві фішки в позицію 2p , як і
в класичних мережах Петрі. Очевидна рівність 210 μ),2,2(μ{),μ(δ t
)}2,4(μ,)2,3( 3 .
Рівняння запуску переходу t з маркування 1μ згідно з рівняннями (10),
мають вигляд ))(μ(1)(μ 111 pfp newnew , 2)(μ)(μ 22 ppnew , звідки ви-
пливає )}4,1{(),μ(δ 1 t . Аналогічним чином )}6,0{()),41((δ t, , а маркування
)6,0( тупикове, оскільки в ньому перехід t не дозволений.
Маркування 2μ є покривним для маркування 0μ , з рівнянь (10) випливає
)};4,4(),4,3(),4,2{(),μ(δ 2 t
}0{)},22,4(),22,3(),22,2{(),)(3,2(δ Nkkkktk .
Нарешті, маркування 3μ теж є покривним для маркування 0μ , але в
ньому перше з рівнянь (10) набуває вигляду ))(μ(3)(μ 111 pfp newnew і не
має розв’язків ),μ(δ 3 t . Тому згідно із зауваженням 2 маркування 3μ
некласичне тупикове. Отримана ситуація, яка суперечить класичним мережам
Петрі: у загальному випадку з маркування μ , яке є покривним для маркуван-
ня μ , неможливо запустити ті самі переходи, що з маркування μ , яке по-
кривається. Тому введення елемента ω потребує додаткових умов.
Отже, можемо побудувати граф досяжності, зображений на рис. 3. Для
даної мережі граф нескінченний, є деревом і має єдину нескінченну гілку
kk :)2,3{( }}0{Ν . Інші гілки скінченні і завершуються або тупико-
вими маркуваннями },4,3:)2,0{( kk , або некласичними тупиковими
маркуваннями }:)2,4{( Nkk . Зазначимо, що у працях [4, гл. 4; 6] для ілю-
Рис. 2
3
p1 p2
2
t
Модифікація мереж Петрі з антисипацією по позиції
Системні дослідження та інформаційні технології, 2023, № 1 107
страції досяжних маркувань неперервних мереж Петрі з двома (трьома) по-
зиціями використовуються двовимірні (тривимірні) графіки відносно коор-
динат )(μ),(μ 21 pp ),((μ 1p ),(μ 2p ( )(μ 3p відповідно).
Також зазначимо, що в побудові дерева
покриття для класичної мережі Петрі кіль-
кість нових маркувань дорівнює кількості до-
зволених переходів у відповідному маркуван-
ні [1, 2]. Проте для мережі з антисипацією по
позиції кількість нових маркувань визнача-
ється рівняннями запуску переходів і у загаль-
ному випадку може бути зліченною (див. за-
уваження 3).
Перехід від нескінченного графу досяж-
ності до скінченного дерева покриття
пов’язаний із введенням елемента ω .
Тоді виникає питання, чи можна з маркування
μ , яке є покривним для маркування μ , за-
пустити ті самі послідовності переходів, що з
маркування μ , яке покривається. Наприклад, обидва маркування 2μ і 3μ є
покривними для маркування 0μ , але множина ),μ(δ 2 t непорожня, а ),μ(δ 3 t
Зазначимо, що умова обмеженості носіїв усіх функцій не дає відповіді
на це питання: }4,3{supp 1f , 2supp f . Причому недостатньо
лише знати всі некласичні тупикові маркування – множина послідовностей
запусків переходів може бути вужчою, але вона може бути непорожною.
Зазначимо, що граф досяжності може бути також і скінченним: для
мережі прикладу 2 граф досяжності скінченний (рис. 4). Таким же способом
можна переконатись, що і граф досяжності для мережі прикладу 1
скінченний, всі маркування з множини μ з множини 2}5,4,3,2,1,0{ досяжні.
У цьому неважко переконатись, якщо записати відповідні рівняння запусків
переходів 1t і 2t з кожного досяжного маркування.
Рис. 4
5
4
3
2
1
1 2 3 4
t1
0
μ(p1)
μ(p2)
t2
Рис. 3
8
7
6
5
4
3
2
1
1 2 3 4 5
t
0
μ(p2)
μ(p1)
В.М. Статкевич
ISSN 1681–6048 System Research & Information Technologies, 2023, № 1 108
Приклад 4. Розглянемо мережу Петрі з антисипацією по позиції, зобра-
жену на рис. 5, і нехай позиціям ip відповідають функції }0{:Νif
}0{ N , 2,1i ;
.0,1
,,0
sgn)(
,0,0
,,1
sgn)( 21 k
k
kkf
k
k
kkf
NN
Поточне маркування позначимо через ))(μ),((μμ 21 pp .
Розглянемо рівняння запуску переходу 1t з поточного маркування:
)(μsgn1)(μ)(μ),(μsgn1)(μ)(μ 222111 pppppp newnewnewnew .
Якщо 0)(μ 1 p , то перехід 1t не дозволений. Якщо 1)(μ 1 p , то
}1,0{)(μ 1 pnew . Якщо ж 2)(μ 1 p , то оскіль-
ки 1)(μ 1 pnew , 1)(μsgn 1 pnew , отримуємо
)(μ)(μ 11 ppnew . Друге рівняння з урахуван-
ням того, що 1)(μ 2 pnew , 0)(μsgn 2 pnew ,
має єдиний розв’язок 1)(μ)(μ 22 ppnew . Та-
ким чином, у поточному маркуванні ))(μ,0( 2p
перехід 1t не дозволений, ))),(μ,1((δ 12 tp )}1)(μ,1(),1)(μ,0{( 22 pp , а
для 2)(μ 1 p ))),(μ),(μ((δ 121 tpp )}1)(μ),(μ{( 21 pp .
Тепер розглянемо рівняння запуску переходу 2t з поточного маркування:
)(μsgn1)(μ)(μ),(μsgn1)(μ)(μ 222111 pppppp newnewnewnew .
Перше рівняння, 1)(μ 1 pnew , 1)(μsgn 1 pnew , має єдиний розв’язок
2)(μ)(μ 11 ppnew . Якщо 0)(μ 2 p , то перехід 2t не дозволений. Якщо
1)(μ 2 p , то друге рівняння набуде вигляду )(μsgn)(μ 22 pp newnew і не
має розв’язків. Якщо ж 2)(μ 2 p , то з урахуванням того, що 1)(μ 2 pnew ,
0)(μsgn 2 pnew , отримуємо )(μ 2pnew 1)(μ 2 p . Таким чином, у поточно-
му маркуванні )0),((μ 1p перехід 2t не дозволений, )),1),(μ((δ 21 tp ,
)}1)(μ,2)(μ{())),(μ),(μ((δ 21221 pptpp для 2)(μ 2 p .
Отже, можемо побудувати граф
досяжності, зображений на рис. 6. Для
даної мережі граф нескінченний, має
єдине некласичне тупикове маркування
)1,0( (оскільки в ньому перехід 1t
не дозволений, а перехід 2t хоча і до-
зволений, але )),1,0((δ 2t ) і не є
деревом ( )),2,2((δ)),2,2((δ 1221 tttt
)}2,4{( ). Зазначимо, що для класичної
мережі Петрі без антисипації, зображеної
на рис. 5, граф досяжності був би скін-
ченним і містив би всього два марку-
Рис. 5
p1 p2
t2
t1
4
3
2
1
1 2 3
t
0 μ(p1)
μ(p2)
t
Рис. 6
t1
t2
Модифікація мереж Петрі з антисипацією по позиції
Системні дослідження та інформаційні технології, 2023, № 1 109
вання )0,1( і )1,0( . Також зазначимо, що умова обмеженості носіїв усіх фун-
кцій не виконується: N1supp f , }0{supp 2 f .
Нарешті, зазначимо, що запуском переходу 1t з маркування )1,1(
)),0,1((δ 1t , яке є покривним для маркування )0,1( , можна отримати марку-
вання )2,0( , яке вже не є покривним для маркування )0,1( . Крім того, з мар-
кування )1,1( можна запускати перехід 1t нескінченну кількість разів і отри-
мувати маркування ),1( k , }1{\Nk , а в маркуванні )),1,1((δ)2,0( 1t перехід
1t хоча і дозволений, але )),2,0((δ 1t . Таким чином, проблема введення
елемента ω (див. приклад 3) для даної мережі зберігається.
ДЕРЕВО ПОКРИТТЯ ДЛЯ МЕРЕЖ ПЕТРІ З АНТИСИПАЦІЄЮ ПО ПОЗИЦІЇ
Розглянемо мережу Петрі з антисипацією по позиції з початковим марку-
ванням 0μ . Нагадаємо, що множину маркувань, досяжних з маркування μ ,
позначають через )μ(R [1–3]. Нехай мережа задовольняє дві додаткові умо-
ви 1 і 2.
Умова 1. Існує константа NC , яка залежить від мережі та від функ-
цій if ( mi 1 ), що для кожного маркування )μ(μ 0R і для кожного пе-
реходу t , дозволеного в маркуванні μ , рівняння запуску переходу t мають
не більше ніж C розв’язків.
Умова 2. Якщо маркування μ досяжне з маркування )μ(μ 0R послі-
довністю запусків переходів σ і є покривним для маркування μ , і до того
ж для певної позиції p )(μ)(μ pp , то:
а) або заздалегідь відоме скінченне число NN , що послідовність σ
можна запустити з маркування μ не більше ніж N разів;
б) або заздалегідь відомо, що послідовність σ можна запустити з мар-
кування μ нескінченну кількість разів, і причому жодне з отриманих цими
запусками маркувань не є некласичним тупиковим, а для всіх }0{Nk
довільне маркування )σ,μ(δμ k
k покривається кожним маркуванням
)σ,μ(δμ 1 kk і для вказаної позиції p )(μ)(μ 1 pp kk .
Зазначимо, що для класичної мережі Петрі без антисипації по позиції
умови 1, 2 і 2б виконуються завжди ( 1C ), умова 2а ніколи не виконується.
Проте з введенням антисипації по позиції з’являються мережі, для яких мо-
же не виконуватись
– або умова 1 – див., наприклад, зауваження 3;
– або умова 2 – у прикладі 3 маркування ),μ(δ)2,3( 0 t є покривним
для маркування 0μ , послідовність tδ можна запускати з маркування )2,3(
нескінченну кількість разів та отримувати маркування )2,3( k , }1{\Nk , але
маркування )),2,3((δ)4,2( t вже не є покривним для маркування )2,3( ,
більш того маркування ),(3,2)(δ)4,4( t некласичне тупикове.
Також зазначимо, що умова 2б є формалізацією нескінченного зростан-
ня по кожній гілці.
В.М. Статкевич
ISSN 1681–6048 System Research & Information Technologies, 2023, № 1 110
Якщо додаткові умови 1 і 2 виконуються, стає можливим ввести еле-
мент ω . Пропонується такий алгоритм побудови скінченного дерева
покриття, який узагальнює добре відомий класичний алгоритм [2, c. 51;
1, c. 94; 3, с. 23; 4, с. 39–40].
Крок 1. Позначити початкове маркування 0μ як корінь та присвоїти
йому мітку “нове”.
Крок 2. Поки існують нові маркування, виконувати такі операції:
Крок 2.1. Вибрати нове маркування μ .
Крок 2.2. Якщо μ збігається з одним з маркувань на шляху від кореня
до μ , присвоїти μ мітку “старе” та перейти до іншого нового маркування.
Крок 2.3. Якщо для маркування μ немає дозволених переходів, присвоїти
μ мітку “тупикове”; якщо ж для кожного дозволеного переходу t рівняння
запуску t не мають розв’язків, приcвоїти μ мітку “некласичне тупикове”.
Крок 2.4. Поки для маркування μ існують дозволені переходи t , рів-
няння запуску яких мають розв’язки, для кожного з них виконати такі
операції:
Знайти множину маркувань ),μ(δ t і для кожного маркування
),μ(δμ t виконати такі операції:
– якщо на шляху від кореня до маркування μ існує маркування μ , яке
покривається маркуванням μ , і для них виконується умова 2б, то замінити
)(μ p на ω для кожної позиції p , указаної в умові 2;
– ввести μ як вузол, з’єднати μ з μ дугою, помітити дугу символом t
і присвоїти μ мітку “нове”.
Очевидно, що певні операції наведеного алгоритму точно збігаються з
операціями класичного алгоритму [2, c. 51]. Відмінності обумовлені спосо-
бом введення , а також множиною ),μ(δ t , яка для дозволеного переходу t
може бути в загального випадку як порожньою, так і містити більше одного
маркування.
Теорема 1. Нехай для певної мережі Петрі з антисипацією по позиції
виконуються умови 1 і 2. Тоді дерево покриття для такої мережі скінченне.
Доведення точно повторює доведення теореми 4.1 [1, с. 97–98]. Ви-
користані в ньому леми 4.1–4.3 [1, с. 95–97] запозичуються без змін, а в до-
ведення само́ї теореми 4.1 вносяться такі два коригування:
1) наявність нескінченного шляху ,,, 210 xxx , який виходить з кореня
0x , свідчить про те, що в умові 2 виконується саме пункт 2б, а не пункт 2а –
таким чином введення елемента ω коректне;
2) кількість вершин, які слідують за кожною вершиною в дереві, обме-
жена не кількістю переходів, а константою C з умови 1.
Для мережі прикладу 4 побудова дерева покриття викликає складності:
вказані у прикладі 4 міркування свідчать про те, що умова 2 не виконується.
Приклад 5. Змінимо початкове маркування мережі в прикладі 4, нехай
)1,2(μ0 . Тоді умови 1 і 2 виконуються і в результаті застосування наведе-
ного алгоритму отримуємо дерево покриття, зображене на рис. 7.
Модифікація мереж Петрі з антисипацією по позиції
Системні дослідження та інформаційні технології, 2023, № 1 111
Зазначимо, що можливість побудови
дерева покриття за допомогою наведеного
алгоритму, тобто виконання умов 1 і 2, за-
лежить у тому числі і від початкового ма-
ркування 0μ та множини )μ( 0R . Тут си-
туація відрізняється від класичної: для
мережі Петрі без антисипації по позиції від
початкового маркування залежить конкре-
тний вигляд само́го дерева покриття, але
аж ніяк не можливість його побудови. Як і
у прикладі 4 умова обмеженості носіїв усіх
функцій не виконується, але на відміну від
прикладу 4 дерево покриття побудоване.
Як і у випадку класичних мереж Петрі, у дереві покриття не відобража-
ється певна інформація. Наприклад, послідовність 2
21 tt запустити неможли-
во, але на рис. 7 це не відображається.
Граф покриття будується за таким же принципом, як і у випадку класич-
них мереж Петрі [2]. Граф покриття для мережі прикладу 5 зображено на рис. 8.
Зауваження 4. Якщо послабити умову 2б і дозволити отримувати не-
класичні тупикові маркування, то дерево покриття залишиться скінченним.
Але виникне інша проблема —
можуть з’явитись зайві недося-
жні маркування. А саме, якщо в
дереві покриття буде наявне
певне маркування μ , яке місти-
тиме ω , то не можна буде зро-
зуміти чи повинне це марку-
вання μ бути насправді
наявним, чи наявність некласи-
чних тупикових маркувань ви-
ключатиме появу маркування μ . Один зі способів розв’язання цієї проблеми
може полягати у введенні нового додаткового елемента [ω /н.т.], але це мо-
же призвести до суттєвого збільшення кількості маркувань у дереві покрит-
тя, хоча дерево і залишиться скінченним.
ВИСНОВКИ
Запропоновано мережі Петрі з урахуванням сильної антисипації по позиції,
які розширюють класичні мережі Петрі за допомогою модифікації правила
запуску переходів. Наведено приклади виконання таких мереж; розглянуто
питання побудови графу досяжності та дерева покриття. Виявлені відмінно-
сті від класичних мереж Петрі, які вказують на необхідність подальшого
дослідження мереж такого типу.
Автор вдячний Олександру Сергійовичу Макаренко за плідні обгово-
рення та коментарі.
ЛІТЕРАТУРА
1. J. Peterson, Theory of Petri nets and system modeling. M.: Mir, 1984, 264 p.
2. T. Murata, “Petri nets: Properties, analysis, applications,” TIIER, vol. 77, no. 4,
pp. 41–85, 1989.
3. V.E. Kotov, Petri nets. M.: Nauka, 1984, 160 p.
Рис. 7
t1 t2
(2,1)
(2, ω)
(2, ω)
(ω, ω)
(ω, ω) (ω, ω)
t1 t2
t1
Рис. 8
(2,1)
(2, ω) (ω, ω)
t1 t2
t1 t1
t2
В.М. Статкевич
ISSN 1681–6048 System Research & Information Technologies, 2023, № 1 112
4. R. David and H. Alla, Discrete, Continuous, and Hybrid Petri Nets. Springer, Berlin,
Heidelberg, 2005.
5. T. Gu and R. Dong, “A novel continuous model to approximate time Petri nets:
modeling and analysis,”International Journal of Applied Mathematics and Computer
Science, vol. 15, no. 1, pp. 141–150, 2005.
6. C.R. Vazquez, C. Mahulea, J. Julvez, and M. Silva, “Introduction to Fluid Petri nets”,
Chapter in Book: “Control of Discrete-Event Systems,” Lecture Notes in Control and
Information Sciences, vol. 433, Eds. C. Seatzu, M. Silva, J.H. van Schuppen, Springer-
Verlag London, pp. 365–386, 2013. doi: 10.1007/978-1-4471-4276-8_18.
7. D. Dubois, “Incursive and hyperincursive systems, fractal machine and anticipatory
logic,” Computing Anticipatory Systems: CASYS 2000 – Fourth International Con-
ference. AIP Conference Proceedings 573, pp. 437–451, 2001. doi:
10.1063/1.1388710.
8. D. Dubois, “Theory of Incursive Synchronization and Application to the Anticipa-
tion of the Chaotic Epidemic,”International Journal of Computing Anticipatory Sys-
tems, vol. 10, pp. 3–18, 2001.
9. D. Dubois, “Generation of fractals from incursive automata, digital diffusion and
wave equation systems,” Biosystems, vol. 43, pp. 97–114, 1997. doi: 10.1016/S0303-
2647(97)01692-4.
10. A. Makarenko, “Multivaluedness Aspects in Self-Organization, Complexity and
Computations Investigations by Strong Anticipation,”Chapter in Book: Recent Ad-
vances in Nonlinear Dynamics and Synchronization; Eds. K. Kyamakya, W. Mathis,
R. Stoop, J. Chedjou, Z. Li, Springer, Cham, pp. 33–54, 2018. doi: 10.1007/978-3-
319-58996-1_3.
11. A. Makarenko, “Neural Networks with Strong Anticipation and Some Related Prob-
lems of Complexity Theory,” Chapter 12 in Series: Studies in Systems, Decisions
and Control, vol. 55. Ed. George H. Dimirovski, Springer, 2016, pp. 267–281. doi:
10.1007/978-3-319-28860-4_12.
12. A. Makarenko, “Toward Multivaluedness Aspects in Self-Organization, Complexity
and Computations Investigations,” Forth International Workshop on Nonlinear Dy-
namics and Synchronization INDS’15, Klagenfurt, Austria, Alpen-Adria University,
July 31, 2015, pp. 84–93.
13. L.E. Elsgolts and S.B. Norkin, Introduction to the theory of differential equations
with deviating argument. M.: Nauka, 1971, 296 p.
14. G.A. Kamensky and A.L. Skubachevskii, Linear boundary value problems for
differential-difference equations. M.: Ed. MAI, 1992, 190 p.
15. V.G. Pimenov and D.A. Korotkiy, “On solving systems of differential equations with
lead and lag,” Izvestiya UrGU, 2006, no. 44, pp. 113–139.
Received 03.08.2022
INFORMATION ON THE ARTICLE
Vitalii M. Statkevych, ORCID: 0000-0001-5210-9890, Educational and Scientific
Institute for Applied System Analysis of the National Technical University of Ukraine
“Igor Sikorsky Kyiv Polytechnic Institute”, Ukraine, e-mail: mstatckevich@yahoo.com
A MODIFICATION OF PETRI NETS WITH ANTICIPATION ON A POSITION /
V.M. Statkevych
Abstract. We propose a modification of Petri nets with strong anticipation on a po-
sition. The extension modifies a transition rule by adding a new term that contains
an integer function of the new marking in the position. The differences from classic
Petri nets are found; for example, the set of markings that are reachable from a cur-
rent marking by firing the enabled transition can either be empty or contain more
than one marking. We consider the construction of a reachability graph and a cover-
ability tree. We give the conditions for the existence of the coverability tree and pro-
pose the algorithm for constructing the coverability tree that generalizes the well-known
classic algorithm. The main ideas and constructions are illustrated in the examples.
Keywords: Petri net, anticipation, transition rule, reachability graph, coverability tree.
|
| id | journaliasakpiua-article-279774 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2025-07-17T10:28:09Z |
| publishDate | 2023 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/3a/ecc3a95a5a9a335f1b8262c146c0243a.pdf |
| spelling | journaliasakpiua-article-2797742023-05-24T21:28:17Z A modification of Petri nets with anticipation on a position Модифікація мереж Петрі з антисипацією по позиції Statkevych, Vitalii Petri net anticipation transition rule reachability graph coverability tree мережа Петрі антиcипація умова запуску переходу граф досяжності дерево покриття We propose a modification of Petri nets with strong anticipation on a position. The extension modifies a transition rule by adding a new term that contains an integer function of the new marking in the position. The differences from classic Petri nets are found; for example, the set of markings that are reachable from a current marking by firing the enabled transition can either be empty or contain more than one marking. We consider the construction of a reachability graph and a coverability tree. We give the conditions for the existence of the coverability tree and propose the algorithm for constructing the coverability tree that generalizes the well-known classic algorithm. The main ideas and constructions are illustrated in the examples. Запропоновано модифікацію мережі Петрі з урахуванням сильної антисипації по позиції. Розширення реалізовано за допомогою введення в правило запуску переходу нового доданка, який містить цілочислову функцію від нової кількості фішок у позиції. Знайдено важливі відмінності від класичних мереж Петрі, наприклад, множина маркувань, досяжних з поточного маркування запуском дозволеного переходу, може бути як порожньою, так і містити більше одного маркування. Розглянуто питання побудови графу досяжності та дерева покриття. Указано умови, за яких дерево покриття існує, а для його побудови запропоновано алгоритм, який узагальнює відомий класичний алгоритм. Основні ідеї та конструкції проілюстровано на прикладах. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2023-03-30 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/279774 10.20535/SRIT.2308-8893.2023.1.08 System research and information technologies; No. 1 (2023); 102-112 Системные исследования и информационные технологии; № 1 (2023); 102-112 Системні дослідження та інформаційні технології; № 1 (2023); 102-112 2308-8893 1681-6048 uk https://journal.iasa.kpi.ua/article/view/279774/274365 |
| spellingShingle | мережа Петрі антиcипація умова запуску переходу граф досяжності дерево покриття Statkevych, Vitalii Модифікація мереж Петрі з антисипацією по позиції |
| title | Модифікація мереж Петрі з антисипацією по позиції |
| title_alt | A modification of Petri nets with anticipation on a position |
| title_full | Модифікація мереж Петрі з антисипацією по позиції |
| title_fullStr | Модифікація мереж Петрі з антисипацією по позиції |
| title_full_unstemmed | Модифікація мереж Петрі з антисипацією по позиції |
| title_short | Модифікація мереж Петрі з антисипацією по позиції |
| title_sort | модифікація мереж петрі з антисипацією по позиції |
| topic | мережа Петрі антиcипація умова запуску переходу граф досяжності дерево покриття |
| topic_facet | Petri net anticipation transition rule reachability graph coverability tree мережа Петрі антиcипація умова запуску переходу граф досяжності дерево покриття |
| url | https://journal.iasa.kpi.ua/article/view/279774 |
| work_keys_str_mv | AT statkevychvitalii amodificationofpetrinetswithanticipationonaposition AT statkevychvitalii modifíkacíâmerežpetrízantisipacíêûpopozicíí AT statkevychvitalii modificationofpetrinetswithanticipationonaposition |