Универсальная сеть Петри
Побудовано універсальну інгібіторну мережу Петрі, яка виконує довільну задану інгібіторну мережу Петрі. Граф інгібіторної мережі Петрі, її маркірування і послідовність спрацьовування переходів зашифровано як десять невід’ємних цілих скалярних змінних, поданих відповідними позиціями універсальної мер...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2012 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84122 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Универсальная сеть Петри / Д.А. Зайцев // Кибернетика и системный анализ. — 2012. — Т. 48, № 4. — С. 24-39. — Бібліогр.: 10 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859904874677796864 |
|---|---|
| author | Зайцев, Д.А. |
| author_facet | Зайцев, Д.А. |
| citation_txt | Универсальная сеть Петри / Д.А. Зайцев // Кибернетика и системный анализ. — 2012. — Т. 48, № 4. — С. 24-39. — Бібліогр.: 10 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Побудовано універсальну інгібіторну мережу Петрі, яка виконує довільну задану інгібіторну мережу Петрі. Граф інгібіторної мережі Петрі, її маркірування і послідовність спрацьовування переходів зашифровано як десять невід’ємних цілих скалярних змінних, поданих відповідними позиціями універсальної мережі. За рівнянням станів побудовано алгоритм виконання інгібіторної мережі, який використовує лише вказані скалярні змінні. Алгоритм закодовано інгібіторною мережею Петрі. Використано підмережі, які реалізують арифметичні і логічні операції, копіювання значень змінних.
A universal inhibitor Petri net is constructed, which executes an arbitrary given inhibitor Petri net. The inhibitor Petri net graph, its marking, and transition firing sequence are encoded as 10 scalar nonnegative integer variables and are represented by the corresponding places of the universal net. An algorithm of inhibitor net execution that uses only these scalar variables is developed based on the state equation and is encoded by the universal inhibitor Petri net. Subnets that implement arithmetic, comparison, and copying operations are employed.
|
| first_indexed | 2025-12-07T15:59:19Z |
| format | Article |
| fulltext |
ÓÄÊ 519.6, 510.51
Ä.À. ÇÀÉÖÅÂ
ÓÍÈÂÅÐÑÀËÜÍÀß ÑÅÒÜ ÏÅÒÐÈ
Êëþ÷åâûå ñëîâà: óíèâåðñàëüíàÿ èíãèáèòîðíàÿ ñåòü Ïåòðè, óíèâåðñàëüíàÿ
ìàøèíà Òüþðèíãà, àëãîðèòì, øèôðîâàíèå, ïîòîê óïðàâëåíèÿ.
ÂÂÅÄÅÍÈÅ
Èçâåñòíî, ÷òî èíãèáèòîðíûå, ñèíõðîííûå, ïðèîðèòåòíûå è äðóãèå ðàñøèðåí-
íûå êëàññû ñåòåé Ïåòðè ÿâëÿþòñÿ óíèâåðñàëüíîé àëãîðèòìè÷åñêîé ñèñòåìîé
[1, 2]. Äëÿ òàêèõ àëãîðèòìè÷åñêèõ ñèñòåì, êàê ìàøèíû Òüþðèíãà èçâåñòíû
ïðèìåðû ïîñòðîåíèÿ óíèâåðñàëüíîé ìàøèíû [3]. Â ýòîé ñâÿçè îïðåäåëåííûé
èíòåðåñ ïðåäñòàâëÿåò ïîñòðîåíèå óíèâåðñàëüíîé ñåòè Ïåòðè, êîòîðàÿ ìîæåò
âûïîëíÿòü ïðîèçâîëüíóþ çàäàííóþ ñåòü Ïåòðè. Ýòî ñîñòàâëÿåò öåëü íàñòîÿ-
ùåé ñòàòüè. Ïðåäâàðèòåëüíûé âàðèàíò ðàáîòû áûë ïðåäñòàâëåí íà 17-ì Íå-
ìåöêîì ñåìèíàðå ïî àëãîðèòìàì è ïðîãðàììàì äëÿ ñåòåé Ïåòðè [4].
Ïîìèìî ïîáî÷íûõ ðåçóëüòàòîâ ïî êîäèðîâàíèþ ñåòåé Ïåòðè öåëûìè ÷èñëà-
ìè, àíàëîãè÷íûõ îòìå÷åííûì â [9] äëÿ óíèâåðñàëüíûõ ìàøèí Òüþðèíãà, îñíîâ-
íîé ìîòèâàöèåé ïîñòðîåíèÿ óíèâåðñàëüíîé ñåòè Ïåòðè ÿâëÿåòñÿ òåíäåíöèÿ ïðè-
ìåíåíèÿ ñåòåé Ïåòðè íå òîëüêî äëÿ ìîäåëèðîâàíèÿ, íî è êàê ãðàôè÷åñêîé îñíî-
âû ïàðàëëåëüíûõ àñèíõðîííûõ ÿçûêîâ ïðîãðàììèðîâàíèÿ.  ýòîì ñëó÷àå
óíèâåðñàëüíàÿ ñåòü Ïåòðè ïðåäñòàâëÿåò ïðîòîòèï ïðîöåññîðà, ïðåäíàçíà÷åííîãî
äëÿ âûïîëíåíèÿ ïðîãðàìì, íàïèñàííûõ íà ÿçûêå ñåòåé Ïåòðè.
Âîçìîæíî òàêæå ïðèìåíåíèå ìîäèôèêàöèé óíèâåðñàëüíîé ñåòè äëÿ àíàëèçà
ñâîéñòâ ñåòåé Ïåòðè (òàêèõ êàê îãðàíè÷åííîñòü, êîíñåðâàòèâíîñòü, æèâîñòü) íà
îñíîâå ñîõðàíåíèÿ â çàøèôðîâàííîì âèäå íå òîëüêî òåêóùåé òðàññû çàïóñêà ïå-
ðåõîäîâ, à âñåãî ãðàôà äîñòèæèìûõ (ïîêðûâàþùèõ) ìàðêèðîâîê.
1. ÊÎÍÖÅÏÖÈß ÓÍÈÂÅÐÑÀËÜÍÎÉ ÑÅÒÈ ÏÅÒÐÈ
Ïîñòðîåíèå óíèâåðñàëüíîé ñåòè âûïîëíèì â êëàññå èíãèáèòîðíûõ ñåòåé Ïåò-
ðè [1, 2]. Ñîîòâåòñòâóþùóþ óíèâåðñàëüíóþ èíãèáèòîðíóþ ñåòü Ïåòðè îáîçíà-
÷èì UIPN. Ââèäó íåäåòåðìèíèðîâàííîãî õàðàêòåðà äèíàìèêè ñåòè Ïåòðè íàè-
áîëåå áëèçêèì àíàëîãîì ÿâëÿþòñÿ íåäåòåðìèíèðîâàííûå ìàøèíû Òþðèíãà [3].
Ïîñêîëüêó èíòåðåñ ïðåäñòàâëÿåò ïîñòðîåíèå óíèâåðñàëüíîé ñåòè UIPN
ñ ôèêñèðîâàííîé ñòðóêòóðîé, åäèíñòâåííûì ñðåäñòâîì ïðåäñòàâëåíèÿ âõîäíîé è
âûõîäíîé èíôîðìàöèè ÿâëÿåòñÿ ìàðêèðîâêà ôèêñèðîâàííîãî ÷èñëà îïðåäåëåí-
íûõ ïîçèöèé ñåòè UIPN. Ïîýòîìó íåîáõîäèìî çàäàòü íåêîòîðûå ïðàâèëà âçàèì-
íî îäíîçíà÷íîãî øèôðîâàíèÿ ãðàôà ñåòè Ïåòðè è åå ìàðêèðîâêè ôèêñèðîâàííûì
÷èñëîì öåëûõ íåîòðèöàòåëüíûõ ÷èñåë. Ïóñòü çàäàíû ñîîòâåòñòâóþùèå ïðàâèëà
øèôðîâàíèÿ, à òàêæå sXIPN — øèôð ãðàôà ñåòè Ïåòðè XIPN è sQXIPN — øèôð
ìàðêèðîâêè QXIPN.
Êîíöåïöèÿ äîñòèæèìîñòè ìàðêèðîâêè â ñåòè Ïåòðè ïîäðàçóìåâàåò íàëè÷èå
ñîîòâåòñòâóþùåé äîïóñòèìîé ïîñëåäîâàòåëüíîñòè ñðàáàòûâàíèé ïåðåõîäîâ [1, 2].
Îäíàêî èñïîëüçîâàíèå ëèøü ìàðêèðîâîê QXIPN â îïðåäåëåíèè UIPN íå ãàðàí-
òèðóåò ïîëó÷åíèÿ âñåõ äîïóñòèìûõ ïîñëåäîâàòåëüíîñòåé ñðàáàòûâàíèÿ ïåðåõî-
äîâ ñåòè XIPN. Ïóñòü çàäàíû òàêæå ïðàâèëà øèôðîâàíèÿ ïîñëåäîâàòåëüíîñòåé
ñðàáàòûâàíèÿ ïåðåõîäîâ è sZQXIPN — øèôð äîïóñòèìîé ïîñëåäîâàòåëüíîñòè
24 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4
© Ä.À. Çàéöåâ, 2012
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4 25
ñðàáàòûâàíèÿ ïåðåõîäîâ ZQXIPN, ïåðåâîäÿùåé ñåòü Ïåòðè XIPN èç ìàðêèðîâêè
Q0XIPN â ìàðêèðîâêó QXIPN.
Îïðåäåëåíèå 1. Ñåòü Ïåòðè UIPN ÿâëÿåòñÿ óíèâåðñàëüíîé èíãèáèòîðíîé
ñåòüþ Ïåòðè òîãäà è òîëüêî òîãäà, êîãäà äëÿ ïðîèçâîëüíîé çàäàííîé èíãèáèòîð-
íîé ñåòè XIPN è åå íà÷àëüíîé ìàðêèðîâêè Q0XIPN ñåòü UIPN îñòàíàâëèâàåòñÿ â
ìàðêèðîâêå (sQXIPN, sZQXIPN) òàêîé, ÷òî ìàðêèðîâêà QXIPN äîñòèæèìà
â XIPN ñ ïîìîùüþ ïîñëåäîâàòåëüíîñòè ñðàáàòûâàíèé ïåðåõîäîâ ZQXIPN è ëþ-
áàÿ ìàðêèðîâêà (sQXIPN, sZQXIPN), â êîòîðîé îñòàíàâëèâàåòñÿ UIPN, ÿâëÿåòñÿ
øèôðîì ìàðêèðîâêè QXIPN, äîñòèæèìîé â XIPN èç íà÷àëüíîé ìàðêèðîâêè
Q0XIPN ñ ïîìîùüþ ïîñëåäîâàòåëüíîñòè ZQXIPN.
Òðåáîâàíèå âîçìîæíîñòè îñòàíîâà UIPN äàæå â ñëó÷àå íå òóïèêîâîé ìàðêèðîâ-
êè QXIPN ñåòè XIPN ñâÿçàíî ñ îáåñïå÷åíèåì ïðîâåðêè (íàáëþäåíèÿ) ëþáîé äîñòè-
æèìîé ìàðêèðîâêè (è ïîñëåäîâàòåëüíîñòè ñðàáàòûâàíèÿ ïåðåõîäîâ) è àáñòðàãèðîâà-
íèåì îò ðåàëèçàöèè UIPN, â ïðîòèâíîì ñëó÷àå íåîáõîäèìî äîáàâèòü îãðàíè÷åíèÿ
äëÿ èñêëþ÷åíèÿ èç ðàññìîòðåíèÿ ïðîìåæóòî÷íûõ ìàðêèðîâîê ñåòè UIPN.
2. ÔÎÐÌÀËÜÍÎÅ ÏÐÅÄÑÒÀÂËÅÍÈÅ ÈÍÃÈÁÈÒÎÐÍÎÉ ÑÅÒÈ ÏÅÒÐÈ
Ãðàô èíãèáèòîðíîé ñåòè Ïåòðè [1, 2] — ýòî ÷åòâåðêà G P T B D� ( , , , ) , ãäå
P p pm� { }1, ,� — êîíå÷íîå ìíîæåñòâî âåðøèí, íàçûâàåìûõ ïîçèöèÿìè;
T t tn� { }1, ,� — êîíå÷íîå ìíîæåñòâî âåðøèí, íàçûâàåìûõ ïåðåõîäàìè; îòî-
áðàæåíèÿ B P T: � � � �� { }1 è D T P: � � � çàäàþò âõîäÿùèå è èñõîäÿùèå
äóãè ïåðåõîäîâ ñîîòâåòñòâåííî è èõ êðàòíîñòü, � — ìíîæåñòâî öåëûõ íåîò-
ðèöàòåëüíûõ ÷èñåë; íóëåâîå çíà÷åíèå îòîáðàæåíèé B D, îçíà÷àåò îòñóòñòâèå
äóãè, íåíóëåâîå — êðàòíîñòü äóãè, ñïåöèàëüíîå çíà÷åíèå –1 îçíà÷àåò èíãèáè-
òîðíóþ äóãó. Îòîáðàæåíèÿ ìîãóò áûòü ïðåäñòàâëåíû ñîîòâåòñòâóþùèìè ìàò-
ðèöàìè: B b b B p ti j i j j i� �| | | | , ( , ), , è D d d D t pi j i j i j� �| | | | , ( , ), , .
Ñîñòîÿíèå ñåòè íàçûâàþò ìàðêèðîâêîé è ïðåäñòàâëÿþò îòîáðàæåíèåì
Q P: � �, çàäàþùèì êîëè÷åñòâî äèíàìè÷åñêèõ ýëåìåíòîâ — ôèøåê â ïîçèöèÿõ
ñåòè. Èíãèáèòîðíàÿ ñåòü Ïåòðè [1, 2] — ýòî ïàðà N G Q� ( , )0 , ãäå G — ãðàô ñåòè,
à Q0 — åå íà÷àëüíàÿ ìàðêèðîâêà. Ìàðêèðîâêà ìîæåò áûòü ïðåäñòàâëåíà ñîîòâåò-
ñòâóþùèì âåêòîðîì: Q q q Q pj j j� �| | | | , ( ). Òàêèì îáðàçîì, èíãèáèòîðíàÿ ñåòü
Ïåòðè çàäàíà ïàðîé ÷èñåë, ïàðîé ìàòðèö è âåêòîðîì: N m n B D Q� ( , , , , )0 .
Ãðàôè÷åñêè ïîçèöèè ïðåäñòàâëÿþò îêðóæíîñòÿìè, ïåðåõîäû — ïðÿìî-
óãîëüíèêàìè, ôèøêè èçîáðàæàþò òî÷êàìè, íàõîäÿùèìèñÿ âíóòðè ïîçèöèé. Åñëè
çíà÷åíèå ìàðêèðîâêè ïîçèöèè âåëèêî, òî âíóòðè ïîçèöèè çàïèñûâàþò ÷èñëî,
ðàâíîå êîëè÷åñòâó ôèøåê. Äëÿ ãðàôè÷åñêîãî ïðåäñòàâëåíèÿ èíãèáèòîðíîé äóãè
èñïîëüçóþò ïîëûé êðóã íà åå êîíöå. Èíãèáèòîðíûå äóãè ïðîâåðÿþò ìàðêèðîâêó
ïîçèöèè íà ðàâåíñòâî íóëþ. Äóãè ñ çàêðàøåííûì êðóãîì íà êîíöå ÿâëÿþòñÿ
âñïîìîãàòåëüíûì îáîçíà÷åíèåì äëÿ ïàðû äóã ïðîòèâîïîëîæíîãî íàïðàâëåíèÿ
ñ îäèíàêîâîé êðàòíîñòüþ. Îíè èñïîëüçóþòñÿ äëÿ ïðîâåðêè íåíóëåâîé ìàðêèðîâ-
êè ïîçèöèè. Ïðèìåðû èíãèáèòîðíûõ ñåòåé äàíû â ïðèëîæåíèè À.
Äèíàìèêà èíãèáèòîðíîé ñåòè ïðåäñòàâëÿåò ñîáîé ïîøàãîâûé ïðîöåññ èçìå-
íåíèÿ åå ìàðêèðîâêè â ðåçóëüòàòå ñðàáàòûâàíèÿ ïåðåõîäîâ [1, 2] è ìîæåò áûòü
ôîðìàëüíî îïèñàíà ñëåäóþùåé ñèñòåìîé:
q q x b d j m
u t y b
j
k
j
k
l j l j
i
j m
i j
� � � �
� �
�
�
�
1
1
1( ) , , ,
( ) ( ( )
, ,
,
, ( )) ( ( ) ( )), , ,
( ) ,
, ,q y b q b i n
u t l
j
k
i j j
k
i j
l
� �� �
�
� �
1 10 1
1 1
1 2
0
0 1
0 0
1 1
, ,
, , ,
( )
, ,
, ,
( )
, ,
,
n
k
x b
b b
b
y b
b
b
�
�
� �
�
�
�
� �
�
.
�
�
�
�
�
�
�
�
�
�
�
�
(1)
Ïåðâàÿ ñòðîêà ñèñòåìû (1) îïèñûâàåò èçìåíåíèå ìàðêèðîâêè ïðè ñðàáàòûâà-
íèè ïåðåõîäà tl ; ôóíêöèÿ u ti( ) âî âòîðîé ñòðîêå ïðåäñòàâëÿåò óñëîâèå âîçáóæäåíèÿ
ïåðåõîäà ti íà òåêóùåì øàãå k; òðåòüÿ ñòðîêà çàäàåò íåäåòåðìèíèðîâàííûé âûáîð
ñðàáàòûâàþùåãî ïåðåõîäà tl èç ìíîæåñòâà âîçáóæäåííûõ; ÷åòâåðòàÿ ñòðîêà çàäàåò
ïîðÿäîê ñëåäîâàíèÿ øàãîâ; âñïîìîãàòåëüíûå îòîáðàæåíèÿ x è y ñëóæàò äëÿ çàäàíèÿ
äåêðåìåíòà ìàðêèðîâêè è ðàñïîçíàâàíèÿ èíãèáèòîðíîé äóãè ñîîòâåòñòâåííî.
3. ØÈÔÐÎÂÀÍÈÅ ÈÍÃÈÁÈÒÎÐÍÎÉ ÑÅÒÈ ÏÅÒÐÈ
Ïðåäñòàâèì øèôð ãðàôà èíãèáèòîðíîé ñåòè Ïåòðè, åå òåêóùóþ ìàðêèðîâêó è
ñîîòâåòñòâóþùóþ ïîñëåäîâàòåëüíîñòü ñðàáàòûâàíèÿ ïåðåõîäîâ â âèäå ìàðêè-
ðîâêè äåñÿòè âûäåëåííûõ ïîçèöèé óíèâåðñàëüíîé ñåòè UIPN (ðèñ. 1). Ïðèìå-
ðû øèôðîâàíèÿ ñåòåé ïðèâåäåíû â ïðèëîæåíèè Á.
3.1. Øèôðîâàíèå âåêòîðà. Ïóñòü Q — íåêîòîðûé âåêòîð (ñòðîêà), ñîäåðæà-
ùèé m öåëûõ íåîòðèöàòåëüíûõ ýëåìåíòîâ. Ïðåäïîëàãàåì, ÷òî èíäåêñàöèÿ ýëå-
ìåíòîâ íà÷èíàåòñÿ ñ íóëÿ. Ïóñòü òàêæå íàéäåíî çíà÷åíèå r q
j
j� �max 1.
Ïðåäñòàâèì ôóíêöèþ øèôðîâàíèÿ âåêòîðà:
s Q r qj
j
j
m
� � �
�
�
��( )
0
1
.
Óòâåðæäåíèå 1. Ôóíêöèÿ øèôðîâàíèÿ âåêòîðà ÿâëÿåòñÿ èíúåêòèâíîé.
Ñîîòâåòñòâóþùàÿ ôóíêöèÿ äåøèôðîâàíèÿ ìîæåò áûòü ïðåäñòàâëåíà êàê
q s j s r ri
j� ��( , ) ( )div mod .
Óêàçàííîå øèôðîâàíèå ÿâëÿåòñÿ ôîðìîé ïðåäñòàâëåíèÿ ÷èñåë â ïîçèöèîííîé
ñèñòåìå ñ÷èñëåíèÿ ñ îñíîâàíèåì r.
Øèôðîâàíèå ìîæåò áûòü âûïîëíåíî ðåêóððåíòíî:
s s r q s q j mj j m j m� � � � � �� � � �1 1 0 1 1 1, , , , (2)
ãäå øèôð âåêòîðà Q ðàâåí s sm� �1.
Äåøèôðîâàíèå ìîæåò áûòü òàêæå âûïîëíåíî ðåêóððåíòíî:
q s r s s r s s j mj m j m j m j m� � � � �� � � � � � � �1 1 1 1 1 0 1mod div, , , ,( ) . (3)
3.2. Øèôðîâàíèå ìàòðèöû. Ïóñòü A — íåêîòîðàÿ n m� -ìàòðèöà ñ öåëûìè
íåîòðèöàòåëüíûìè çíà÷åíèÿìè ýëåìåíòîâ. Ïðåäïîëàãàåì, ÷òî èíäåêñàöèÿ ýëå-
ìåíòîâ íà÷èíàåòñÿ ñ íóëÿ. Ïóñòü òàêæå íàéäåíî çíà÷åíèå
r a
i j
i j� �max
,
, 1 .
Ïðè øèôðîâàíèè áóäåì ïðåäñòàâëÿòü ìàòðèöó êàê âåêòîð ñ ðàçëîæåíèåì ïî
ñòðîêàì. Òîãäà ìàòðèöà A ìîæåò áûòü çàøèôðîâàíà êàê
s A r am i j
i j
j
m
i
n
� � �� �
��
���( ) ( )
,
00
.
26 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4
Ðèñ. 1. Ïðåäñòàâëåíèå øèôðîâ ñåòè Ïåòðè è ïîñëåäîâàòåëüíîñòè ñðàáàòûâàíèÿ ïåðåõîäîâ
Óòâåðæäåíèå 2. Ôóíêöèÿ øèôðîâàíèÿ ìàòðèöû ÿâëÿåòñÿ èíúåêòèâíîé.
Ñîîòâåòñòâóþùàÿ ôóíêöèÿ äåøèôðîâàíèÿ ìîæåò áûòü ïðåäñòàâëåíà êàê
a A i j s r ri j
m i j
,
( )( , , ) ( )� � � �
� div mod .
Øèôðîâàíèå ìîæåò áûòü âûïîëíåíî ðåêóððåíòíî:
s s r a s ai j n m� �� � � �� � �1 0 1 1, ,, ,
� � �� � � � �1 1, , ,n m i n j ndiv mod , (4)
ãäå øèôð ìàòðèöû A ðàâåí s sn m� � �1.
Äåøèôðîâàíèå ìîæåò áûòü òàêæå âûïîëíåíî ðåêóððåíòíî:
a s r s s r si j n m n m n m n m, ( ), ,� �� � � � � � � � � � � �1 1 1 1 1� � �mod div � s,
� � �� � � � �0 1, , ,n m i n j ndiv mod . (5)
3.3. Øèôðîâàíèå ãðàôà èíãèáèòîðíîé ñåòè Ïåòðè. Ãðàô ïðåäñòàâëåí ïà-
ðîé ìàòðèö B è D, ÿâëÿþùèõñÿ ñîîòâåòñòâåííî ìàòðèöàìè âõîäÿùèõ è èñõîäÿ-
ùèõ äóã ïåðåõîäîâ. Îáû÷íî íóëåâîå çíà÷åíèå ýëåìåíòà ìàòðèöû óêàçûâàåò íà
îòñóòñòâèå ñîîòâåòñòâóþùåé äóãè, íåíóëåâîå — íà åå êðàòíîñòü. Ïðåäñòàâëåíèå
èíãèáèòîðíûõ äóã ìàòðèöû B òðåáóåò ñïåöèàëüíûõ ñîãëàøåíèé, ÷òîáû èçáåæàòü
èñïîëüçîâàíèÿ îòðèöàòåëüíûõ çíà÷åíèé. Ïóñòü k — êðàòíîñòü äóãè. Òîãäà äëÿ åå
ïðåäñòàâëåíèÿ áóäåì èñïîëüçîâàòü çíà÷åíèå k �1 . Çíà÷åíèå, ðàâíîå åäèíèöå, çà-
ðåçåðâèðóåì äëÿ ïðåäñòàâëåíèÿ èíãèáèòîðíîé äóãè.
Öåëåñîîáðàçíî ðàçäåëüíîå øèôðîâàíèå â ñîîòâåòñòâèè ñ (4) è õðàíåíèå â îò-
äåëüíûõ ïîçèöèÿõ øèôðîâ ìàòðèö B è D, à òàêæå ñîîòâåòñòâóþùèõ çíà÷åíèé r.
Äëÿ õðàíåíèÿ çàøèôðîâàííîãî ãðàôà ñåòè Ïåòðè áóäåì èñïîëüçîâàòü øåñòü ïî-
çèöèé ñ èìåíàìè m n sB rB sD rD, , , , , , èçîáðàæåííûõ íà ðèñ. 1, ìàðêèðîâêà êîòî-
ðûõ ñîäåðæèò çíà÷åíèÿ m n sB rB sD rD, , , , , ñîîòâåòñòâåííî.
3.4. Øèôðîâàíèå ìàðêèðîâêè. Ìàðêèðîâêà ñåòè Ïåòðè, ñîäåðæàùåé m ïî-
çèöèé, çàäàíà âåêòîðîì Q ðàçìåðà m ñ öåëûìè íåîòðèöàòåëüíûìè êîìïîíåíòàìè
q Q pj j� ( ) . Äëÿ õðàíåíèÿ çàøèôðîâàííîé â ñîîòâåòñòâèè ñ (2) ìàðêèðîâêè áó-
äåì èñïîëüçîâàòü òðè ïîçèöèè ñ èìåíàìè m sQ rQ, , , èçîáðàæåííûå íà ðèñ. 1, ìàð-
êèðîâêà êîòîðûõ ñîäåðæèò çíà÷åíèÿ m sQ rQ, , ñîîòâåòñòâåííî.
3.5. Øèôðîâàíèå ïîñëåäîâàòåëüíîñòè ñðàáàòûâàíèÿ ïåðåõîäîâ. Ïîñëå-
äîâàòåëüíîñòü ñðàáàòûâàíèÿ ïåðåõîäîâ Z äëèíû k ìîæåò áûòü ïðåäñòàâëåíà âåê-
òîðîì Z ðàçìåðà k ñ öåëûìè íåîòðèöàòåëüíûìè êîìïîíåíòàìè z lj � , ãäå l — íî-
ìåð ïåðåõîäà tl , ñðàáàòûâàþùåãî íà øàãå j. Äëÿ õðàíåíèÿ çàøèôðîâàííîé â ñî-
îòâåòñòâèè ñ (2) ïîñëåäîâàòåëüíîñòè áóäåì èñïîëüçîâàòü òðè ïîçèöèè ñ èìåíàìè
k sZ n, , , èçîáðàæåííûå íà ðèñ. 1, ìàðêèðîâêà êîòîðûõ ñîäåðæèò çíà÷åíèÿ k sZ n, ,
ñîîòâåòñòâåííî.
Îòìåòèì, ÷òî ïîçèöèè m n, èñïîëüçóþòñÿ â êà÷åñòâå ïàðàìåòðîâ äëÿ øèôðî-
âàíèÿ (äåøèôðîâàíèÿ) ãðàôà ñåòè Ïåòðè, ìàðêèðîâêè è ïîñëåäîâàòåëüíîñòè
ñðàáàòûâàíèÿ ïåðåõîäîâ.
3.6. Øèôðîâàíèå ìíîæåñòâà âîçáóæäåííûõ ïåðåõîäîâ. Ìíîæåñòâî âîç-
áóæäåííûõ ïåðåõîäîâ ñåòè Ïåòðè ÿâëÿåòñÿ âñïîìîãàòåëüíîé èíôîðìàöèåé äëÿ
íåäåòåðìèíèðîâàííîãî âûáîðà ñðàáàòûâàþùåãî ïåðåõîäà t ul l( )�1 íà òåêóùåì
øàãå. Äëÿ ïðåäñòàâëåíèÿ ìíîæåñòâà âîçáóæäåííûõ ïåðåõîäîâ èñïîëüçóåì âåê-
òîð u äëèíû n, êîìïîíåíòàìè êîòîðîãî ÿâëÿþòñÿ èíäèêàòîðû âîçáóæäåíèÿ ui ñî-
îòâåòñòâóþùèõ ïåðåõîäîâ t i ni , ,� �0 1, âû÷èñëåííûå â ñîîòâåòñòâèè ñ (1). Òîãäà
äëÿ øèôðîâàíèÿ u ïðèìåíèì ïðàâèëà øèôðîâàíèÿ âåêòîðà (2) ïðè r � 2 .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4 27
4. ÀËÃÎÐÈÒÌ ÂÛÏÎËÍÅÍÈß ÈÍÃÈÁÈÒÎÐÍÎÉ ÑÅÒÈ ÏÅÒÐÈ
Ïî ñèñòåìå (1) â ñîîòâåòñòâèè ñ âûáðàííûì ñïîñîáîì øèôðîâàíèÿ ãðàôà,
ìàðêèðîâêè è ïîñëåäîâàòåëüíîñòè ñðàáàòûâàíèÿ ïåðåõîäîâ ñåòè Ïåòðè ïîñòðî-
èì àëãîðèòì AUIPN âûïîëíåíèÿ èíãèáèòîðíîé ñåòè Ïåòðè íà Ñè-ïîäîáíîì
ïñåâäîÿçûêå:
void AUIPN()
{
uint u, l;
inputXIPN();
k=1; sZ=0;
while(NonDeterministic())
{
CheckFire(&u);
if(u==0) goto out;
PickFire(u, &l);
Fire(l);
MUL_ADD(&sZ,n,l-1);
k++;
}
out:outputXIPN();
}
 àëãîðèòìå èñïîëüçîâàíû ñëåäóþùèå ïåðåìåííûå è ïðîöåäóðû: u — øèôð
