Конструкції мереж Петрі із сильною антисипацією за позицією та за переходом у випадку дійсних функцій
We propose extending the classic Petri nets and considering D. Dubois’s strong anticipation in two ways. We propose to add a new term into a transition rule that contains a real-valued function of a new marking in a certain place (strong place anticipation) or of a new marking in the input place of...
Saved in:
| Date: | 2024 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2024
|
| Subjects: | |
| Online Access: | https://journal.iasa.kpi.ua/article/view/304607 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | System research and information technologies |
| Download file: |  |
Institution
System research and information technologies| _version_ | 1867334445365723136 |
|---|---|
| author | Statkevych, Vitalii |
| author_facet | Statkevych, Vitalii |
| author_institution_txt_mv | [
{
"author": "Vitalii Statkevych",
"institution": "Навчально-науковий Інститут Прикладного Системного Аналізу Національного Технічного Університету України \"Київський Політехнічний Інститут імені Ігоря Сікорського\", Київ"
}
] |
| author_sort | Statkevych, Vitalii |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2024-05-23T07:09:36Z |
| description | We propose extending the classic Petri nets and considering D. Dubois’s strong anticipation in two ways. We propose to add a new term into a transition rule that contains a real-valued function of a new marking in a certain place (strong place anticipation) or of a new marking in the input place of a certain transition (an example of strong transition anticipation). Any integer constraints are not applied either to the weight function or to the marking in contrast to the classic Petri nets (as in continuous Petri nets). The execution of the mentioned nets is investigated, and important properties are stated. Several examples of reachability graphs are given, and differences from classic Petri nets are formulated. We also investigate the conditions of the equality of the markings, which are obtained by firing the sequences of transitions tjtk and tktj. |
| doi_str_mv | 10.20535/SRIT.2308-8893.2024.1.09 |
| first_indexed | 2025-07-17T10:28:31Z |
| format | Article |
| fulltext |
В.М. Статкевич, 2024
122 ISSN 1681–6048 System Research & Information Technologies, 2024, № 1
УДК 519.711.7
DOI: 10.20535/SRIT.2308-8893.2024.1.09
КОНСТРУКЦІЇ МЕРЕЖ ПЕТРІ ІЗ СИЛЬНОЮ
АНТИСИПАЦІЄЮ ЗА ПОЗИЦІЄЮ ТА ЗА ПЕРЕХОДОМ
У ВИПАДКУ ДІЙСНИХ ФУНКЦІЙ
В.М. СТАТКЕВИЧ
Анотація. Запропоновано розширити класичні мережі Петрі та врахувати
сильну антисипацію в сенсі Д. Дюбуа двома способами. Пропонується ввести
в правило запуску переходу новий доданок, який містить дійснозначну функ-
цію від нової кількості фішок у даній позиції (сильна антисипація за позицією)
та від нової кількості фішок у вхідній позиції для даного переходу (приклад
сильної антисипації за переходом). На відміну від класичних мереж Петрі
умови цілочисловості вагової функції та цілочисловості маркування не накла-
даємо аналогічно неперервним мережам Петрі. Розглянуто виконання таких
мереж, указано важливі властивості, для декількох прикладів побудовано гра-
фи досяжності та сформульовано відмінності порівняно з класичними мере-
жами Петрі. Також досліджено умови виконання рівності маркувань для по-
слідовностей запусків переходів kjtt і jk tt .
Ключові слова: мережа Петрі, сильна антиcипація, правило запуску переходу,
граф досяжності, цілочислова функція, функція наступного стану, послідов-
ність запусків переходів, гранична досяжність.
ВСТУП
Мережі Петрі, запропоновані К.А. Петрі в 1962 р., є зручним та потужним
інструментом для проектування, аналізу та моделювання різних процесів,
мереж та систем [1–3]. Нині відомо багато різних модифікацій класичних
мереж Петрі, зокрема, інгібіторні, стохастичні, кольорові, неперервні, часові
та інші мережі [2–5], у яких правило запуску переходу може відрізнятись від
класичного правила запуску переходу.
У неперервних мереж Петрі, запропонованих у праці [4] (див. деталь-
ніше монографію [3]), конструктивна відмінність від класичних мереж по-
лягає в тому, що кількість фішок у позиції може бути будь-яким дійсним
невід’ємним числом, а модифіковане правило запуску переходу дозволяє
запускати перехід нецілу кількість разів, тобто вводиться поняття ступеня
запуску переходу.
Відомі також часові неперервні мережі та інші типи мереж Петрі,
у яких кількість фішок у позиції також може не бути цілим числом [3].
Зазначимо, що для стохастичних мереж Петрі середня кількість фішок у по-
зиції природним чином може не бути цілим числом [2].
Поняття антисипації, коли новий стан об’єкта залежить не тільки від
попередніх станів, а також від оцінок майбутніх станів, отриманих за допо-
могою внутрішньої прогнозної моделі, розглядалось багатьма авторами [6].
Конструкції мереж Петрі із сильною антисипацією за позицією та за переходом…
Системні дослідження та інформаційні технології, 2024, № 1 123
Д. Дюбуа у 1992 р. запропонував поняття сильної антисипації, коли замість
оцінок майбутніх станів використовуються саме майбутні стани [7; 8]. У працях
[7–10; 12] досліджувались системи різної природи із сильною антисипацією.
Модифікація класичних мереж Петрі із сильною антисипацією за пози-
цією була запропонована в [11]: у правило запуску переходу вводився новий
доданок, який містив цілочислову функцію }0{}0{: NΝf від нової
кількості фішок у позиції. Для такої функції кількість фішок у позиції зали-
шається цілим невід’ємним числом, як і у випадку класичних мереж Петрі.
У роботі ідея врахування сильної антисипації в класичній мережі Петрі
реалізується у двох напрямках. Пропонується ввести в правило запуску пе-
реходу новий доданок, який містить дійсну функцію R);0[:f від но-
вої кількості фішок
– у позиції (антисипація за позицією),
– у вхідній позиції для даного переходу (приклад антисипації за пере-
ходом).
Для такої функції вважається корисним відмовитись від умов цілочис-
ловості вагової функції та цілочисловості маркування аналогічно непере-
рвним мережам Петрі, але дозволити запускати перехід лише цілу кількість
разів, як і у класичних мережах Петрі. Наскільки автору відомо, такі мережі
Петрі з антисипацією не розглядались.
ПОПЕРЕДНІ ВІДОМОСТІ
Мережа Петрі — це набір 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 . (2)
Тут );0[)()( TPPTW є дійсною ваговою функцією, а
);0[:μ0 P — дійсним початковим маркуванням, тобто на відміну від
класичних мереж Петрі умови цілочисловості вагової функції та цілочисло-
вості маркування не накладаємо. Функція R);0[:
ipf відповідає пози-
В.М. Статкевич
ISSN 1681–6048 System Research & Information Technologies, 2024, № 1 124
Рис. 1
ції ip , mi 1 (також будемо використовувати позначення if ). Рівняння
запуску переходу t (вважаємо перехід t дозволеним):
))(μ(),(),()(μ)(μ pfptWtpWpp newpknew , (3)
де )(μ pnew — нова кількість фішок у позиції p , узагальнює правило запус-
ку переходу (1) класичної мережі Петрі. Запропоноване розширення (2) на-
звемо мережею Петрі з антисипацією за позицією та дійсними функціями.
Зазначимо, що випадок цілочислової вагової функції, цілочислових марку-
вань та цілочислових функцій if запропоновано у праці [11].
Розглянемо виконання таких мереж.
Твердження 1. Нехай у мережі Петрі з анти-
сипацією за позицією та дійсною функцією, яка
зображена на рис. 1, );0[μ0 , );0[ w ,
);0[ w . Позиції p відповідає лінійна функція
baxxf )( , 0a , Rb . Тоді:
1) якщо w0μ і wawb )1( , то послідовність запусків перехо-
дів kt є дозволеною для всіх Nk , відповідна послідовність маркувань
,μ,μ,μ 210 має вигляд
1
0 ))1(1)((μ)1(μ aawwba kk
k , (4)
і збігається до wawwb 1* )(μ , причому швидкість збіжності є
лінійною.
2) якщо w0μ або wawb )1( , то існує таке }0{NK , що
послідовність kt є дозволеною для всіх Kk , але послідовність 1Kt вже
не є дозволеною (тобто маркування Kμ є тупиковим).
Доведення. Рівняння запуску переходу t з поточного маркування kμ
має вигляд
bawwfww kkkkk
111 μμ)μ(μμ ; (5)
)()1(μ)1()(μ)1(μ 111
1
wwbaabwwa kkk . (6)
Доведемо методом математичної індукції, що wkμ , якщо умови
п. 1) виконані. База індукції: виконується нерівність w0μ і перехід t є
дозволеним. Припущення індукції: нехай wkμ . Тоді перехід t є дозво-
леним, а з рівностей (6) випливає оцінка
wwawwak ))1(()1(μ 1
1 ,
яка доводить крок індукції. Тобто послідовність запусків переходів kt є до-
зволеною для всіх Nk .
Доведемо методом математичної індукції рівність (4). База індукції ви-
пливає з рівностей (6), крок індукції набуває вигляду
)()1(μ)1(μ 11
1 wwbaa kk
Конструкції мереж Петрі із сильною антисипацією за позицією та за переходом…
Системні дослідження та інформаційні технології, 2024, № 1 125
)()1(]))1(1)(()(1[)1( 11
0
1 wwbaaawwbaa kk
11)1(1
0
)1( ])1()1()1[()()(1 aaaaawwba kk
.))1(1)(()(1 1)1(
0
)1( aawwba kk
Зазначимо, що рівності (6) визначають арифметико-геометричну про-
гресію dquu nn 1 , тому рівність (4) також можна отримати із загальних
міркувань.
Із рівності (4) граничним переходом за k отримуємо *μμ k , як-
що k , а також w*μ . Зазначимо, що збіжність *μμ k також можна
довести за допомогою принципу стискальних відображень, не використовуючи
рівність (4). Справді, оператор RR )()1(: 1 bwwxaxT є
стиском
)()1( 1 bwwxaTyTx
yxabwwya 11 )1()()1( ,
а тому має єдину нерухому точку *x , яку знаходимо з рівняння (5):
baxwwxx *** , 1* )( awwbx .
Оцінимо швидкість збіжності послідовності ,μ,μ,μ 210 до *μ :
111*
1 )()()1(μ)1(μμ awwbwwbaa kk
*1111 μμ)1()1()(μ)1( kk aaawwba
*
0
)1( μμ)1( ka
(згідно з принципом математичної індукції). Таким чином, швидкість збіж-
ності є лінійною, доведення п. 1) завершено.
Для доведення п. 2) міркування такі. Якщо w0μ , то перехід t вже
не є дозволеним у початковому маркуванні, тому 0K . Якщо ж w0μ ,
але wawb )1( (для зручності дві наведені нерівності можна
об’єднати в одну подвійну нерівність 0
1 μ)( wawwb ), то для пе-
вного K виконується оцінка wKμ . Справді, рівність (4) виконується в
даному разі для всіх Kk , тому
waawwba KK
K
1
0 ))1(1)((μ)1(μ ,
11
0 )())((μ)1( awwbwawwba K ,
1
0
1
)(μ
)(
)1(
awwb
awwbw
a K ,
В.М. Статкевич
ISSN 1681–6048 System Research & Information Technologies, 2024, № 1 126
1
1
0
1
)(
)(μ
log
awwbw
awwb
K a ,
1
μ
log 0
1
wwbaw
wwba
K a
(тут ][x позначає цілу частину числа x ). Отже, перехід t стає недозволе-
ним, маркування Kμ стає тупиковим, а послідовність маркувань
Kμ,,μ,μ,μ 210 стає скінченною. Твердження 1 доведено.
Із твердження 1 випливають такі наслідки:
1) існують такі w , w , a , b та початкове маркування 0μ , що *μ мо-
же дорівнювати довільному наперед заданому невід’ємному числу;
2) для структури WTP ,, класичної мережі Петрі показаного на рис. 1
вигляду, тобто для довільних ваг w і w існує така функція baxxf )(
і таке початкове маркування 0μ , що *μ може дорівнювати довільному на-
перед заданому невід’ємному числу;
3) згідно з принципом стискальних відображень )μμ( *
0
)μμ:( * kk N ;
4) рівність (4) свідчить про те, що точка kμ ділить відрізок ]μ;μ[ *
0 або
]μ;μ[ 0
* у заданому відношенні: *
0 μ))1(1(μ)1(μ kk
k aa .
Нагадаємо, що у класичних мережах Петрі послідовність кількостей
фішок у певній позиції має скінченну границю тоді і тільки тоді, коли ця
послідовність стабілізується, починаючи з деякого номера (також послідов-
ність кількостей фішок у певній позиції може мати нескінченну границю
ω ). Але з введенням антисипації за позицією з дійсною функцією по-
слідовність kμ може мати довільну скінченну границю *μ і при цьому в
загальному випадку *μμ k . Така властивість є характерною саме для непе-
рервних мереж Петрі і називається граничною досяжністю або lim -
досяжністю [3, с. 135–136; 5].
Зазначимо, що випадок 0a відповідає класичній мережі Петрі без
антисипації, якщо змінити вагу дуги wbptW ),( (за умови wb ). У
випадку 01 a оператор T не є стиском, рівність (4) зберігається, але
kμ , якщо k , і можна вводити символ ω . Випадок 1a не
розглядаємо, оскільки значення 1μ k згідно з рівнянням (5) може стати
від’ємним. Випадок 1a розглянемо окремо у прикладі 1.
Приклад 1. Розглянемо мережу Петрі з антисипацією за позицією та
дійсною функцією, зображену на рис. 1, де 4μ0 , 1w , 0w , 1a ,
3b . Тоді рівняння запуску переходу t з початкового маркування 0μ має
вигляд 3μ14μ 11 згідно з рівнянням (5), звідки 0μ1 . Таким чином,
отримуємо нове маркування );0[μ1 , яке взагалі не є маркуванням у
класичному сенсі та яке не є зліченною множиною. Звернемо увагу, що за
Конструкції мереж Петрі із сильною антисипацією за позицією та за переходом…
Системні дослідження та інформаційні технології, 2024, № 1 127
антисипації за позицією та цілочислових функцій }0{}0{: NNf
множина ),μ(δ t зліченна і незліченною бути не може [11, c. 106].
Рівняння запуску переходу t з маркування 1μ має вигляд
3μ1μμ 212 , воно має розв’язки 0μ2 , якщо 4μ1 , і не має
розв’язків, якщо }4{\);1[μ1 (перехід є дозволеним, якщо 1μ1 ). Тому
нове маркування, яке збігається з уже отриманим раніше “маркуванням”
);0[μ1 , отримане не класичним запуском переходу t , а умовним за
умови 4μ1 .
Отже, будуємо граф досяжності (рис. 2). Для даної мережі граф є скін-
ченним, не є деревом і містить єдине класичне маркування 0μ та маркуван-
ня 1μ , яке не з’являється у класичних мережах Пе-
трі. Граф не містить тупикових маркувань. Також у
графі існують класичний запуск переходу t та умо-
вний, причому умовні переходи характерні саме для
неперервних мереж Петрі [3, c. 116–119].
Зауваження 1. У монографії [3, c. 115–116] зазначається, що у непере-
рвних мережах Петрі кількість маркувань може бути нескінченною, а тому
пропонується оригінальний механізм макромаркувань, кількість яких скін-
ченна.
Розглянемо довільну мережу Петрі з антисипацією за позицією, у якій
позиціям ip відповідають лінійні функції iii bxaxf )( , mi 1 . Нехай
)μ(R — множина маркувань, досяжних з маркування μ , t і t — множи-
ни вхідних та вихідних позицій переходу t відповідно [2, 3].
Твердження 2. Якщо 1ia , mi 1 , то для кожного маркування
)μ(μ 0R та для кожного переходу t множина ),μ(δ t містить не більше од-
ного елемента.
Доведення випливає з твердження 1, оскільки рівняння вигляду (5) не
може мати двох або більше розв’язків.
Теорема 1. Нехай виконуються такі умови:
1) 1ia , mi 1 ;
2) для деяких j і k обидві послідовності запусків переходів kjtt і jk tt
є дозволеними у поточному маркуванні )μ(μ 0R , а обидві множини
}μ{),μ(δ jkkjtt і }μ{),μ(δ kjjk tt є непорожніми;
3) ji tp або ji tp , ki tp або ki tp .
Тоді виконується еквівалентність
),(),(або0())(μ)((μ ijjiiikjijk ptWtpWapp
)),(),( kjki ptWtpW .
Доведення. Позначимо ijji wtpW ),( , ijij wptW ),( , ikki wtpW ),( ,
ikik wptW ),( . Двічі застосовуємо рівності (6) і отримуємо:
Рис. 2
В.М. Статкевич
ISSN 1681–6048 System Research & Information Technologies, 2024, № 1 128
))μ()1(()1(),μ(δ 11
iikikiijijiikj bwwbwwaatt ;
))μ()1(()1(),μ(δ 11
iijijiikikiijk bwwbwwaatt .
Тоді
)()1()()1(())(μ)((μ 12
ikikiijijiikjijk wwawwapp
))()1()()1( 12
ijijiikiki wwawwa
)))(1())(1(( ijijiikikikikiijij wwawwwwaww
.))()(( ijijiikiki wwawwa
Рівність ijijikik wwww означає рівність i -х елементів k -го та
j -го рядків матриці A у класичному рівнянні стану мережі Петрі μxAT
(нагадаємо, що згідно з [2] рядкам матриці A відповідають переходи, стов-
пцям — позиції, вектор x є лічильником запусків переходів). У класичній
мережі Петрі без антисипації рівність )(μ)(μ ikjijk pp виконується завжди,
якщо обидві послідовності запусків переходів kjtt і jk tt є дозволеними; це
співвідноситься з рівностями 0 ii ba для всіх mi 1 . З уведенням ан-
тисипації за позицією множини ),μ(δ kjtt і ),μ(δ jk tt , )μ(μ 0R у загальному
випадку стають різними, більш того жодна з цих множин не обов’язково у
загальному випадку має бути підмножиною іншої [11]. Теорема 1 важлива
тим, що надає достатні умови рівності ),μ(δ),μ(δ jkkj tttt у випадку ліній-
них функцій.
Випадок 1ia для деякого i розглянемо окремо в прикладі 2.
Приклад 2. Розглянемо мережу Петрі з антисипацією за позицією та
дійсними функціями, зображену на рис. 3, де );0[11 w , );0[11 w ,
);0[12 w , );0[12 w , ));,[max(μ 12110 ww , 1a , Rb . Викорис-
таємо міркування прикладу 1.
Рівняння запуску переходу 1t з почат-
кового маркування 0μ має вигляд 01 μμ
bww
11111 μ , звідки 0μ1 , якщо ви-
конується рівність bww
11110μ . Таким
чином отримуємо нове маркування );0[μ1 . Рівняння запуску переходу
2t з маркування 1μ має вигляд bww
2121212 μμμ , воно має
розв’язки 0μ2 , якщо bww
12121μ , і не має розв’язків, якщо
bww
12121μ (перехід є дозволеним за 121μ w ). Тому нове маркування,
яке збігається з уже отриманим раніше маркуванням );0[μ1 , отримане
не класичним запуском переходу 2t , а умовним за умови bww
12121μ .
Рис. 3
Конструкції мереж Петрі із сильною антисипацією за позицією та за переходом…
Системні дослідження та інформаційні технології, 2024, № 1 129
Аналогічним чином, розглядаючи послідовність запусків переходів
12tt , отримуємо:
1) якщо виконуються обидві рівності bww
11110μ і 0μ
bww
1212 , то );0[),μ(δ),μ(δ 1221 tttt ;
2) якщо не виконується перша (відповідно, друга) рівність, то перехід
1t (відповідно, 2t ) формально є дозволеним у класичному сенсі, але
),μ(δ 1t (відповідно, ),μ(δ 2t ).
Зауваження 2. Ситуацію, коли у мережі Петрі з антисипацією за пози-
цією певний перехід t може бути дозволений у класичному сенсі, але рів-
няння його запуску не має розв’язків і ),μ(δ t , виявлено у праці [11].
ПРИКЛАДИ МЕРЕЖ ПЕТРІ З АНТИСИПАЦІЄЮ ЗА ПЕРЕХОДОМ ТА
ДІЙСНИМИ ФУНКЦІЯМИ
Розглянемо класичну мережу Петрі 0μ,,, WTP , кожен перехід якої має не
більше однієї вхідної позиції 1|| t , і введемо інше розширення:
},,{,μ,,,
10 ntt ffWTP . (7)
Як і раніше, );0[)()( TPPTW — дійсна вагова функція,
);0[:μ0 P — дійсне початкове маркування, тобто умови цілочисловос-
ті також не накладаємо. Проте на відміну від попереднього розширення (2)
функція R);0[:
it
f відповідає переходу it , ni 1 , а не позиції ip
(також будемо використовувати позначення if , якщо це не буде призводити
до конфлікту позначень). Якщо перехід t є дозволеним, то нова кількість
фішок )(μ pnew у позиції tp задовольняє рівняння запуску переходу
))(μ(),(),()(μ)(μ pfptWtpWpp newtknew , (8)
а кількість фішок у позиції tp змінюється згідно з класичним правилом
запуску переходу (1). Якщо ж позиція p є одночасно і вхідною, і вихідною
позицією для переходу t , то також використовуємо рівняння (8). Рівняння
(8) узагальнює класичне правило запуску переходу (1), але відрізняється від
рівняння (3) — тому розширення (7) відрізняється від розширення (2). Стру-
ктура мережі WTP ,, є суттєвою — факт 1|| t ураховується у рівнянні
(8). Запропоноване розширення (7) ілюструє приклад антисипації за перехо-
дом та дійсними функціями.
Приклад 3. Розглянемо мережу Петрі з антисипацією за переходом та
дійснозначними функціями, зображену на
рис. 4. Нехай переходам 1t і 2t відповідають
лінійні функції R);0[:if ( 2,1i ),
xxf )(1 , 72)(2 xxf . Якщо перехід it є
дозволеним, то нова кількість фішок )(μ 1pnew
Рис. 4
В.М. Статкевич
ISSN 1681–6048 System Research & Information Technologies, 2024, № 1 130
у вхідній позиції 1p задовольняє рівняння запуску переходу (8), окрім того,
запуск переходу 1t додає одну фішку у вихідну позицію 2p .
Під час запуску дозволеного переходу 1t з початкового маркування
)0,3(μ0 рівняння (8) набуває вигляду ))(μ(33)(μ 111 pfp newnew , звід-
ки )(μ)(μ 11 pp newnew , 0)(μ 1 pnew . Таким чином, отримуємо нове марку-
вання )1),;0([μ1 , яке, як і у прикладі 1, не є класичним маркуванням і
яке не є зліченною множиною. Із запуском дозволеного переходу 2t з марку-
вання 0μ маємо ))(μ(33)(μ 121 pfp newnew , звідки )(μ 1pnew
7)(μ2 1 pnew . Таким чином, отримуємо нове маркування )0,7(μ2 .
Під час запуску переходу 1t з маркування 1μ маємо )(μ 1pnew
)(μ3)(μ 111 pp new . Дане рівняння має розв’язки 0)(μ 1 pnew за умови
3)(μ 11 p і не має розв’язків, якщо 3)(μ 11 p ( 1t не є дозволеним у випадку
3)(μ 11 p ). Таким чином, нове маркування )2),;0([μ3 отримано не кла-
сичним запуском переходу 1t , а умовним за умови 3)(μ 11 p . За запуску
переходу 2t з маркування 1μ маємо рівняння 3)(μ)(μ 111 ppnew
7)(μ2 1 pnew , звідки )(μ10)(μ 111 ppnew . Ураховуючи обмеження
0)(μ 1 pnew , отримуємо нове маркування )1],7;0([μ4 умовним запуском
переходу 2t за умови 10)(μ3 11 p ( 2t не є дозволеним, якщо 3)(μ 11 p ).
Під час запуску з маркування 2μ переходу 1t , який є дозволеним,
отримуємо рівняння )(μ37)(μ 11 pp newnew , яке не має розв’язків. Ана-
логічно зауваженню 2 знайдена ситуація, коли перехід формально є дозво-
леним, але ),μ(δ 12 t . За запуску з маркування 2μ переходу 2t , який та-
кож є дозволеним, маємо 7)(μ237)(μ 11 pp newnew , звідки 3)(μ 1 pnew .
Таким чином, отримуємо маркування )0,3( , яке збігається з початковим.
Зазначимо, що для класичних мереж Петрі послідовність маркувань
)0,3(μ0 , )0,7(),μ(δμ 202 t , )0,3(μ),μ(δ 022 t отримати не можна: у
такому випадку ),μ(δ 22 t має дорівнювати )0,11( .
Нарешті, після запуску з маркування 4μ переходу 1t маємо рівняння
)(μ3)(μ)(μ 1141 ppp newnew , звідки отримуємо маркування 3μ умовним
запуском за умови 3)(μ 14 p , а після запуску з маркування 4μ переходу 2t
маємо рівняння 7)(μ23)(μ)(μ 1141 ppp newnew і далі )(μ 1pnew
)(μ10 14 p , звідки отримуємо нове маркування )1],7;3([μ5 умовним за-
пуском за умови 3)(μ 14 p . Із маркування 5μ отримуємо вже існуюче мар-
кування 3μ умовним запуском переходу 1t за умови 3)(μ 15 p , отримуємо те
саме маркування 5μ класичним запуском переходу 2t .
Отже, можемо побудувати граф досяжності, зображений на рис. 5. Для
спрощення запису умовних переходів на рис. 5 використаємо позначення
)(μμ 1
1 pkk , )(μμ 2
2 pkk для Νk . Для даної мережі граф нескінченний
( )1),;0([μ3 kk , )],7;0([μ 13 kk , )],7;3([μ 23 kk для Νk ), не є де-
Конструкції мереж Петрі із сильною антисипацією за позицією та за переходом…
Системні дослідження та інформаційні технології, 2024, № 1 131
ревом і не містить жодного тупикового маркування, хоча без уведення анти-
сипації за переходом класична мережа Петрі на рис. 4 мала б два тупикові
маркування )0,0( і )1,0( . Існують тільки два класичні маркування 0μ і 2μ ,
інші маркування в класичних мережах Петрі не з’являються. Також у графі
існують як класичні запуски переходів 1t , 2t , так і умовні.
Твердження 1 для мережі на рис. 1 в точності переноситься для випадку
з антисипацією за переходом та дійсними функціями, оскільки t має в точ-
ності одну вхідну позицію. Наведемо аналог теореми 1 для часткового випа-
дку мережі, зображеної на рис. 3.
Твердження 3. Нехай виконуються такі умови:
1) );0[μ0 , );0[11 w , );0[11 w , );0[12 w , );0[12 w ;
2) переходам it відповідають функції iii bxaxf )( , 1ia , Rib
( 2,1i );
3) обидві послідовності запусків переходів 21tt і 12tt є дозволеними у
поточному маркуванні )μ(μ 0R , а обидві множини }μ{),μ(δ 1221tt і
}μ{),μ(δ 2112tt є непорожніми.
Тоді виконується еквівалентність
0)μ(μ
212122
111111
2112
bwwa
bwwa
.
Доведення. За запуску переходу 1t з поточного маркування μ маємо
рівняння
11111111111111 μμ)μ(μμ bawwfww ; (9)
)(μ)1(μ 11111
1
11 bwwa .
Після запуску переходу 2t з маркування 1μ маємо рівняння
2122121211221212112 μμ)μ(μμ bawwfww ; (10)
))(μ)1(()1(μ 2121211111
1
1
1
212 bwwbwwaa .
Рис. 5
В.М. Статкевич
ISSN 1681–6048 System Research & Information Technologies, 2024, № 1 132
Аналогичним чином отримуємо
))(μ)1(()1(μ 1111121212
1
2
1
121 bwwbwwaa .
Тоді
)μ(μ 2112
)()1()()1()1(( 21212
1
211111
1
2
1
1 bwwabwwaa
))()1()()1()1( 11111
1
121212
1
2
1
1 bwwabwwaa
))(1(( 21212111111 bwwabww
)))(1( 11111221212 bwwabww
.0))()((
212122
111111
111112212121
bwwa
bwwa
bwwabwwa
Зазначимо, що в класичній мережі Петрі без антисипації, яка зображена
на рис. 3, рівність 2112 μμ виконується завжди, якщо обидві послідовності
запусків переходів 21tt і 12tt є дозволеними, це співвідноситься з рівностями
0 ii ba для всіх ni 1 . Твердження 3 важливе тим, що надає достатні
умови рівності ),μ(δ),μ(δ 1221 tttt у випадку лінійних функцій.
Також відслідкуємо умови, за яких обидві послідовності запусків пере-
ходів 21tt і 12tt є дозволеними у твердженні 3:
1) якщо 11μ w , перехід 1t є дозволеним (див. рівність (9));
2) якщо 1211111
1
11 )(μ)1(μ wbwwa , послідовність переходів
21tt є дозволеною (див. рівність (10));
3) отже, з урахуванням двох аналогічних нерівностей достатньо вимагати
);;;(maxμ 112212121112111112111211
wabwwwwabwwwww .
ВИСНОВКИ
Запропоновано дві модифікації класичних мереж Петрі: із сильною антиси-
пацією за позицією та дійсними функціями та із сильною антисипацією за
переходом та дійсними функціями. Розглянуто виконання таких мереж, ука-
зано важливі властивості, а також досліджено умови виконання рівності ма-
ркувань для послідовностей запусків переходів kjtt і jktt .
ЛІТЕРАТУРА
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. R. David and H. Alla, Discrete, Continuous, and Hybrid Petri Nets. Springer, Berlin,
Heidelberg, 2005.
4. R. David and H. Alla, “Continuous Petri Nets”, 8th European Workshop on Applica-
tion and Theory of Petri Nets, Zaragoza, Spain, pp. 275–294, 1987.
Конструкції мереж Петрі із сильною антисипацією за позицією та за переходом…
Системні дослідження та інформаційні технології, 2024, № 1 133
5. 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 Con-
trol and Information Sciences, vol. 433, Eds. C. Seatzu, M. Silva, J.H. van Schup-
pen, Springer-Verlag, London, pp. 365–386, 2013. doi: 10.1007/978-1-4471-4276-
8_18.
6. R. Rosen, Anticipatory Systems: Philosophical, Mathematical and Methodological
Foundations. Pergamon Press, 1985. doi: 10.1016/C2009-0-07769-1.
7. D. Dubois, “Incursive and hyperincursive systems, fractal machine and anticipatory
logic,” Computing Anticipatory Systems: CASYS 2000 — Fourth International Con-
ference. AIP Conference Proceedings, vol. 573, pp. 437–451, 2001. doi:
10.1063/1.1388710.
8. 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.
9. 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.
10. 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.
11. V.M. Statkevych, “A modification of Petri nets with anticipation on a position,” Sys-
tem Research & Information Technologies, no. 1, pp. 102–112, 2023. doi:
10.20535/SRIT.2308-8893.2023.1.08.
12. S.V. Lazarenko, O.S. Makarenko, Discrete systems with anticipation. National
Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Kyiv,
2020.
Надійшла 01.07.2023
INFORMATION ON THE ARTICLE
Vitalii M. Statkevych, ORCID: 0000-0001-5210-9890, Educational and Research
Institute for Applied System Analysis of the National Technical University of Ukraine
“Igor Sikorsky Kyiv Polytechnic Institute”, Ukraine, e-mail: mstatckevich@yahoo.com
DESIGNING PETRI NETS WITH STRONG PLACE AND TRANSITION
ANTICIPATION FOR REAL-VALUED FUNCTIONS / V.M. Statkevych
Abstract. We propose extending the classic Petri nets and considering D. Dubois’s
strong anticipation in two ways. We propose to add a new term into a transition rule
that contains a real-valued function of a new marking in a certain place (strong place
anticipation) or of a new marking in the input place of a certain transition (an exam-
ple of strong transition anticipation). Any integer constraints are not applied either to
the weight function or to the marking in contrast to the classic Petri nets (as in con-
tinuous Petri nets). The execution of the mentioned nets is investigated, and impor-
tant properties are stated. Several examples of reachability graphs are given, and dif-
ferences from classic Petri nets are formulated. We also investigate the conditions of
the equality of the markings, which are obtained by firing the sequences of transi-
tions kjtt and jktt .
Keywords: Petri net, strong anticipation, transition rule, reachability graph, real-
valued function, next-state function, sequence of transition firings, limit reachability.
|
| id | journaliasakpiua-article-304607 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2025-07-17T10:28:31Z |
| publishDate | 2024 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/e2/1b512cb0496652f35debf841daae30e2.pdf |
| spelling | journaliasakpiua-article-3046072024-05-23T07:09:36Z Designing Petri nets with strong place and transition anticipation for real-valued functions Конструкції мереж Петрі із сильною антисипацією за позицією та за переходом у випадку дійсних функцій Statkevych, Vitalii мережа Петрі сильна антиcипація правило запуску переходу граф досяжності цілочислова функція функція наступного стану послідовність запусків переходів гранична досяжність Petri net strong anticipation transition rule reachability graph real-valued function next-state function sequence of transition firings limit reachability We propose extending the classic Petri nets and considering D. Dubois’s strong anticipation in two ways. We propose to add a new term into a transition rule that contains a real-valued function of a new marking in a certain place (strong place anticipation) or of a new marking in the input place of a certain transition (an example of strong transition anticipation). Any integer constraints are not applied either to the weight function or to the marking in contrast to the classic Petri nets (as in continuous Petri nets). The execution of the mentioned nets is investigated, and important properties are stated. Several examples of reachability graphs are given, and differences from classic Petri nets are formulated. We also investigate the conditions of the equality of the markings, which are obtained by firing the sequences of transitions tjtk and tktj. Запропоновано розширити класичні мережі Петрі та врахувати сильну антисипацію в сенсі Д. Дюбуа двома способами. Пропонується ввести в правило запуску переходу новий доданок, який містить дійснозначну функцію від нової кількості фішок у даній позиції (сильна антисипація за позицією) та від нової кількості фішок у вхідній позиції для даного переходу (приклад сильної антисипації за переходом). На відміну від класичних мереж Петрі умови цілочисловості вагової функції та цілочисловості маркування не накладаємо аналогічно неперервним мережам Петрі. Розглянуто виконання таких мереж, указано важливі властивості, для декількох прикладів побудовано графи досяжності та сформульовано відмінності порівняно з класичними мережами Петрі. Також досліджено умови виконання рівності маркувань для послідовностей запусків переходів tjtk і tktj. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2024-03-29 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/304607 10.20535/SRIT.2308-8893.2024.1.09 System research and information technologies; No. 1 (2024); 122-133 Системные исследования и информационные технологии; № 1 (2024); 122-133 Системні дослідження та інформаційні технології; № 1 (2024); 122-133 2308-8893 1681-6048 uk https://journal.iasa.kpi.ua/article/view/304607/296434 |
| spellingShingle | мережа Петрі сильна антиcипація правило запуску переходу граф досяжності цілочислова функція функція наступного стану послідовність запусків переходів гранична досяжність Statkevych, Vitalii Конструкції мереж Петрі із сильною антисипацією за позицією та за переходом у випадку дійсних функцій |
| title | Конструкції мереж Петрі із сильною антисипацією за позицією та за переходом у випадку дійсних функцій |
| title_alt | Designing Petri nets with strong place and transition anticipation for real-valued functions |
| title_full | Конструкції мереж Петрі із сильною антисипацією за позицією та за переходом у випадку дійсних функцій |
| title_fullStr | Конструкції мереж Петрі із сильною антисипацією за позицією та за переходом у випадку дійсних функцій |
| title_full_unstemmed | Конструкції мереж Петрі із сильною антисипацією за позицією та за переходом у випадку дійсних функцій |
| title_short | Конструкції мереж Петрі із сильною антисипацією за позицією та за переходом у випадку дійсних функцій |
| title_sort | конструкції мереж петрі із сильною антисипацією за позицією та за переходом у випадку дійсних функцій |
| topic | мережа Петрі сильна антиcипація правило запуску переходу граф досяжності цілочислова функція функція наступного стану послідовність запусків переходів гранична досяжність |
| topic_facet | мережа Петрі сильна антиcипація правило запуску переходу граф досяжності цілочислова функція функція наступного стану послідовність запусків переходів гранична досяжність Petri net strong anticipation transition rule reachability graph real-valued function next-state function sequence of transition firings limit reachability |
| url | https://journal.iasa.kpi.ua/article/view/304607 |
| work_keys_str_mv | AT statkevychvitalii designingpetrinetswithstrongplaceandtransitionanticipationforrealvaluedfunctions AT statkevychvitalii konstrukcíímerežpetríízsilʹnoûantisipacíêûzapozicíêûtazaperehodomuvipadkudíjsnihfunkcíj |