èíäèêàòîðà âîçáóæäåííûõ ïåðåõîäîâ, l — íîìåð ñðàáàòûâàþùåãî ïåðåõîäà,
k — íîìåð øàãà; CheckFire — ïðîâåðêà óñëîâèé âîçáóæäåíèÿ ïåðåõîäîâ,
PickFire — âûáîð ñðàáàòûâàþùåãî ïåðåõîäà, Fire — ñðàáàòûâàíèå ïåðåõîäà;
NonDeterministic — íåäåòåðìèíèðîâàííûé âûáîð ÷èñëà èç ìíîæåñòâà {0, 1}.
Ïðåäñòàâèì àëãîðèòìû âñïîìîãàòåëüíûõ ïðîöåäóð MUL_ADD, MOD_DIV, ðåàëèçó-
þùèõ ðåêóððåíòíîå øèôðîâàíèå/äåøèôðîâàíèå â ñîîòâåòñòâèè ñ (2), (3):
void MUL_ADD(&x,y,z)
{
(*x) = (*x) * y + z;
}
void MOD_DIV(&m,&x,y)
{
(*m) = (*x) mod y;
(*x) = (*x) div y;
}
Àëãîðèòì ïðîöåäóðû CheckFire:
void CheckFire(uint *u)
{
uint i, j, qj, bij, ui, uij;
uint sB1, sQ1;
sB1=sB; &u=0;
for(i=n; i>0; i--)
{
sQ1=sQ;
ui=1;
for(j=m; j>0; j--)
28 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4
{
MOD_DIV(&qj,&sQ1,rQ);
MOD_DIV(&bij,&sB1,rB);
uij=1;
if(bij==0) continue;
bij--;
if(bij==0) uij=(qj==0);
else uij=(qj>=bij);
ui=ui && uij;
}
MUL_ADD(&u,2,ui);
}
}
Ëåììà 1. Àëãîðèòì CheckFire ôîðìèðóåò ìíîæåñòâî ïåðåõîäîâ, âîçáóæ-
äåííûõ â òåêóùåé ìàðêèðîâêå.
Äîêàçàòåëüñòâî. Àëãîðèòì ïðåäñòàâëÿåò ïîñëåäîâàòåëüíîå âû÷èñëåíèå êîì-
ïîíåíòîâ âåêòîðà u â ñîîòâåòñòâèè ñî âòîðîé ñòðîêîé ñèñòåìû (1) è åãî îäíîâðå-
ìåííîå øèôðîâàíèå (2) â ïåðåìåííîé u ïîñëå âû÷èñëåíèÿ òåêóùåé êîìïîíåíòû
â ïåðåìåííîé ui. Öèêë ïî ïåðåìåííîé i çàäàåò ïåðåáîð âñåõ ïåðåõîäîâ, âëîæåí-
íûé öèêë ïî ïåðåìåííîé j çàäàåò ïåðåáîð âñåõ ïîçèöèé äëÿ òåêóùåãî ïåðåõîäà.
Ïîðÿäîê ïîñëåäîâàòåëüíîãî äåøèôðîâàíèÿ ýëåìåíòîâ âåêòîðà Q è ìàòðèöû B ñî-
îòâåòñòâóåò ïîðÿäêó èçìåíåíèÿ èíäåêñîâ öèêëîâ â ñîîòâåòñòâèè ñ (3) è (5). �
Àëãîðèòì ïðîöåäóðû PickFire:
void PickFire(uint u, uint *l)
{
uint ui, i;
i=0;
while(u>0)
{
MOD_DIV(&ui,&u,2);
i++;
if(ui==0) continue;
if(NonDeterministic()) goto out;
}
out:*l=i;
}
Ëåììà 2. Àëãîðèòì PickFire âûïîëíÿåò âûáîð ïðîèçâîëüíîãî ñðàáàòûâàþ-
ùåãî ïåðåõîäà èç ìíîæåñòâà âîçáóæäåííûõ.
Äîêàçàòåëüñòâî. Óñëîâèå âûáîðà ñðàáàòûâàþùåãî ïåðåõîäà ñîîòâåòñòâóåò
òðåòüåé ñòðîêå ñèñòåìû (1) è ïîðÿäêó äåøèôðîâàíèÿ âåêòîðà u â ñîîòâåòñòâèè
ñ (3). Äëÿ íåäåòåðìèíèðîâàííîãî âûáîðà âîçáóæäåííîãî ïåðåõîäà èñïîëüçîâàíà
ôóíêöèÿ NonDeterministic äëÿ âûõîäà èç öèêëà. Óñëîâèå u � 0 îáåñïå÷èâàåò çà-
âåðøåíèå öèêëà ïîñëå îáðàáîòêè ïîñëåäíåãî âîçáóæäåííîãî ïåðåõîäà, êîòîðûé
áóäåò âûáðàí äëÿ ñðàáàòûâàíèÿ. �
Àëãîðèòì ïðîöåäóðû Fire:
void Fire(uint l)
{
uint rQ1, maxQ1, shift, qj, bij, dij, j;
uint sB1, sD1, sQ1;
sB1=sB; sD1=sD; sQ1=0; rQ1=rQ+rD-1; maxQ1=0;
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4 29
shift=(n-l)*m;
while(shift--)
{
MOD_DIV(&b,&sB1,rB);
MOD_DIV(&d,&sD1,rD);
}
for(j=m; j>0; j--)
{
MOD_DIV(&qj,&sQ,rQ);
MOD_DIV(&bij,&sB1,rB);
if(bij>0) bij--;
MOD_DIV(&dij,&sD1,rD);
qj=qj-bij+dij;
maxQ1=MAX(qj,maxQ1);
MUL_ADD(&sQ1,rQ1,qj);
}
sQ=0; rQ=maxQ1+1;
for(j=m; j>0; j--)
{
MOD_DIV(&qj,&sQ1,rQ1);
MUL_ADD(&sQ,rQ,qj);
}
}
Ëåììà 3. Àëãîðèòì Fire ðåàëèçóåò èçìåíåíèå ìàðêèðîâêè â ðåçóëüòàòå ñðà-
áàòûâàíèÿ óêàçàííîãî ïåðåõîäà.
Äîêàçàòåëüñòâî. Àëãîðèòì ðåàëèçóåò ïåðåâû÷èñëåíèå ìàðêèðîâêè â ñîîò-
âåòñòâèè ñ ïåðâîé ñòðîêîé ñèñòåìû (1) è âûáðàííûì ïîðÿäêîì äåøèôðîâàíèÿ
ìàòðèö B D, è âåêòîðà Q â ñîîòâåòñòâèè ñ (5) è (3). Çíà÷åíèå ïåðåìåííîé shift
ñîîòâåòñòâóåò êîëè÷åñòâó ïðîïóñêàåìûõ ýëåìåíòîâ äëÿ ïîçèöèîíèðîâàíèÿ íà íà-
÷àëî ñòðîêè ñðàáàòûâàþùåãî ïåðåõîäà ñ íîìåðîì l. Çàòåì â ïåðâîì öèêëå ïî ïå-
ðåìåííîé j âûïîëíÿåòñÿ ïðåäâàðèòåëüíîå ïåðåâû÷èñëåíèå øèôðà (2) ìàðêèðîâ-
êè â ïåðåìåííîé sQ1. Ïðè ýòîì èñïîëüçîâàíî çíà÷åíèå rQ1, îáåñïå÷èâàþùåå
õðàíåíèå íàèáîëüøåãî äîïóñòèìîãî çíà÷åíèÿ ýëåìåíòà íîâîé ìàðêèðîâêè
rQ+rD-2. Äëÿ ïðåäîòâðàùåíèÿ íàðàñòàíèÿ rQ âî âòîðîì öèêëå ïî ïåðåìåííîé j
âûïîëíÿåòñÿ îêîí÷àòåëüíîå ïåðåâû÷èñëåíèå øèôðà (2) ìàðêèðîâêè â ïåðåìåí-
íîé sQ ñ ó÷åòîì ôàêòè÷åñêîãî çíà÷åíèÿ ìàêñèìàëüíîãî ýëåìåíòà maxQ1. �
Òåîðåìà 1. Àëãîðèòì AUIPN ðåàëèçóåò äèíàìèêó ïðîèçâîëüíîé çàäàííîé
èíãèáèòîðíîé ñåòè Ïåòðè.
Äîêàçàòåëüñòâî. Ïîêàæåì, ÷òî àëãîðèòì AUIPN ïåðåâû÷èñëÿåò ìàðêèðîâêó
èíãèáèòîðíîé ñåòè Ïåòðè â ñîîòâåòñòâèè ñ ñèñòåìîé (1) è ñîõðàíÿåò èñïîëüçî-
âàííóþ ïîñëåäîâàòåëüíîñòü ñðàáàòûâàíèÿ ïåðåõîäîâ. Àëãîðèòì âûïîëíåíèÿ
øàãà ïðåäñòàâëåí öèêëîì while àëãîðèòìà AUIPN è ïîëíîñòüþ ñîîòâåòñòâóåò
ñèñòåìå (1). Âíà÷àëå ïðîöåäóðà CheckFire îïðåäåëÿåò ìíîæåñòâî âîçáóæäåí-
íûõ ïåðåõîäîâ è ôîðìèðóåò øèôð (2) ñîîòâåòñòâóþùåãî èíäèêàòîðà âîçáóæäåí-
íûõ ïåðåõîäîâ u (ëåììà 1). Ïðè îòñóòñòâèè âîçáóæäåííûõ ïåðåõîäîâ u �� 0 âû-
ïîëíåíèå àëãîðèòìà ïðåêðàùàåòñÿ, ÷òî ñîîòâåòñòâóåò òóïèêîâîé ìàðêèðîâêå.
Ïðîöåäóðà PickFire âûïîëíÿåò íåäåòåðìèíèðîâàííûé âûáîð ñðàáàòûâàþùåãî
ïåðåõîäà èç ìíîæåñòâà âîçáóæäåííûõ. Ïåðåìåííàÿ l âîçâðàùàåò íîìåð ñðàáàòû-
âàþùåãî ïåðåõîäà (ëåììà 2). Ïðîöåäóðà Fire ðåàëèçóåò èçìåíåíèå òåêóùåé
ìàðêèðîâêè â ðåçóëüòàòå ñðàáàòûâàíèÿ ïåðåõîäà ñ íîìåðîì l ñ åå îäíîâðåìåí-
30 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4
íûì øèôðîâàíèåì (2) (ëåììà 3). Çàòåì â øèôð (2) ïîñëåäîâàòåëüíîñòè ñðàáàòû-
âàíèÿ ïåðåõîäîâ sZ äîáàâëÿåòñÿ íîìåð l è çíà÷åíèå òåêóùåãî øàãà k óâåëè÷èâà-
åòñÿ íà åäèíèöó. Íåäåòåðìèíèðîâàííûé âûõîä èç öèêëà ñîîòâåòñòâóåò îïðåäåëå-
íèþ 1. �
Àëãîðèòì AUIPN áûë òàêæå çàêîäèðîâàí íà ÿçûêå Ñè ñ èñïîëüçîâàíèåì áèá-
ëèîòåêè MPI äëÿ ïðåäñòàâëåíèÿ ñâåðõäëèííûõ öåëûõ è ïðîòåñòèðîâàí íà ðÿäå
ñåòåé Ïåòðè.
Òåîðåìà 2. Àëãîðèòì AUIPN ìîæåò áûòü ïðåäñòàâëåí èíãèáèòîðíîé ñåòüþ
Ïåòðè.
Äîêàçàòåëüñòâî òåîðåìû 2 íåïîñðåäñòâåííî âûòåêàåò èç òîãî ôàêòà, ÷òî èí-
ãèáèòîðíàÿ ñåòü Ïåòðè ÿâëÿåòñÿ óíèâåðñàëüíîé àëãîðèòìè÷åñêîé ñèñòåìîé [1] è
àëãîðèòì AUIPN èñïîëüçóåò òîëüêî öåëûå íåîòðèöàòåëüíûå ñêàëÿðíûå ïåðåìåí-
íûå, çíà÷åíèÿ êîòîðûõ ìîãóò áûòü ïðåäñòàâëåíû ìàðêèðîâêàìè ñîîòâåòñòâóþ-
ùèõ ïîçèöèé ñåòè Ïåòðè.
Äëÿ êîíñòðóêòèâíîãî äîêàçàòåëüñòâà òåîðåìû 2 ñîîòâåòñòâóþùàÿ ñåòü áóäåò
ïîñòðîåíà ïî àëãîðèòìó AUIPN â ïîñëåäóþùèõ ðàçäåëàõ íàñòîÿùåé ñòàòüè.
5. ÏÐÈÍÖÈÏÛ ÊÎÄÈÐÎÂÀÍÈß ÀËÃÎÐÈÒÌÀ ÈÍÃÈÁÈÒÎÐÍÎÉ ÑÅÒÜÞ ÏÅÒÐÈ
Èçâåñòíû ðàçëè÷íûå ïîäõîäû ê êîäèðîâàíèþ àëãîðèòìà ñåòüþ Ïåòðè,
îñíîâàííûå íà ïðèíöèïàõ êîìáèíèðîâàíèÿ ïîòîêîâ äàííûõ è ïîòîêîâ óïðàâëå-
íèÿ [2, 5, 6]. Èñïîëüçóåì íåïîñðåäñòâåííîå êîäèðîâàíèå îñíîâíûõ îïåðàòîðîâ
ÿçûêà ïðîãðàììèðîâàíèÿ Ñè äëÿ ïðåäñòàâëåíèÿ îäíîãî ïîòîêà óïðàâëåíèÿ. Êàæ-
äàÿ ïåðåìåííàÿ ïðåäñòàâëåíà ñîîòâåòñòâóþùåé ïîçèöèåé ñåòè Ïåòðè. Âñå ïåðå-
ìåííûå ÿâëÿþòñÿ ãëîáàëüíûìè. Ïîòîê óïðàâëåíèÿ ìîäåëèðóåòñÿ òðàññîé ïðîõîæ-
äåíèÿ îäíîé ôèøêè èç íà÷àëüíîé ïîçèöèè start â êîíå÷íóþ ïîçèöèþ finish.
Äëÿ óíèôèöèðîâàííîé îðãàíèçàöèè ðàáîòû ñ ïåðåìåííûìè áóäåì ïðåäñòàâ-
ëÿòü îïåðàòîðû ÿçûêà ïðîãðàììèðîâàíèÿ â âèäå ñõåìû, èçîáðàæåííîé íà ðèñ. 2.
Äëÿ îáåñïå÷åíèÿ ïî-
âòîðíîãî ïðîõîæäåíèÿ ïîòî-
êà óïðàâëåíèÿ ÷åðåç îïåðà-
òîðû (ïðîöåäóðû) ïðèìåì
ñëåäóþùèå ñîãëàøåíèÿ: âñå
âíóòðåííèå ïîçèöèè èìåþò
íóëåâóþ ðàçìåòêó; ïåðåä íà-
÷àëîì ðàáîòû âõîäíûå ïåðå-
ìåííûå êîïèðóþòñÿ âî
âõîäíûå ïîçèöèè îïåðàòîðà;
ðàáîòà îïåðàòîðà çàïóñêàåòñÿ ôèøêîé â ïîçèöèè start (s); îïåðàòîð çàâåðøàåò
ñâîþ ðàáîòó ïðè ïîïàäàíèè ôèøêè â ïîçèöèþ finsh (f); ïðè çàâåðøåíèè ðàáî-
òû âñå ïîçèöèè îïåðàòîðà ñòàíîâÿòñÿ ïóñòûìè, çà èñêëþ÷åíèåì âûõîäíûõ ïîçè-
öèé, â êîòîðûõ íàõîäèòñÿ ðåçóëüòàò. Øòðèõîâûå äóãè îáîçíà÷àþò ñëåäóþùèå
äîïîëíèòåëüíûå ïðàâèëà ôîðìèðîâàíèÿ çíà÷åíèé âõîäíûõ è âûõîäíûõ ïåðåìåí-
íûõ îïåðàòîðà: ïðè çàïóñêå ñîäåðæèìîå ïåðåìåííîé êîïèðóåòñÿ â ëîêàëüíóþ
âõîäíóþ ïîçèöèþ îïåðàòîðà; ïîñëå çàâåðøåíèÿ ïåðåìåííàÿ î÷èùàåòñÿ è â íåå
ïåðåìåùàåòñÿ çíà÷åíèå èç ëîêàëüíîé âûõîäíîé ïîçèöèè îïåðàòîðà (ðèñ. 3).
 ñëó÷àå íåñêîëüêèõ ïåðåìåííûõ ñîçäàþòñÿ öåïî÷êè COPY äëÿ ïîñëåäîâàòåëüíî-
ãî êîïèðîâàíèÿ âõîäíûõ ïåðåìåííûõ è öåïî÷êè CLEAN, MOVE äëÿ ïåðåìåùåíèÿ
âûõîäíûõ ïåðåìåííûõ. Ïîñëåäîâàòåëüíîñòü îïåðàöèé CLEAN, MOVE äàëåå îáî-
çíà÷åíà ASSIGN. Ïðåäñòàâëåííàÿ ñõåìà îáåñïå÷èâàåò êîððåêòíóþ ðàáîòó ñ ïåðå-
ìåííûìè â îáùåì ñëó÷àå. Ðàáîòà ñ ïåðåìåííûìè ìîæåò áûòü îïòèìèçèðîâàíà,
êîãäà îíè ÿâëÿþòñÿ âðåìåííûìè ëèáî âõîäíûìè è âûõîäíûìè îäíîâðåìåííî.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4 31
fs
Âûõîäíûå
ïåðåìåííûå
. . .
Âõîäíûå ïåðåìåííûå
. . .
Îïåðàòîð (ïðîöåäóðà)
Ðèñ. 2. Ñõåìà ïðåäñòàâëåíèÿ îïåðàòîðà ÿçûêà ïðîãðàììèðî-
âàíèÿ
Äëÿ âû÷èñëåíèÿ âûðàæåíèé ìîæåò áûòü èñïîëüçîâàí ïîäõîä ïîòîêîâ äàííûõ: âû-
ïîëíåíèå îïåðàöèé óïîðÿäî÷èâàåòñÿ â ñîîòâåòñòâèè ñ èõ ïðèîðèòåòàìè. Âûõîäíûå
ïîçèöèè îïåðàöèè ñîâìåùàþòñÿ ñ âõîäíûìè ïîçèöèÿìè ñëåäóþùåé îïåðàöèè.
Äàëåå ðàññìîòðèì ïðåäñòàâëåíèå îñíîâíûõ óïðàâëÿþùèõ êîíñòðóêöèé ÿçû-
êà ïðîãðàììèðîâàíèÿ: ïîñëåäîâàòåëüíîñòè (operator1; operator2) âåòâëåíèÿ
(if(condition()) operator1; else operator2) , öèêë while
(while(condition()) operator) è öèêë for (for(i=n;i>0;i--) operator).
Àáñòðàãèðóåìñÿ îò èñïîëüçóåìûõ ïåðåìåííûõ.
Ëåììà 4. Àëãîðèòìè÷åñêèå óïðàâëÿþùèå êîíñòðóêöèè ÿçûêà ïðîãðàììèðî-
âàíèÿ ìîãóò áûòü çàêîäèðîâàíû èíãèáèòîðíîé ñåòüþ Ïåòðè â ôîðìå, èçîáðàæåí-
íîé íà ðèñ. 4.
32 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4
Îïåðàòîð
Âõîäíûå ïåðåìåííûå
s
Âûõîäíûå ïåðåìåííûå
COPY
x
CLEANf
MOVE f
f/s
y
s
Ðèñ. 3. Ñõåìà ôîðìèðîâàíèÿ âõîäíûõ è âûõîäíûõ ïåðåìåííûõ
Ðèñ. 4. Ñõåìà êîäèðîâàíèÿ óïðàâëÿþùèõ êîíñòðóêöèé ÿçûêà ïðîãðàììèðîâàíèÿ:
ïîñëåäîâàòåëüíîñòü (à), âåòâëåíèå (á), öèêë while (â), öèêë for (ã)
a
á
â
ã
Äëÿ êàæäîé óïðàâëÿþùåé êîíñòðóêöèè êîððåêòíîñòü ïðåäñòàâëåíèÿ ìîæåò
áûòü äîêàçàíà ïóòåì êëàññèôèêàöèè âñåõ äîïóñòèìûõ ïîñëåäîâàòåëüíîñòåé ñðà-
áàòûâàíèÿ ïåðåõîäîâ è èõ ñðàâíåíèÿ ñ ïîðÿäêîì âûïîëíåíèÿ îïåðàòîðîâ â êîí-
ñòðóêöèÿõ ÿçûêà ïðîãðàììèðîâàíèÿ [2]. Îòìåòèì, ÷òî â ñîîòâåòñòâèè ñ ðèñ. 4, à
ñóïåðïîçèöèÿ îïåðàòîðîâ ïðè êîäèðîâàíèè ïðîãðàììû âûïîëíÿåòñÿ ïóòåì íàëî-
æåíèÿ (ñîâìåùåíèÿ) âûõîäíîé ïîçèöèè f ïåðâîãî îïåðàòîðà ñ âõîäíîé ïîçèöèåé
s âòîðîãî îïåðàòîðà. Ñîâìåùåíèå ïîçèöèé ãëîáàëüíûõ ïåðåìåííûõ ñ êîíòàêòíû-
ìè ïîçèöèÿìè îïåðàòîðîâ èñïîëüçîâàíî òàêæå ïðè ïðèñîåäèíåíèè âñïîìîãà-
òåëüíûõ ñåòåé êîïèðîâàíèÿ çíà÷åíèé ïåðåìåííûõ (CLEAN, COPY, MOVE, ASSIGN),
ïðåäñòàâëåííûõ øòðèõîâûìè äóãàìè íà ðèñ. 2.
Ðåàëèçàöèÿ îñíîâíûõ àëãåáðàè÷åñêèõ è ëîãè÷åñêèõ îïåðàöèé ñåòÿìè Ïåòðè
ðàññìîòðåíà â [2, 6].  íåêîòîðûõ ñëó÷àÿõ öåëåñîîáðàçíî ïðåäñòàâèòü íåïîñðå-
äñòâåííî íàèáîëåå ÷àñòî âñòðå÷àþùèåñÿ îïåðàöèè (êàê, íàïðèìåð, MUL_ADD è
MOD_DIV äëÿ øèôðîâàíèÿ è äåøèôðîâàíèÿ ñåòè Ïåòðè). Â ïðèëîæåíèè À ïðèâå-
äåíû ñåòè, âûïîëíÿþùèå îïåðàöèè, êîòîðûå èñïîëüçîâàíû â àëãîðèòìå AUIPN.
Ëåììà 5. Ñåòè, ïðåäñòàâëåííûå â ïðèëîæåíèè À, ðåàëèçóþò óêàçàííûå îïåðàöèè.
Äëÿ êàæäîé ïðåäñòàâëåííîé ñåòè äîêàçàòåëüñòâî êîððåêòíîé ðåàëèçàöèè
òðåáóåìîé îïåðàöèè ìîæíî ïîñòðîèòü íà îñíîâå êëàññèôèêàöèè âñåõ äîïóñòè-
ìûõ ïîñëåäîâàòåëüíîñòåé ñðàáàòûâàíèÿ ïåðåõîäîâ [2, 6].
6. ÊÎÌÏÎÇÈÖÈß ÓÍÈÂÅÐÑÀËÜÍÎÉ ÈÍÃÈÁÈÒÎÐÍÎÉ ÑÅÒÈ ÏÅÒÐÈ UIPN
Çàêîäèðóåì àëãîðèòì ðàáîòû óíèâåðñàëüíîé ñåòè Ïåòðè AUIPN èíãèáèòîðíîé
ñåòüþ Ïåòðè â ñîîòâåòñòâèè ñ ïðàâèëàìè, îïèñàííûìè â ðàçä. 5. Îòìåòèì, ÷òî
ëåììà 4 è ëåììà 5 (Ïðèëîæåíèå À) ïåðå÷èñëÿþò âñå óïðàâëÿþùèå êîíñòðóêöèè è
âñå îïåðàöèè, èñïîëüçóåìûå â àëãîðèòìå AUIPN. Ïîëó÷èì ñåòü UIPN, èçîáðàæåí-
íóþ íà ðèñ. 5 è 6. Äëÿ ïðåäñòàâëåíèÿ ïåðåìåííûõ àëãîðèòìà èñïîëüçóþòñÿ ñîâìå-
ùåííûå ïîçèöèè: âñå ïîçèöèè ñ îäèíàêîâûì èìåíåì ëîãè÷åñêè ÿâëÿþòñÿ îäíîé è
òîé æå ïîçèöèåé. Ñîâìåùåííûå ïîçèöèè óïðîùàþò ãðàôè÷åñêîå ïðåäñòàâëåíèå
ñåòè. Ïðåäïîëàãàåì, ÷òî ïåðåä çàïóñêîì ñåòè UIPN øèôð èñïîëíÿåìîé ñåòè XIPN
çàãðóæåí â ïîçèöèè, èçîáðàæåííûå íà ðèñ. 1, à ïîñëå îñòàíîâà ñåòè UIPN øèôð
ìàðêèðîâêè è ïîñëåäîâàòåëüíîñòè ñðàáàòûâàíèÿ ïåðåõîäîâ ñåòè XIPN ñ÷èòàí èç ñî-
îòâåòñòâóþùèõ ïîçèöèé. Øòðèõîâûå äóãè îáîçíà÷àþò ðàññìîòðåííûå â ðàçä. 5 ñî-
ãëàøåíèÿ ïî êîïèðîâàíèþ âõîäíûõ è âûõîäíûõ ïåðåìåííûõ. Äâóõíàïðàâëåííûå
äóãè èñïîëüçîâàíû äëÿ ðàáîòû ñ ïåðåìåííûìè, êîòîðûå îäíîâðåìåííî ÿâëÿþòñÿ
âõîäíûìè è âûõîäíûìè.  ýòîì ñëó÷àå êîïèðîâàíèå ìîæíî îïòèìèçèðîâàòü,
äâàæäû âûïîëíÿÿ îïåðàöèè MOVE áåç î÷èñòêè.  íåêîòîðûõ ñëó÷àÿõ äëÿ êîïèðîâà-
íèÿ âõîäíîé ïåðåìåííîé âìåñòå ñ åå îäíîâðåìåííîé î÷èñòêîé öåëåñîîáðàçíî èñ-
ïîëüçîâàòü MOVE âìåñòî COPY.  êà÷åñòâå ñîîòâåòñòâóþùåãî îáîçíà÷åíèÿ èñïîëüçó-
åòñÿ ïóíêòèð. Ïîäñòàíîâêà ïåðåõîäà ïîäðàçóìåâàåò êîïèðîâàíèå ñîîòâåòñòâóþùåé
ïîäñåòè ñ ñîâìåùåíèåì êîíòàêòíûõ ïîçèöèé [7].  îáùåì ñëó÷àå ïîäñòàíîâêà ïå-
ðåõîäà òðåáóåò óêàçàíèÿ îòîáðàæåíèÿ âõîäíûõ è âûõîäíûõ ïîçèöèé. Â ïðåäñòàâ-
ëåííûõ ñåòÿõ îòîáðàæåíèå ïîçèöèé îïðåäåëåíî êîíòåêñòîì èñïîëüçîâàíèÿ îïåðà-
öèè è íå óêàçàíî íà ðèñóíêàõ.
Òåîðåìà 3. Ñåòü UIPN ÿâëÿåòñÿ óíèâåðñàëüíîé èíãèáèòîðíîé ñåòüþ Ïåòðè.
Äîêàçàòåëüñòâî òåîðåìû 3 íåïîñðåäñòâåííî ñëåäóåò èç òåîðåìû 1 è êîððåêò-
íîñòè èñïîëüçîâàííûõ ïðàâèë êîäèðîâàíèÿ ïîñëåäîâàòåëüíîãî àëãîðèòìà èíãè-
áèòîðíîé ñåòüþ Ïåòðè (ëåììà 4), à òàêæå êîððåêòíîñòè ñåòåé, ðåàëèçóþùèõ èñ-
ïîëüçîâàííûå îïåðàöèè (ëåììà 5).
Îòìåòèì, ÷òî ñåòü UIPN èçîáðàæåíà íà ðèñ. 5, 6 ïîêîìïîíåíòíî â ñîîòâåò-
ñòâèè ñ èñïîëüçîâàííûìè ïðîöåäóðàìè, îïåðàöèÿìè è ïðàâèëàìè ðàáîòû ñ ïåðå-
ìåííûìè. Îïðåäåëåííûé èíòåðåñ ïðåäñòàâëÿþò êîìïîíîâêà UIPN â ôîðìå åäè-
íîé èíãèáèòîðíîé ñåòè Ïåòðè è åå èñïîëíåíèå â ñðåäå íåêîòîðîé ìîäåëèðóþùåé
ñèñòåìû, èìèòèðóþùåé ïðîöåññ ñðàáàòûâàíèÿ ïåðåõîäîâ.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4 33
34 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4
à
á
â
Ð
è
ñ.
5
.
Ó
í
è
â
åð
ñà
ë
ü
í
àÿ
è
í
ãè
á
è
òî
ð
í
àÿ
ñå
òü
Ï
åò
ð
è
U
I
P
N
(à
);
ï
î
ä
ñå
òü
P
i
c
k
F
i
r
e
(á
);
àë
ãî
ð
è
òì
ï
ð
î
ö
åä
ó
ð
û
C
h
e
c
k
F
i
r
e
(â
)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4 35
Ð
è
ñ.
6
.
Ï
î
ä
ñå
òü
F
i
r
e
ÇÀÊËÞ×ÅÍÈÅ
 íàñòîÿùåé ñòàòüå âûïîëíåíî ïîñòðîåíèå óíèâåðñàëüíîé èíãèáèòîðíîé ñåòè
Ïåòðè, èñïîëíÿþùåé ïðîèçâîëüíóþ çàäàííóþ èíãèáèòîðíóþ ñåòü Ïåòðè.
 ñîîòâåòñòâèè ñ îöåíêàìè, ïîëó÷åííûìè â [8], ñåòü ñîäåðæèò îêîëî 500 ïî-
çèöèé, 500 ïåðåõîäîâ, 1500 äóã è ìîäåëèðóåò äèíàìèêó çàäàííîé èíãèáèòîð-
íîé ñåòè çà âðåìÿ o k k( / )2 log ñ ðàçìåðîì ïàìÿòè o k( ), ãäå k — êîëè÷åñòâî
çàïóùåííûõ ïåðåõîäîâ.
Âîçìîæíî ïîñòðîåíèå óíèâåðñàëüíûõ ñåòåé è â äðóãèõ êëàññàõ ñåòåé Ïåòðè
(ïðèîðèòåòíûõ, ñèíõðîííûõ, âðåìåííûõ), ÿâëÿþùèõñÿ óíèâåðñàëüíîé àëãîðèò-
ìè÷åñêîé ñèñòåìîé. Êðîìå òîãî, âîçìîæíû êîìáèíèðîâàííûå ïîñòðîåíèÿ, íà-
ïðèìåð èíãèáèòîðíîé ñåòè, âûïîëíÿþùåé ïðîèçâîëüíóþ ñèíõðîííóþ ñåòü.
Ïðèìåðû ïîñòðîåíèÿ óíèâåðñàëüíûõ ìàøèí Òüþðèíãà ñ ìèíèìàëüíûì êî-
ëè÷åñòâîì èñïîëüçîâàííûõ ñèìâîëîâ/ñîñòîÿíèé äàíû â ðàáîòàõ [9, 10].  ýòîé
ñâÿçè îïðåäåëåííûé èíòåðåñ ïðåäñòàâëÿåò ïîñòðîåíèå óíèâåðñàëüíîé ñåòè Ïåòðè
ñ ìèíèìàëüíûì êîëè÷åñòâîì ïîçèöèé (ïåðåõîäîâ), ìèíèìàëüíûì çíà÷åíèåì
ìàðêèðîâêè.
ÏÐÈËÎÆÅÍÈÅ À. ÐÅÀËÈÇÀÖÈß ÈÑÏÎËÜÇÎÂÀÍÍÛÕ ÎÏÅÐÀÖÈÉ
1. Î÷èñòèòü ïåðåìåííóþ (x � 0)
CLEAN::
2. Êîïèðîâàòü çíà÷åíèå ïåðåìåííîé ( y x� )
COPY::
3. Ïåðåìåñòèòü çíà÷åíèå ïåðåìåííîé (y x x� �, 0)
MOVE::
36 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4
4. Ñëîæåíèå (z x y� � )
ADD::
5. Âû÷èòàíèå (z x y� �� ): óñëîâíîå âû÷èòàíèå z
x y x y
x y
�
�
�
�
�
,
,0SUB::
6. Óìíîæåíèå (z x y� � )
MUL::
7. Ñðàâíåíèå (x y
)
GTE::
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4 37
8. Ìàêñèìóì (z x y� max( , ))
MAX::
9. Äîáàâèòü ê øèôðó
MUL_ADD::
10. Èçâëå÷ü èç øèôðà (z x y x y� �div mod, � )
MOD_DIV::
38 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4
ÏÐÈËÎÆÅÍÈÅ Á. ÏÐÈÌÅÐÛ ØÈÔÐÎÂÀÍÈß ÑÅÒÅÉ
Ò à á ë è ö à 1 . Øèôðîâàíèå ãðàôà ñåòè
Ñåòü m n sB rB sD rD
add 6 4 21180169496 3 282946 2
max 8 8 254813592433189871074065241412 3 293862152152879368 2
mul 10 9 646549072061101455668889034663481743952654 3 19352259085292454555975681 2
Ò à á ë è ö à 2 . Øèôðîâàíèå ìàðêèðîâêè
Ñåòü Ìàðêèðîâêà Q sQ rQ
add addQ0 (2,3,1,0,0,0) 2880 4
add addQ (0,0,0,5,1,0) 186 6
max maxQ0 (2,3,1,0,0,0,0,0) 46080 4
max maxQ (0,0,0,3,1,0,0,0) 832 4
mul mulQ0 (2,3,1,0,0,0,0,0,0,0) 737280 4
mul mulQ (0,0,0,6,1,0,0,0,0,0) 722701 7
Ò à á ë è ö à 3 . Øèôðîâàíèå ïîñëåäîâàòåëüíîñòè ñðàáàòûâàíèÿ ïåðåõîäîâ
Ñåòü Q0 Q Z sZ k
add addQ0 addQ t1,t3,t2,t2,t3,t3,t4 2411 7
max maxQ0 maxQ t1,t2,t2,t6,t7,t8 4983 6
mul mulQ0 mulQ
t1,t2,t4,t4,t5,t6,t6,t7,t2,t4,t4,t5,t6,t6,
t7,t2,t4,t4,t5,t6,t6,t7,t3,t9,t9,t8
109815712212339723705298 26
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. A g e r w a l a T . A complete model for representing the coordination of asynchronous processes.
— Baltimore: John Hopkins University, Hopkins Computer Science Program, Res. Rep., No. 32,
July 1974. — 58 ð.
2. Ê î ò î â Â . Å . Ñåòè Ïåòðè. — Ì.: Íàóêà, 1984. — 160 ñ.
3. T h e u n i v e r s a l Turing machine. A half-century survey / Rolf Herken (ed.), Wien; New York:
Springer-Verlag, 1994. — 609 p.
4. Z a i t s e v D . A . Universal inhibitor Petri net // Proceedings of the 17th German Workshop on
Algorithms and Tools for Petri Nets, Cottbus, Germany, October 07-08, 2010. — Ð. 1–15.
5. Ñ ë å ï ö î â À . È . , Þ ð à ñ î â À . À . Àâòîìàòèçàöèÿ ïðîåêòèðîâàíèÿ óïðàâëÿþùèõ ñèñòåì
ãèáêèõ àâòîìàòèçèðîâàííûõ ïðîèçâîäñòâ / Ïîä ðåä. Á.Í. Ìàëèíîâñêîãî. — Ê.: Òåõíiêà, 1986.
— 160 ñ.
6. Ñ ë å ï ö î â À . È . Óðàâíåíèÿ ñîñòîÿíèé è ýêâèâàëåíòíûå ïðåîáðàçîâàíèÿ íàãðóæåííûõ
ñåòåé Ïåòðè (àëãåáðàè÷åñêèé ïîäõîä) // Ôîðìàëüíûå ìîäåëè ïàðàëëåëüíûõ âû÷èñëåíèé:
Äîêë. è ñîîáù. Âñåñîþç. êîíô. — Íîâîñèáèðñê, 1988. — C. 151–158.
7. Ç à é ö å â Ä . À . Êîìïîçèöèîííûé àíàëèç ñåòåé Ïåòðè // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç.
— 2006. — ¹ 1. — Ñ. 143–154.
8. Z a i t s e v D . A . Complexity of universal inhibitor Petri net // Proc. of the 18th German Workshop
on Algorithms and Tools for Petri Nets, Hagen, Germany, September 29–30, 2011. — Ð. 62–71.
9. M i n s k y M . Size and structure of universal Turing machines using tag systems / Recursive
Function Theory, Symposium in Pure Mathematics, 5, AMS, Provelence, 1962. — Ð. 229–238.
10. R o g o z h i n Y . Small universal Turing machines // TCS. — 1996. — 168(2). — Ð. 215–240.
Ïîñòóïèëà 18.03.2010
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4 39
|
| id | nasplib_isofts_kiev_ua-123456789-84122 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T15:59:19Z |
| publishDate | 2012 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Зайцев, Д.А. 2015-07-03T09:04:12Z 2015-07-03T09:04:12Z 2012 Универсальная сеть Петри / Д.А. Зайцев // Кибернетика и системный анализ. — 2012. — Т. 48, № 4. — С. 24-39. — Бібліогр.: 10 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/84122 519.6, 510.51 Побудовано універсальну інгібіторну мережу Петрі, яка виконує довільну задану інгібіторну мережу Петрі. Граф інгібіторної мережі Петрі, її маркірування і послідовність спрацьовування переходів зашифровано як десять невід’ємних цілих скалярних змінних, поданих відповідними позиціями універсальної мережі. За рівнянням станів побудовано алгоритм виконання інгібіторної мережі, який використовує лише вказані скалярні змінні. Алгоритм закодовано інгібіторною мережею Петрі. Використано підмережі, які реалізують арифметичні і логічні операції, копіювання значень змінних. A universal inhibitor Petri net is constructed, which executes an arbitrary given inhibitor Petri net. The inhibitor Petri net graph, its marking, and transition firing sequence are encoded as 10 scalar nonnegative integer variables and are represented by the corresponding places of the universal net. An algorithm of inhibitor net execution that uses only these scalar variables is developed based on the state equation and is encoded by the universal inhibitor Petri net. Subnets that implement arithmetic, comparison, and copying operations are employed. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Универсальная сеть Петри Універсальна мережа Петрі Universal Petri net Article published earlier |
| spellingShingle | Универсальная сеть Петри Зайцев, Д.А. Кибернетика |
| title | Универсальная сеть Петри |
| title_alt | Універсальна мережа Петрі Universal Petri net |
| title_full | Универсальная сеть Петри |
| title_fullStr | Универсальная сеть Петри |
| title_full_unstemmed | Универсальная сеть Петри |
| title_short | Универсальная сеть Петри |
| title_sort | универсальная сеть петри |
| topic | Кибернетика |
| topic_facet | Кибернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84122 |
| work_keys_str_mv | AT zaicevda universalʹnaâsetʹpetri AT zaicevda uníversalʹnamerežapetrí AT zaicevda universalpetrinet |