Эквивалентное представление моделей сложных дискретных систем с помощью алгебры процессов
The process algebra is considered which is on the parallel structure orientated description. The structures function with real working load. The basic concepts are determined for behavioral equivalence of models submitted by labeled transition systems. Definition is formed and the basic properties a...
Збережено в:
| Опубліковано в: : | Электронное моделирование |
|---|---|
| Дата: | 2008 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2008
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/101549 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Эквивалентное представление моделей сложных дискретных систем с помощью алгебры процессов / Б.Б. Нестеренко, М.А. Новотарский // Электронное моделирование. — 2008. — Т. 30, № 1. — С. 3-18. — Бібліогр.: 7 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-101549 |
|---|---|
| record_format |
dspace |
| spelling |
Нестеренко, Б.Б. Новотарский, М.А. 2016-06-04T19:11:18Z 2016-06-04T19:11:18Z 2008 Эквивалентное представление моделей сложных дискретных систем с помощью алгебры процессов / Б.Б. Нестеренко, М.А. Новотарский // Электронное моделирование. — 2008. — Т. 30, № 1. — С. 3-18. — Бібліогр.: 7 назв. — рос. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/101549 681.3 The process algebra is considered which is on the parallel structure orientated description. The structures function with real working load. The basic concepts are determined for behavioral equivalence of models submitted by labeled transition systems. Definition is formed and the basic properties are stated for strong mutual model similarity. The direct and accelerated algorithms are developed for determination of strong mutual similarity on the basis of the received properties Рассмотрена алгебра процессов, ориентированная на описание параллельных структур, функционирующих с использованием реальной рабочей нагрузки. Определены основные понятия поведенческой эквивалентности моделей, представленных маркированными системами с переходами. Дано определение и изложены основные свойства строгого взаимного подобия моделей. На основании полученных свойств разработаны прямой и ускоренный алгоритмы определения строгого взаимного подобия. Розглянуто алгебру процесів, яка орієнтована на опис паралельних структур, що функціонують з використанням реального робочого навантаження. Визначено основні поняття поведінкової еквівалентності моделей, представлених маркованими системами з переходами. Дано визначення і викладено основні властивості строгої взаємної подібності моделей. На підставі отриманих властивостей розроблено прямий і прискорений алгоритми визначення строгої взаємної подібності. ru Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Электронное моделирование Математические методы и модели Эквивалентное представление моделей сложных дискретных систем с помощью алгебры процессов Equivalent Representation of Models of Complicated Digital Systems by Means of Process Algebra Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Эквивалентное представление моделей сложных дискретных систем с помощью алгебры процессов |
| spellingShingle |
Эквивалентное представление моделей сложных дискретных систем с помощью алгебры процессов Нестеренко, Б.Б. Новотарский, М.А. Математические методы и модели |
| title_short |
Эквивалентное представление моделей сложных дискретных систем с помощью алгебры процессов |
| title_full |
Эквивалентное представление моделей сложных дискретных систем с помощью алгебры процессов |
| title_fullStr |
Эквивалентное представление моделей сложных дискретных систем с помощью алгебры процессов |
| title_full_unstemmed |
Эквивалентное представление моделей сложных дискретных систем с помощью алгебры процессов |
| title_sort |
эквивалентное представление моделей сложных дискретных систем с помощью алгебры процессов |
| author |
Нестеренко, Б.Б. Новотарский, М.А. |
| author_facet |
Нестеренко, Б.Б. Новотарский, М.А. |
| topic |
Математические методы и модели |
| topic_facet |
Математические методы и модели |
| publishDate |
2008 |
| language |
Russian |
| container_title |
Электронное моделирование |
| publisher |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| format |
Article |
| title_alt |
Equivalent Representation of Models of Complicated Digital Systems by Means of Process Algebra |
| description |
The process algebra is considered which is on the parallel structure orientated description. The structures function with real working load. The basic concepts are determined for behavioral equivalence of models submitted by labeled transition systems. Definition is formed and the basic properties are stated for strong mutual model similarity. The direct and accelerated algorithms are developed for determination of strong mutual similarity on the basis of the received properties
Рассмотрена алгебра процессов, ориентированная на описание параллельных структур, функционирующих с использованием реальной рабочей нагрузки. Определены основные понятия поведенческой эквивалентности моделей, представленных маркированными системами с переходами. Дано определение и изложены основные свойства строгого взаимного подобия моделей. На основании полученных свойств разработаны прямой и ускоренный алгоритмы определения строгого взаимного подобия.
Розглянуто алгебру процесів, яка орієнтована на опис паралельних структур, що функціонують з використанням реального робочого навантаження. Визначено основні поняття поведінкової еквівалентності моделей, представлених маркованими системами з переходами. Дано визначення і викладено основні властивості строгої взаємної подібності моделей. На підставі отриманих властивостей розроблено прямий і прискорений алгоритми визначення строгої взаємної подібності.
|
| issn |
0204-3572 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/101549 |
| citation_txt |
Эквивалентное представление моделей сложных дискретных систем с помощью алгебры процессов / Б.Б. Нестеренко, М.А. Новотарский // Электронное моделирование. — 2008. — Т. 30, № 1. — С. 3-18. — Бібліогр.: 7 назв. — рос. |
| work_keys_str_mv |
AT nesterenkobb ékvivalentnoepredstavleniemodeleisložnyhdiskretnyhsistemspomoŝʹûalgebryprocessov AT novotarskiima ékvivalentnoepredstavleniemodeleisložnyhdiskretnyhsistemspomoŝʹûalgebryprocessov AT nesterenkobb equivalentrepresentationofmodelsofcomplicateddigitalsystemsbymeansofprocessalgebra AT novotarskiima equivalentrepresentationofmodelsofcomplicateddigitalsystemsbymeansofprocessalgebra |
| first_indexed |
2025-11-26T18:44:18Z |
| last_indexed |
2025-11-26T18:44:18Z |
| _version_ |
1850768865585266688 |
| fulltext |
ÓÄÊ 681.3
Á. Á. Íåñòåðåíêî, ä-ð òåõí. íàóê, Ì. À. Íîâîòàðñêèé, êàíä. òåõí. íàóê
Èí-ò ìàòåìàòèêè ÍÀÍ Óêðàèíû
(Óêðàèíà, 01601 Êèåâ, 4, ÃÑÏ, óë. Òåðåùåíêîâñêàÿ, 3,
òåë. (044) 2340407; Å-mail: model@imath.kiev.ua, novotar@yandex.ru)
Ýêâèâàëåíòíîå ïðåäñòàâëåíèå ìîäåëåé
ñëîæíûõ äèñêðåòíûõ ñèñòåì ñ ïîìîùüþ àëãåáðû ïðîöåññîâ
(Ñòàòüþ ïðåäñòàâèë ä-ð òåõí íàóê À. Ô. Âåðëàíü)
Ðàññìîòðåíà àëãåáðà ïðîöåññîâ, îðèåíòèðîâàííàÿ íà îïèñàíèå ïàðàëëåëüíûõ ñòðóêòóð,
ôóíêöèîíèðóþùèõ ñ èñïîëüçîâàíèåì ðåàëüíîé ðàáî÷åé íàãðóçêè. Îïðåäåëåíû îñíîâíûå
ïîíÿòèÿ ïîâåäåí÷åñêîé ýêâèâàëåíòíîñòè ìîäåëåé, ïðåäñòàâëåííûõ ìàðêèðîâàííûìè ñèñ-
òåìàìè ñ ïåðåõîäàìè. Äàíî îïðåäåëåíèå è èçëîæåíû îñíîâíûå ñâîéñòâà ñòðîãîãî âçàèì-
íîãî ïîäîáèÿ ìîäåëåé. Íà îñíîâàíèè ïîëó÷åííûõ ñâîéñòâ ðàçðàáîòàíû ïðÿìîé è óñêîðåí-
íûé àëãîðèòìû îïðåäåëåíèÿ ñòðîãîãî âçàèìíîãî ïîäîáèÿ.
Ðîçãëÿíóòî àëãåáðó ïðîöåñ³â, ÿêà îð³ºíòîâàíà íà îïèñ ïàðàëåëüíèõ ñòðóêòóð, ùî ôóíêö³î-
íóþòü ç âèêîðèñòàííÿì ðåàëüíîãî ðîáî÷îãî íàâàíòàæåííÿ. Âèçíà÷åíî îñíîâí³ ïîíÿòòÿ
ïîâåä³íêîâî¿ åêâ³âàëåíòíîñò³ ìîäåëåé, ïðåäñòàâëåíèõ ìàðêîâàíèìè ñèñòåìàìè ç ïåðåõî-
äàìè. Äàíî âèçíà÷åííÿ ³ âèêëàäåíî îñíîâí³ âëàñòèâîñò³ ñòðîãî¿ âçàºìíî¿ ïîä³áíîñò³
ìîäåëåé. Íà ï³äñòàâ³ îòðèìàíèõ âëàñòèâîñòåé ðîçðîáëåíî ïðÿìèé ³ ïðèñêîðåíèé àëãî-
ðèòìè âèçíà÷åííÿ ñòðîãî¿ âçàºìíî¿ ïîä³áíîñò³.
Ê ë þ ÷ å â û å ñ ë î â à: àëãåáðà ïðîöåññîâ, ïîâåäåí÷åñêàÿ ýêâèâàëåíòíîñòü, ñòðîãîå
âçàèìíîå ïîäîáèå.
 ñîâðåìåííîì ìèðå íàñ îêðóæàþò äèñêðåòíûå ñèñòåìû, ñîçäàííûå âñëåäñò-
âèå ðàçâèòèÿ íîâåéøèõ òåõíîëîãèé. Ïîä äèñêðåòíûìè ñèñòåìàìè ïîíèìàþò
ñèñòåìû, èçìåíÿþùèå ñâîè ñîñòîÿíèÿ òîëüêî â äèñêðåòíûå ìîìåíòû âðå-
ìåíè ïîä äåéñòâèåì îïðåäåëåííûõ ñîáûòèé. Òèïè÷íûìè ïðèìåðàìè òàêèõ
ñèñòåì ÿâëÿþòñÿ ãèáêèå ïðîèçâîäñòâåííûå êîìïëåêñû, òåëåêîììóíèêàöèîí-
íûå ñèñòåìû, ïàðàëëåëüíûå ìíîãîïðîöåññîðíûå ñèñòåìû è äð. Óñîâåðøåíñò-
âîâàíèå òåõíîëîãèé âåäåò ê ðàñøèðåíèþ ôóíêöèîíàëüíûõ âîçìîæíîñòåé
äèñêðåòíûõ ñèñòåì è, ñîîòâåòñòâåííî, ê óñëîæíåíèþ èõ ñòðóêòóðû è ïðèí-
öèïîâ ðàáîòû. Âñå áîëåå àêòóàëüíûìè ñòàíîâÿòñÿ çàäà÷è îïòèìèçàöèè óïî-
ìÿíóòûõ ñèñòåì êàê íà ýòàïå ðàçðàáîòêè, òàê è íà ýòàïå ýêñïëóàòàöèè. Ïîý-
òîìó îäíîé èç ãëàâíûõ çàäà÷ òåîðèè ìîäåëèðîâàíèÿ ìîæíî ñ÷èòàòü ïîèñê
íîâûõ èíñòðóìåíòîâ ôîðìàëüíîãî îïèñàíèÿ äèñêðåòíûõ ñèñòåì, îáëàäàþ-
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 1 3
����������� ��
���
��
�
�
����
ùèõ êîìïàêòíîñòüþ è ãèáêîñòüþ ïðåäñòàâëåíèÿ âçàèìîñâÿçåé êîìïîíåíò
ñëîæíûõ ñèñòåì, à òàêæå ïðîñòûìè ñðåäñòâàìè çàäàíèÿ àëãîðèòìîâ ôóíê-
öèîíèðîâàíèÿ ýòèõ êîìïîíåíò. Òàêèå òðåáîâàíèÿ ê ôîðìàëüíîìó îïèñà-
íèþ ïîçâîëÿþò ðàññìàòðèâàòü åãî êàê áàçîâîå ñðåäñòâî äëÿ ñîçäàíèÿ
ïðîãðàììíûõ ìîäóëåé, ìîäåëèðóþùèõ ðàáîòó ñëîæíûõ äèñêðåòíûõ ñèñ-
òåì, ÷òî îáåñïå÷èâàåò ýêâèâàëåíòíîñòü ìîäåëè â ôîðìàëüíîì ïðåäñòàâ-
ëåíèè è ïðîãðàììíîì âèäå, à òàêæå äàåò âîçìîæíîñòü ìîäèôèöèðîâàòü
ôîðìàëüíîå ïðåäñòàâëåíèå ïî ðåçóëüòàòàì òåñòèðîâàíèÿ ïðîãðàììíîé
ìîäåëè. Îäíèì èç âàæíûõ ñâîéñòâ ôîðìàëüíîãî ïðåäñòàâëåíèÿ ìîäåëè
ÿâëÿåòñÿ ìàñøòàáèðóåìîñòü.  ñëó÷àå, êîãäà áîëåå ñëîæíàÿ ìîäåëü ìîæåò
áûòü ïðåäñòàâëåíà ìåíåå ñëîæíîé ïðè ñîõðàíåíèè ýêâèâàëåíòíîñòè ïîâå-
äåíèÿ, ïîÿâëÿåòñÿ âîçìîæíîñòü ýêîíîìèè ðåñóðñîâ, íåîáõîäèìûõ äëÿ èñ-
ñëåäîâàíèÿ ñâîéñòâ òàêîé ìîäåëè.
Ðàñøèðåíèå ñôåðû ïðèìåíåíèÿ ìîäåëåé ïîñëóæèëî ñòèìóëîì ê ñîç-
äàíèþ áîëüøîãî ÷èñëà ôîðìàëüíûõ ñðåäñòâ. Íàïðèìåð, äëÿ îïðåäåëåíèÿ,
âèçóàëèçàöèè, ïðîåêòèðîâàíèÿ è äîêóìåíòèðîâàíèÿ ïðîãðàììíûõ ñèñòåì
èñïîëüçóþò óíèôèöèðîâàííûé ÿçûê ìîäåëèðîâàíèÿ UML ñîâìåñòíî ñ
ÿçûêîì îáúåêòíûõ îãðàíè÷åíèé OCL [1]. Ýòè ÿçûêè òàêæå ïðèìåíÿþò ïðè
ìîäåëèðîâàíèè áèçíåñ-ïðîöåññîâ, ñèñòåìíîì ïðîåêòèðîâàíèè è îòîáðà-
æåíèè îðãàíèçàöèîííûõ ñòðóêòóð. Ñ èñïîëüçîâàíèåì òàêèõ ïîíÿòèé êàê
êëàññ, êîìïîíåíò, îáîáùåíèå (generalization), îáúåäèíåíèå (aggregation) è
ïîâåäåíèå UML ïîçâîëÿåò ñêîíöåíòðèðîâàòüñÿ íà ïðîåêòèðîâàíèè èëè
èçó÷åíèè àðõèòåêòóðû îáúåêòà, íå âíèêàÿ â îñîáåííîñòè ôóíêöèîíèðî-
âàíèÿ êîìïîíåíò è ìåõàíèçìû âçàèìîäåéñòâèÿ ìåæäó íèìè.
ßçûêè UML, ARIS [2] è äðóãèå ÿçûêè îáúåêòíîãî ìîäåëèðîâàíèÿ â
ñèëó ñâîåé óíèâåðñàëüíîñòè íå ëèøåíû ðÿäà íåäîñòàòêîâ, ñðåäè êîòîðûõ
ìîæíî îòìåòèòü èçáûòî÷íîñòü è íåòî÷íóþ ñåìàíòèêó. Èìåííî ýòè íåäîñ-
òàòêè ÷àñòî ñòàíîâÿòñÿ ïðåïÿòñòâèåì ïðè ïîïûòêå ñòðîãîãî îïðåäåëåíèÿ
ýêâèâàëåíòíîñòè ìîäåëè è îáúåêòà ìîäåëèðîâàíèÿ.
Äëÿ ïðåîäîëåíèÿ äàííîé ïðîáëåìû èñïîëüçóþòñÿ íèçêîóðîâíåâûå
ôîðìàëüíûå ñðåäñòâà, àëãåáðû ïðîöåññîâ, ïîçâîëÿþùèå ñòðîãî îáîñíî-
âàòü ýêâèâàëåíòíîñòü âûðàæåíèé, èñõîäÿ èç îòíîøåíèé ýêâèâàëåíòíîñòè
ñîñòîÿíèé è ïðîöåññîâ êàê ïîñëåäîâàòåëüíîñòåé ýòèõ ñîñòîÿíèé.
Àëãåáðà ïðîöåññîâ (ïðîöåññíîå èñ÷èñëåíèå èëè òåîðèÿ ïðîöåññîâ) —
ýòî ìåòîä ôîðìàëüíîãî îïèñàíèÿ ñëîæíûõ äèñêðåòíûõ ñèñòåì, îáåñïå÷è-
âàþùèé ýêâèâàëåíòíîå îòîáðàæåíèå èõ ñòðóêòóðû è ïîâåäåíèÿ [3, 4].
Ïîïóëÿðíîñòü àëãåáð ïðîöåññîâ îáúÿñíÿåòñÿ óäà÷íûì îáúåäèíåíèåì
ôîðìàëüíîãî ïîäõîäà è âîçìîæíîñòè îïèñàíèÿ ñèñòåì ñ ïîìîùüþ àëãî-
ðèòìè÷åñêèõ ÿçûêîâ âûñîêîãî óðîâíÿ.  ðàìêàõ ôîðìàëüíîãî îïèñàíèÿ
îáúåêò ìîäåëèðîâàíèÿ ðàññìàòðèâàåòñÿ êàê ñèñòåìà ñ àêòèâíûìè êîìïî-
Á. Á. Íåñòåðåíêî, Ì. À. Íîâîòàðñêèé
4 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 1
íåíòàìè, âçàèìîäåéñòâóþùèìè ìåæäó ñîáîé è ñ âíåøíåé ñðåäîé â õîäå
ýâîëþöèè. Â ðîëè àêòèâíûõ êîìïîíåíò ìîäåëè, îòîáðàæàþùèõ ñîîòâåòñò-
âóþùèå êîìïîíåíòû ñèñòåìû, âûñòóïàþò àãåíòû èëè ïðîöåññû.
Ïîä ïðîöåññàìè ïîíèìàþò íåêîòîðûå ëîãè÷åñêèå ñòðóêòóðû, îïèñû-
âàþùèå îáúåêòû ìîäåëèðîâàíèÿ â âèäå ïîñëåäîâàòåëüíîñòåé àêòèâíîñ-
òåé, îáúåäèíÿåìûõ ñ ó÷åòîì ïðè÷èííî-ñëåäñòâåííûõ ñâÿçåé. Àêòèâíîñòü
â àëãåáðàõ ïðîöåññîâ îïèñûâàåò ìèíèìàëüíîå äåéñòâèå ìîäåëèðóåìîãî
êîìïîíåíòà.
Ñëåäóåò ðàçëè÷àòü äâà îñíîâíûõ âèäà àêòèâíîñòåé: àêòèâíîñòè âçàè-
ìîäåéñòâèÿ è âû÷èñëèòåëüíûå àêòèâíîñòè. Àêòèâíîñòè âçàèìîäåéñòâèÿ
ÿâëÿþòñÿ îñíîâíûìè áàçîâûìè ýëåìåíòàìè èíñòðóìåíòàðèÿ âûñîêîóðîâ-
íåâîãî îïèñàíèÿ âçàèìîäåéñòâèÿ, ïåðåäà÷è äàííûõ è ñèíõðîíèçàöèè ìåæ-
äó ìíîæåñòâîì ïàðàëëåëüíûõ ïðîöåññîâ. Âû÷èñëèòåëüíûå àêòèâíîñòè
ïðåäñòàâëÿþò íàèìåíüøèå åäèíèöû ðåñóðñîâ, èñïîëüçóåìûõ äëÿ ïðåîáðà-
çîâàíèÿ èíôîðìàöèè âíóòðè êîìïîíåíò. Ñîâîêóïíîñòü óïîìÿíóòûõ àêòèâ-
íîñòåé ñîñòàâëÿåò àëôàâèò àëãåáðû ïðîöåññîâ:
Act � �� �, (1)
ãäå � — ìíîæåñòâî àêòèâíîñòåé âçàèìîäåéñòâèÿ, � — ìíîæåñòâî âû÷èñ-
ëèòåëüíûõ àêòèâíîñòåé.
Ïðîöåññ, êàê ëîãè÷åñêàÿ ñòðóêòóðà, âñåãäà èìååò íà÷àëî, êîíåö è
òåêóùåå ñîñòîÿíèå. Íàïðèìåð, ïðîöåññ èçãîòîâëåíèÿ åäèíèöû ïðîäóêöèè
ñîñòîèò èç óñòàíîâëåíèÿ ïåðå÷íÿ êîìïëåêòóþùèõ ìàòåðèàëîâ, ñáîðêè
èçäåëèÿ, åãî íàëàäêè è çàâåðøàåòñÿ ïðîâåäåíèåì êîíòðîëüíîãî òåñòè-
ðîâàíèÿ. Ïîñëå ýòîãî èçäåëèå ìîæåò áûòü óïàêîâàíî è îòïðàâëåíî íà
ñêëàä ãîòîâîé ïðîäóêöèè. Êàæäûé èç ýòèõ ýòàïîâ ïðîöåññà P ñ çàäàííîé
ñòåïåíüþ äåòàëèçàöèè ìîæåò áûòü ïðåäñòàâëåí îäíîé èëè íåñêîëüêèìè
àêòèâíîñòÿìè:
P a a a nil: . . .�
1 2 3
, (2)
ãäå a
1
— àêòèâíîñòü óñòàíîâëåíèÿ ïåðå÷íÿ êîìïëåêòóþùèõ ìàòåðèàëîâ;
a
2
— àêòèâíîñòü ñáîðêè èçäåëèÿ; a
3
— àêòèâíîñòü íàëàäêè è ôèíàëüíîãî
òåñòèðîâàíèÿ; nil — ñëóæåáíàÿ àêòèâíîñòü, óäàëÿþùàÿ ðåñóðñû.
Àêòèâíîñòè îòäåëÿþòñÿ îäíà îò äðóãîé òî÷êîé è âûïîëíÿþòñÿ ñëåâà
íàïðàâî. Ïîñëåäíåé âñåãäà ñòîèò àêòèâíîñòü nil, ïðåäíàçíà÷åííàÿ äëÿ îñâî-
áîæäåíèÿ ðåñóðñîâ ïðîöåññà. Âûïîëíåííûå àêòèâíîñòè ïðîöåññà íå îòîáðà-
æàþòñÿ, ïîýòîìó òåêóùåé âñåãäà ÿâëÿåòñÿ êðàéíÿÿ ëåâàÿ àêòèâíîñòü. Èç ýòîãî
ïðàâèëà âûòåêàåò ïðåôèêñíàÿ çàïèñü ïðîöåññà �. �P , ñóòü êîòîðîé ñîñòîèò â
òîì, ÷òî îíà ïðåäñòàâëÿåò íåêîòîðûé ïðîöåññ P, âûïîëíÿþùèé ñíà÷àëà
âû÷èñëèòåëüíóþ àêòèâíîñòü �, à çàòåì âåäóùèé ñåáÿ êàê ïðîöåññ �P .
Ïðåäëàãàåìàÿ àëãåáðà ïðîöåññîâ äîïîëíèòåëüíî âêëþ÷àåò ñëåäóþ-
ùèå âèäû ïðåôèêñíûõ çàïèñåé: � .P, � t P. , a x P( ). , a x P( ). . Ïðåôèêñíàÿ
Ýêâèâàëåíòíîå ïðåäñòàâëåíèå ìîäåëåé ñëîæíûõ äèñêðåòíûõ ñèñòåì
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 1 5
çàïèñü � .P ïðåäñòàâëÿåò ñîáîé ïðîöåññ, êîòîðûé äîëæåí áûòü ñíà÷àëà
çàäåðæàí íà � åäèíèö ìîäåëüíîãî âðåìåíè, à çàòåì âûïîëíÿòüñÿ êàê ïðî-
öåññ P. Åñëè â õîäå ìîäåëèðîâàíèÿ íåîáõîäèìî ìåíÿòü âðåìÿ çàäåðæêè, òî
èñïîëüçóþò ïðåôèêñíóþ çàïèñü � t P. , ïîçâîëÿþùóþ óñòàíîâèòü âðåìÿ
çàäåðæêè �, ðàâíîå çíà÷åíèþ âûðàæåíèÿ t. Ïðåôèêñíàÿ çàïèñü a x P( ).
îòîáðàæàåò ââîä èíôîðìàöèè èç âíåøíåé ñðåäû. Ïðåôèêñíàÿ çàïèñü
a x P( ). çàäàåò âûâîä èíôîðìàöèè èç àêòèâíîãî ïðîöåññà âî âíåøíþþ
ñðåäó, çàòåì äàííûé ïðîöåññ âåäåò ñåáÿ êàê ïðîöåññ P. Àêòèâíîñòè a x( ) è
a x( ) íàçûâàþò êîìïëåìåíòàðíûìè àêòèâíîñòÿìè.
Ðàññìàòðèâàåìàÿ àëãåáðà ïðîöåññîâ ïîçâîëÿåò òàêæå âûïîëíÿòü ðÿä
ãðóïïîâûõ îïåðàöèé íàä àêòèâíîñòÿìè ïðîöåññà. Îñíîâíûìè èç íèõ ÿâ-
ëÿþòñÿ ïåðåèìåíîâàíèå è ñæàòèå. Îïåðàöèÿ ïåðåèìåíîâàíèÿ P K[ ] îáåñïå-
÷èâàåò ïåðåèìåíîâàíèå àêòèâíîñòåé ïðîöåññà P â ñîîòâåòñòâèè ñ ìíîæåñò-
âîì çíà÷åíèé ôóíêöèè K, à îïåðàöèÿ ñæàòèÿ P A\ áëîêèðóåò âûïîëíåíèå
àêòèâíîñòåé, âõîäÿùèõ âî ìíîæåñòâî A. Ýòè îïåðàöèè ïîçâîëÿþò ìîäè-
ôèöèðîâàòü ïîâåäåíèå ïðîöåññà â õîäå ìîäåëèðîâàíèÿ.
Èåðàðõè÷åñêèå ñâîéñòâà îïèñàíèÿ ìîäåëè îáåñïå÷èâàþòñÿ ââåäåíèåì
îïåðàöèé êëîíèðîâàíèÿ, âêëþ÷åíèÿ è ñîêðûòèÿ. Îïåðàöèÿ êëîíèðîâàíèÿ
k P
ïîðîæäàåò k èäåíòè÷íûõ ïðîöåññîâ P, êîòîðûå â õîäå ñàìîñòîÿ-
òåëüíîãî ðàçâèòèÿ ìîãóò âçàèìîäåéñòâîâàòü ìåæäó ñîáîé. Îïåðàöèÿ C P{ }
çàäàåò êîíñòðóêöèþ èç ïðîöåññîâ C è P, âêëþ÷àþùóþ ïðîöåññ P â êà-
÷åñòâå ñóáïðîöåññà ïðîöåññà C. Ñ ïîìîùüþ ýòîé îïåðàöèè ìîæíî ñòðîèòü
äðåâîâèäíûå ñòðóêòóðû ïðîöåññîâ. Îïåðàöèÿ ñîêðûòèÿ � P C( ) ïîçâîëÿåò
ñêðûâàòü âûïîëíåíèå ñóáïðîöåññà P, âõîäÿùåãî â ãëàâíûé ïðîöåññ C,
ïóòåì çàìåíû åãî íåêîòîðîé âû÷èñëèòåëüíîé àêòèâíîñòüþ �.
Åñëè ñ ïîìîùüþ àëãåáðû ïðîöåññîâ íóæíî îïèñàòü ïîâåäåíèå ïàðàë-
ëåëüíîé ñèñòåìû, òî ñîîòâåòñòâóþùàÿ ìîäåëü áóäåò ñîäåðæàòü ïàðàëëåëü-
íûå ïðîöåññû.  äàííîé ñèòóàöèè àêòóàëüíîé ñòàíîâèòñÿ çàäà÷à îïðåäå-
ëåíèÿ ïðàâèë âçàèìíîãî ñîñóùåñòâîâàíèÿ ýòèõ ïðîöåññîâ. Òàêèå ôóíêöèè
âûïîëíÿþò îïåðàöèè âûáîðà, ïàðàëëåëüíîé êîìïîçèöèè è âçàèìîäåéñò-
âèÿ. Åñëè íåîáõîäèìî äàòü ïðàâî äàëüíåéøåãî ðàçâèòèÿ òîëüêî îäíîìó èç
ãðóïïû ïàðàëëåëüíûõ ïðîöåññîâ, òî äëÿ âûïîëíåíèÿ ýòîãî äåéñòâèÿ
àêòóàëüíîé ÿâëÿåòñÿ îïåðàöèÿ âûáîðà.
 çàâèñèìîñòè îò êðèòåðèÿ âûáîðà áóäåì ðàññìàòðèâàòü íåäåòåðìè-
íèðîâàííûé, óïðàâëÿåìûé è âåðîÿòíîñòíûé âûáîð. Íåäåòåðìèíèðîâàí-
íûé âûáîð Pi
i I�
� îáåñïå÷èâàåò âûáîð îäíîãî èç ïðîöåññîâ Pi â ìîìåíò
âðåìåíè, íàçûâàåìûé ìîìåíòîì âûáîðà. Óïðàâëÿåìûé âûáîð v Pi i
i I
!
�
�
ââåäåí äëÿ ðàçðåøåíèÿ äàëüíåéøåãî ðàçâèòèÿ òîëüêî òîìó ïðîöåññó, äëÿ
Á. Á. Íåñòåðåíêî, Ì. À. Íîâîòàðñêèé
6 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 1
êîòîðîãî ñóùåñòâóåò ñîîòâåòñòâóþùàÿ ëîãè÷åñêàÿ ïåðåìåííàÿ v truei � .
Âåðîÿòíîñòíûé âûáîð wi
i I�
� # Pi äëÿ êàæäîãî èç ïðîöåññîâ Pi ïðîèñõîäèò ñ
âåðîÿòíîñòüþ wi ïðè óñëîâèè, ÷òî w w wi I1
1
�... ... .
Îïåðàöèþ ïàðàëëåëüíîé êîìïîçèöèè P Q C... ïðîöåññîâ P, Q è C
èñïîëüçóþò â ñëó÷àÿõ, êîãäà íåò íåîáõîäèìîñòè àêöåíòèðîâàòü âíèìàíèå
íà õàðàêòåðå âçàèìîäåéñòâèÿ ìåæäó äàííûìè ïðîöåññàìè, èëè êîãäà òà-
êîãî âçàèìîäåéñòâèÿ íå ñóùåñòâóåò. Äëÿ áîëåå äåòàëüíîé ñïåöèôèêàöèè
âçàèìîäåéñòâèÿ îïðåäåëèì, ÷òî ìåæäó îòäåëüíûì ïðîöåññîì è ïàðàë-
ëåëüíîé êîìïîçèöèåé ïðîöåññîâ ìîæåò ïðîèñõîäèòü óïðàâëÿåìàÿ ïåðå-
äà÷à, ñèíõðîííîå âçàèìîäåéñòâèå èëè àñèíõðîííîå âçàèìîäåéñòâèå.
Óïðàâëÿåìîé ïåðåäà÷åé îò ïðîöåññà P ê ïàðàëëåëüíîé êîìïîçèöèè
P Q C... áóäåì íàçûâàòü îïåðàöèþ P Q C� ... , êîòîðàÿ îáåñïå÷èâàåò ïå-
ðåäà÷ó èíôîðìàöèè îò ïðîöåññà P êî âñåì ïðîöåññàì ïàðàëëåëüíîé êîì-
ïîçèöèè Q C... â ìîìåíò ñâåðøåíèÿ àêòèâíîñòè âûâîäà â ïðîöåññå P.
Ñèíõðîííîå âçàèìîäåéñòâèå ïðîöåññà P è ïàðàëëåëüíîé êîìïîçèöèè
Q C... ñâîäèòñÿ ê îïåðàöèè P Q C� ... , îáåñïå÷èâàþùåé îáìåí èíôîð-
ìàöèåé ìåæäó ïðîöåññîì è ïàðàëëåëüíîé êîìïîçèöèåé Q C... ïðè óñëî-
âèè îäíîâðåìåííîãî âûïîëíåíèÿ êîìïëåìåíòàðíûõ àêòèâíîñòåé â ïðîöåñ-
ñå P è â ïðîöåññàõ óïîìÿíóòîé ïàðàëëåëüíîé êîìïîçèöèè. Àñèíõðîííîå
âçàèìîäåéñòâèå P Q C�� ... îòëè÷àåòñÿ îò ñèíõðîííîãî òåì, ÷òî äëÿ ïðèå-
ìà èëè ïåðåäà÷è èíôîðìàöèè íå òðåáóåòñÿ îæèäàòü ìîìåíòà âîçíèê-
íîâåíèÿ êîìïëåìåíòàðíûõ àêòèâíîñòåé.
Âàæíîé ñîñòàâëÿþùåé ñèíòàêñèñà ïðåäëàãàåìîé àëãåáðû ïðîöåññîâ
ÿâëÿþòñÿ òàêæå îïåðàöèè ïîâòîðåíèÿ àêòèâíîñòåé, âõîäÿùèõ â ñîñòàâ
ïðîöåññà P. Ê òàêèì îïåðàöèÿì îòíåñåì îïåðàöèè ðåêóðñèè è öèêëà.
Îïåðàöèÿ ðåêóðñèè � �( )X P îáåñïå÷èâàåò ïîâòîðåíèå ýêçåìïëÿðà ïðî-
öåññà P ïðèñâîåíèåì åãî ïåðåìåííîé X. Äîïîëíèòåëüíî ââåäåííàÿ îïåðà-
öèÿ öèêëà cycle x X P[ ]( )� îòëè÷àåòñÿ îò îïåðàöèè ðåêóðñèè òåì, ÷òî ÷èñëî
ïîâòîðåíèé èçâåñòíî äî íà÷àëà îïåðàöèè è îïðåäåëÿåòñÿ çíà÷åíèåì ïåðå-
ìåííîé öèêëà x.
Èñïîëüçóÿ ïðåôèêñíóþ çàïèñü è îïèñàííûå îïåðàöèè íàä ïðîöåñ-
ñàìè, ìîæíî çàäàâàòü èìèòàöèîííóþ ìîäåëü ñëîæíîé äèñêðåòíîé ñèñ-
òåìû â âèäå óðàâíåíèé àëãåáðû ïðîöåññîâ. Ýòè óðàâíåíèÿ ïîçâîëÿþò
îïèñûâàòü âñå ìíîæåñòâî ñöåíàðèåâ èìèòàöèîííîãî ìîäåëèðîâàíèÿ, êî-
òîðûå ìîãóò âîçíèêíóòü â çàâèñèìîñòè îò ñèòóàöèè, îïðåäåëÿåìîé õàðàê-
òåðîì ðàáî÷åé íàãðóçêè. Òàêîå îïèñàíèå èìååò áåçóñëîâíûå ïðåèìóùåñò-
âà â ãèáêîñòè, êîìïàêòíîñòè è íàãëÿäíîñòè ïî ñðàâíåíèþ ñ èçâåñòíûìè
ïîäõîäàìè. Îäíàêî â ýòîì ñëó÷àå ìåíåå î÷åâèäíûìè ñòàíîâÿòñÿ âîïðîñû
ýêâèâàëåíòíîñòè îïèñàíèÿ ìîäåëè è îáúåêòà ìîäåëèðîâàíèÿ. Ïîýòîìó
Ýêâèâàëåíòíîå ïðåäñòàâëåíèå ìîäåëåé ñëîæíûõ äèñêðåòíûõ ñèñòåì
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 1 7
íåîáõîäèìû äîïîëíèòåëüíûå èññëåäîâàíèÿ óñëîâèé âîçíèêíîâåíèÿ äàí-
íîé ýêâèâàëåíòíîñòè.
Ïîâåäåí÷åñêàÿ ýêâèâàëåíòíîñòü. Âàæíûì âîïðîñîì â àëãåáðå ïðî-
öåññîâ ÿâëÿåòñÿ îïðåäåëåíèå óñëîâèé, ïðè êîòîðûõ ìîæíî ñêàçàòü, ÷òî
îäèí ïðîöåññ äåìîíñòðèðóåò ýêâèâàëåíòíîå ïîâåäåíèå ïî îòíîøåíèþ ê
äðóãîìó ïðîöåññó. Äëÿ îïðåäåëåíèÿ ýòèõ óñëîâèé ââåäåíî ïîíÿòèå ïîâå-
äåí÷åñêîé ýêâèâàëåíòíîñòè, îñíîâàííîå íà ýêâèâàëåíòíîì îòíîøåíèè
ñîñòîÿíèé. Ïîä ñîñòîÿíèåì ñèñòåìû áóäåì ïîíèìàòü ñîâîêóïíîñòü çíà÷å-
íèé ïàðàìåòðîâ, óñòàíîâëåííûõ â ðåçóëüòàòå ñâåðøåíèÿ àêòèâíîñòè.
Îïðåäåëåíèå 1. Ïóñòü P — ïðîöåññ, à áèíàðíîå îòíîøåíèå R íà P
ïðåäñòàâëÿåò ñîáîé ìíîæåñòâî P P
ñ ñîñòîÿíèÿìè ( , )p q R� èëè pRq.
Òîãäà ýêâèâàëåíòíûì îòíîøåíèåì R íà P áóäåì íàçûâàòü áèíàðíîå îòíî-
øåíèå, ñîîòâåòñòâóþùåå òàêèì óñëîâèÿì:
R äîëæíî áûòü ðåôëåêñèâíûì, ò. å. pRp, qRq ïðè p q P, � ;
R äîëæíî áûòü ñèììåòðè÷íûì, ò. å. èç pRq ñëåäóåò qRp ïðè p q P, � ;
R äîëæíî áûòü òðàíçèòèâíûì, ò. å. èç pRq è qRz ñëåäóåò pRz ïðè
p q z P, , � .
Óñëîâèå ðåôëåêñèâíîñòè áèíàðíîãî îòíîøåíèÿ îáåñïå÷èâàåò âíóòðåí-
íþþ íåïðîòèâîðå÷èâîñòü ïðîöåññîâ, ýêâèâàëåíòíî îòîáðàæàþùèõ âíóòðåí-
íå íåïðîòèâîðå÷èâûå ïðîöåññû. Óñëîâèå òðàíçèòèâíîñòè ñîõðàíÿåò ýêâè-
âàëåíòíîñòü âî âðåìÿ ïîøàãîâîé ðåàëèçàöèè ìîäåëè â ñîîòâåòñòâèè ñ åå
îïèñàíèåì. Åñëè îïèñàíèå çàäàíî â âèäå ôðàãìåíòîâ ñèñòåìû, òî íà îñíî-
âàíèè ñâîéñòâa òðàíçèòèâíîñòè ýêâèâàëåíòíîå îòíîøåíèå ñîâîêóïíîñòè òà-
êèõ ôðàãìåíòîâ áóäåò ýêâèâàëåíòíî èñõîäíîìó îïèñàíèþ. Äëÿ òîãî ÷òîáû
îáúåêò ìîäåëèðîâàíèÿ è åãî îïèñàíèå áûëè âçàèìíî ïîäîáíûìè, íåîáõî-
äèìî òàêæå âûïîëíåíèå ïðèíöèïà ñèììåòðè÷íîñòè.
Èçâåñòíî ìíîãî îïðåäåëåíèé ïîâåäåí÷åñêîé ýêâèâàëåíòíîñòè [5],
àêòóàëüíîñòü êîòîðûõ çàâèñèò îò öåëè ìîäåëèðîâàíèÿ. Èõ èñïîëüçóþò êàê
äëÿ àíàëèçà ïàðàëëåëüíûõ ñèñòåì, òàê è äëÿ îòîáðàæåíèÿ àñïåêòîâ ïîâå-
äåíèÿ êîìïîíåíòîâ ñèñòåì. Ïðîñòåéøèé âèä ïîâåäåí÷åñêîé ýêâèâàëåíò-
íîñòè ìîæåò áûòü ñâåäåí ê ñðàâíåíèþ ïîñëåäîâàòåëüíîñòåé àêòèâíîñòåé,
âõîäÿùèõ â ñîñòàâ ñðàâíèâàåìûõ ïðîöåññîâ. Òàêèå ïîñëåäîâàòåëüíîñòè
íàçûâàþò òðàññàìè èëè ïðîòîêîëàìè àêòèâíîñòåé [6].
Äëÿ ôîðìàëüíîãî îïðåäåëåíèÿ ïîâåäåí÷åñêîé ýêâèâàëåíòíîñòè ïðåä-
ñòàâèì ìîäåëü â âèäå ìàðêèðîâàííîé ñèñòåìû ñ ïåðåõîäàìè: ( , ,� A
{ })
a a A��� � , ãäå � — ìíîæåñòâî ïðîöåññîâ, A — ìíîæåñòâî àêòèâíîñòåé
è
a
��� — ìíîæåñòâî ïåðåõîäîâ ïðè
a A��� �
� �.  äàííîì ñëó÷àå
îïèñàíèå ïðîöåññà � ïðåäñòàâëåíî ïîñëåäîâàòåëüíîñòüþ ñîñòîÿíèé ñèñ-
òåìû íà ìîìåíò íà÷àëà âûïîëíåíèÿ àêòèâíîñòåé, ïðèíàäëåæàùèõ ìíî-
æåñòâó àêòèâíîñòåé A.
Á. Á. Íåñòåðåíêî, Ì. À. Íîâîòàðñêèé
8 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 1
Îáîçíà÷èì ÷åðåç U ìíîæåñòâî ïîñëåäîâàòåëüíîñòåé, ýëåìåíòàìè êî-
òîðûõ ÿâëÿþòñÿ àêòèâíîñòè a Ai � ïðè 1� �i n, A n� . Åñëè â ìàðêèðî-
âàííîé ñèñòåìå ñ ïåðåõîäàìè ( , ,{ })� A a Aa
��� � ñóùåñòâóåò ïîñëåäîâà-
òåëüíîñòü àêòèâíîñòåé u a a Un� �
1
... , U � �, êîòîðàÿ âåäåò ê ñóùåñòâîâà-
íèþ ïåðåõîäà q qu
��� � ïðè óñëîâèè, ÷òî ñóùåñòâóåò ïîñëåäîâàòåëüíîñòü
ïåðåõîäîâ q qi
a
i
i
� ��
1
1
, ãäå 0 1� � �i n , q q�
0
, � �q qn , òî u áóäåì íàçûâàòü
òðàññîé äëÿ ñîñòîÿíèÿ q.
Îïðåäåëåíèå 2. Ïóñòü â ìàðêèðîâàííîé ñèñòåìå ñ ïåðåõîäàìè
( , ,{ })� A a Aa
��� � ìíîæåñòâà S p( ) è S q( ) ÿâëÿþòñÿ ìíîæåñòâàìè âñåõ äî-
ïóñòèìûõ òðàññ äëÿ ñîñòîÿíèé p è q. Òîãäà äëÿ äàííûõ ñîñòîÿíèé ñóùåñòâóåò:
ñòðîãàÿ ïîâåäåí÷åñêàÿ ýêâèâàëåíòíîñòü p q� ïðè óñëîâèè, ÷òî S p( ) �
� S q( ) è A Act� ;
ñëàáàÿ ïîâåäåí÷åñêàÿ ýêâèâàëåíòíîñòü p q� ïðè óñëîâèè, ÷òî S p( ) �
� S q( ) è A � �.
Ïîñêîëüêó ñîñòîÿíèå ÿâëÿåòñÿ áàçîâûì ýëåìåíòîì ìàðêèðîâàííîé
ñèñòåìû ñ ïåðåõîäàìè, ïîíÿòèå ïîâåäåí÷åñêîé ýêâèâàëåíòíîñòè ìîæåò
áûòü ðàñïðîñòðàíåíî íà âñþ ñèñòåìó.
Óïîìÿíóòîå îïðåäåëåíèå ýêâèâàëåíòíîñòè ïîâåäåíèÿ ìîæåò áûòü
èñïîëüçîâàíî òîëüêî äëÿ ñðàâíåíèÿ ìîäåëåé ñèñòåì, ïðåäñòàâëåííûõ äå-
òåðìèíèðîâàííûìè îïåðàòîðàìè, ò. å. òàêèìè, êîòîðûå íå ñîäåðæàò íå-
îïðåäåëåííîñòåé. Ïðîáëåìà ñîñòîèò â òîì, ÷òî íàëè÷èå îäèíàêîâûõ òðàññ
â íåäåòåðìèíèðîâàííûõ ìîäåëÿõ íå ãàðàíòèðóåò ýêâèâàëåíòíîãî ïîâå-
äåíèÿ. Íàïðèìåð, ïóñòü ðàçâèòèå ïðîöåññîâ b a a nil a a nil: . . . .�
0 1 0 2
è c:�
�
a a nil a nil
0 1 2
.( . . ) íà÷èíàåòñÿ ñ ñîñòîÿíèé p è r, êàê ïîêàçàíî íà ðèñ. 1.
Òîãäà ìîäåëè, îïèñûâàåìûå ïðîöåññàìè b è c, èìåþò îäèíàêîâûå òðàññû:
S p S r a a nil a a nil( ) ( ) { . . } { . . }� � �
0 1 0 2
. Îäíàêî äëÿ ïðîöåññà b ïîñëå àêòèâ-
Ýêâèâàëåíòíîå ïðåäñòàâëåíèå ìîäåëåé ñëîæíûõ äèñêðåòíûõ ñèñòåì
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 1 9
p
r
Ïðîöåññ b
Ïðîöåññ c
p
1 p
3
p
4
p
2
r
1
r
3
r
4
r
2
a
0
a
0
a
0 a
1
a
1
a
2
a
2
nil
nil
nil
nil
Ðèñ. 1. Íåäåòåðìèíèðîâàííûå ìîäåëè ñ îäèíàêîâûìè òðàññàìè
íîñòè a
0
âñåãäà âûïîëíÿåòñÿ ÷åòêî îïðåäåëåííàÿ àêòèâíîñòü, â òî âðåìÿ
êàê äëÿ ïðîöåññà c ïðîèñõîäèò íåäåòåðìèíèðîâàííûé âûáîð ñëåäóþùåé
àêòèâíîñòè. Ïîýòîìó âîçíèêàåò íåîáõîäèìîñòü óòî÷íèòü ïîíÿòèå ýêâè-
âàëåíòíîñòè.
Ñòðîãîå âçàèìíîå ïîäîáèå. Âçàèìíîå ïîäîáèå, îñíîâàííîå íå òîëüêî
íà òðåáîâàíèè ýêâèâàëåíòíîñòè òðàññ, íî è íà äîñòèæåíèè îäèíàêîâûõ
àêòèâíîñòåé ïîñëå âûïîëíåíèÿ òåêóùèõ àêòèâíîñòåé, âïåðâûå áûëî ïðåä-
ëîæåíî â [7].  ñëó÷àå âçàèìíîãî ïîäîáèÿ ñ ðàçâåòâëåíèåì äëÿ ýêâèâà-
ëåíòíîñòè ñîîòâåòñòâóþùèõ ïðîöåññîâ äîáàâëÿåòñÿ óñëîâèå ïðîõîæäåíèÿ
îäèíàêîâûõ ïðîìåæóòî÷íûõ àêòèâíîñòåé. Ïðåèìóùåñòâî ïðèìåíåíèÿ
âçàèìíîãî ïîäîáèÿ ñîñòîèò â âîçìîæíîñòè ññûëêè íà îïðåäåëåíèå ïî-
äîáèÿ, èñõîäÿ èç îáùåé òåîðèè ñèñòåì, è ïîñòðîåíèÿ äîêàçàòåëüñòâà íà
îñíîâå ýòîãî îïðåäåëåíèÿ.
Îïðåäåëåíèå 3. Ïóñòü â ìàðêèðîâàííîé ñèñòåìå ñ ïåðåõîäàìè
( , ,{ })� A a Aa
��� � ñóùåñòâóåò îòíîøåíèå R �
� � è ïðîöåññû P Q, � � ñ
äîïóñòèìûìè ñîñòîÿíèÿìè p p P, �� , q q Q, �� ïðè( , )p q R� . Òîãäà, åñëè äëÿ
ïðîèçâîëüíîé àêòèâíîñòè a äëÿ êàæäîãî ïåðåõîäà p pa
��� � ñóùåñòâóåò
ñîñòîÿíèå �q òàêîå, ÷òî q qa
��� � ïðè ( , )� � �p q R, a äëÿ êàæäîãî ïåðåõîäà
q qa
��� � ñóùåñòâóåò ñîñòîÿíèå �p òàêîå, ÷òî p pa
��� � ïðè ( , )� � �p q R, òî îòíî-
øåíèå R áóäåì íàçûâàòü ñòðîãèì âçàèìíûì ïîäîáèåì, åñëè a Act� . Ñîñ-
òîÿíèÿ p è q áóäåì íàçûâàòü ñòðîãî âçàèìíî ïîäîáíûìè p q~ , åñëè
ñóùåñòâóåò îòíîøåíèå R, êîòîðîå ñîäåðæèò ( , )p q ïðè a Act� .
Äîêàæåì îñíîâíûå ñâîéñòâà ñòðîãîãî âçàèìíîãî ïîäîáèÿ äëÿ ìàðêè-
ðîâàííîé ñèñòåìû ñ ïåðåõîäàìè, îñíîâûâàÿñü íà ïîëîæåíèÿõ îáùåé òåî-
ðèè ñèñòåì.
Òåîðåìà 1. Â ìàðêèðîâàííîé ñèñòåìå ñ ïåðåõîäàìè ( , ,{ })� A a Aa
��� �
ñòðîãîå âçàèìíîå ïîäîáèå ÿâëÿåòñÿ ýêâèâàëåíòíûì îòíîøåíèåì.
Ä î ê à ç à ò å ë ü ñ ò â î. Ïóñòü ìíîæåñòâî ïðîöåññîâ � ìàðêèðîâàííîé
ñèñòåìû ñ ïåðåõîäàìè ñîäåðæèò ïðîöåññû P Q, � �, êàæäûé èç êîòîðûõ
âêëþ÷àåò ñîñòîÿíèÿ p p P, �� è q q Q, �� . Äëÿ òîãî ÷òîáû ñîñòîÿíèÿ p q~
ñîîòâåòñòâîâàëè ýêâèâàëåíòíîìó îòíîøåíèþ íà R, ( , )p q R� , íåîáõîäèìî, â
ñîîòâåòñòâèè ñ îïðåäåëåíèåì 1, äîêàçàòü åãî ðåôëåêñèâíîñòü, ñèììåòðè÷-
íîñòü è òðàíçèòèâíîñòü. Èñõîäÿ èç îïðåäåëåíèÿ 3, ââåäåì çàìåíó �p íà p è �q
íà q. Òîãäà ïîëó÷èì ñèñòåìó, â êîòîðîé ñóùåñòâóåò àêòèâíîñòü a, ÿâëÿþùàÿ-
ñÿ ïðè÷èíîé òîæäåñòâåííûõ ïåðåõîäîâ ìåæäó ñîñòîÿíèÿìè, à èìåííî:
p pa
��� è q qa
��� . Î÷åâèäíî, ÷òî â òàêîé ñèñòåìå ïîäìíîæåñòâàìè ìíî-
æåñòâà R áóäóò áèíàðíûå îòíîøåíèÿ: I p p p Pp � �{( , )| }, I q q q Qq � �{( , )| }.
Ïîñêîëüêó I I Rp q, � ÿâëÿþòñÿ îòíîøåíèÿìè èäåíòè÷íîñòè, îíè ðåô-
ëåêñèâíû. Äëÿ ñèììåòðè÷íîñòè p q~ íåîáõîäèìî äîêàçàòü, ÷òî ñóùåñò-
âóåò q p~ . Èñõîäÿ èç óñëîâèÿ ñòðîãîãî âçàèìíîãî ïîäîáèÿ ( , )p q R� . Òîãäà
Á. Á. Íåñòåðåíêî, Ì. À. Íîâîòàðñêèé
10 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 1
R q p p q R�
� �
1
{( , )|( , ) }. Î÷åâèäíî, ÷òî R �1
òàêæå ÿâëÿåòñÿ îòíîøåíèåì
âçàèìíîãî ïîäîáèÿ. Îòñþäà p q~ è q p~ âçàèìíî ñèììåòðè÷íû.
Åñëè ñòðîãîå âçàèìíîå ïîäîáèå òðàíçèòèâíî, òî ñòðîãèå âçàèìíûå
ïîäîáèÿ ñîñòîÿíèé p q~ è q z~ ïðåäîïðåäåëÿþò p z~ . Ñîãëàñíî óñëîâèþ
p q~ , ïîýòîìó ñîîòâåòñòâåííî ( , )p q R� �, ïîñêîëüêó q z~ , ( , )q z R� ��. Ðàñ-
ñìîòðèì áèíàðíîå îòíîøåíèå R p z p q R q z R� � � � ��{( , )|( , ) ( , ) } äëÿ íåêîòî-
ðîãî q. Ïîñêîëüêó �R è ��R — îòíîøåíèÿ ñòðîãîãî âçàèìíîãî ïîäîáèÿ, R
òàêæå ÿâëÿåòñÿ îòíîøåíèåì ñòðîãîãî âçàèìíîãî ïîäîáèÿ. Îòñþäà âûòå-
êàåò, ÷òî ñòðîãîå âçàèìíîå ïîäîáèå òðàíçèòèâíî. Òåîðåìà äîêàçàíà.
Òåîðåìà 2. Íàèáîëüøèì ñòðîãèì âçàèìíûì ïîäîáèåì áóäåì íàçûâàòü
îáúåäèíåíèå âñåõ äîïóñòèìûõ îòíîøåíèé âçàèìíîãî ïîäîáèÿ. Òîãäà â
ìàðêèðîâàííîé ñèñòåìå ñ ïåðåõîäàìè( , ,{ })� A a Aa
��� � ñòðîãîå âçàèìíîå
ïîäîáèå ÿâëÿåòñÿ íàèáîëüøèì ñòðîãèì âçàèìíûì ïîäîáèåì.
Ä î ê à ç à ò å ë ü ñ ò â î. Ðàññìîòðèì, êàê è â ïðåäøåñòâóþùåì ñëó÷àå,
ïðîöåññû P Q, � �, êàæäûé èç êîòîðûõ âêëþ÷àåò ñîñòîÿíèÿ p p P, �� è
q q Q, �� . Èñõîäÿ èç óñëîâèÿ òåîðåìû, �� �{ }R , ãäå R — îòíîøåíèå âçàèì-
íîãî ïîäîáèÿ. Èòàê, íåîáõîäèìî äîêàçàòü, ÷òî �{ }R òàêæå ÿâëÿåòñÿ îòíî-
øåíèåì âçàèìíîãî ïîäîáèÿ. Äëÿ ýòîãî äîëæíû âûïîëíÿòüñÿ ñëåäóþùèå
óñëîâèÿ:
åñëè ( , ) { }p q R�� è p pa
��� �, òî ñóùåñòâóåò ñîñòîÿíèå �q òàêîå, ÷òî
q qa
��� � ïðè ( , ) { }� � �p q R� ;
åñëè ( , ) { }p q R�� è q qa
��� �, òî ñóùåñòâóåò ñîñòîÿíèå �p òàêîå, ÷òî
p pa
��� � ïðè ( , ) { }� � �p q R� .
Ïóñòü ( , ) { }p q R�� , òîãäà ñóùåñòâóåò òàêîå îòíîøåíèå âçàèìíîãî ïî-
äîáèÿ R, ÷òî ( , )p q R� . Ïîñêîëüêó R — îòíîøåíèå âçàèìíîãî ïîäîáèÿ è
p pa
��� �, ñóùåñòâóåò ñîñòîÿíèå �q òàêîå, ÷òî q qa
��� � ïðè ( , )� � �p q R. Ñîîò-
âåòñòâåííî ñâîéñòâàì ñèììåòðè÷íîñòè äëÿ q qa
��� � ñóùåñòâóåò ñîñòîÿíèå
�p òàêîå, ÷òî p pa
��� � ïðè ( , )� � �p q R. Íî ïàðà ñîñòîÿíèé ( , ) { }� � �p q R� , ò. å.
ñòðîãîå âçàèìíîå ïîäîáèå, âêëþ÷àåò âñå îòíîøåíèÿ âçàèìíîãî ïîäîáèÿ è
ÿâëÿåòñÿ íàèáîëüøèì ñòðîãèì âçàèìíûì ïîäîáèåì. Òåîðåìà äîêàçàíà.
Òåîðåìà 3. Â ìàðêèðîâàííîé ñèñòåìå ñ ïåðåõîäàìè ( , ,{ })� A a Aa
��� � ,
âêëþ÷àþùåé ïðîöåññû P Q, � � ñ äîïóñòèìûìè ñîñòîÿíèÿìè p p P, �� è
q q Q, �� , äëÿ ïðîèçâîëüíîé àêòèâíîñòè a äâà ñîñòîÿíèÿ p q~ òîãäà è òîëü-
êî òîãäà, êîãäà äëÿ ïåðåõîäà p pa
��� � ñóùåñòâóåò ïåðåõîä q qa
��� � òàêîé, ÷òî
� �p q~ , à äëÿ ïåðåõîäà q qa
��� �ñóùåñòâóåò ïåðåõîä p pa
��� �òàêîé, ÷òî � �p q~ .
Ä î ê à ç à ò å ë ü ñ ò â î. Ïîñêîëüêó, â ñîîòâåòñòâèè ñ îïðåäåëåíèåì
òðàññ äëÿ ñîñòîÿíèé â ìàðêèðîâàííûõ ñèñòåìàõ ñ ïåðåõîäàìè, äëÿ êàæ-
äîãî ïåðåõîäà p pa
��� � ñóùåñòâóåò ñîñòîÿíèå �q òàêîå, ÷òî q qa
��� � ïðè
Ýêâèâàëåíòíîå ïðåäñòàâëåíèå ìîäåëåé ñëîæíûõ äèñêðåòíûõ ñèñòåì
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 1 11
( , )� � �p q R, äëÿ ïðîèçâîëüíîé àêòèâíîñòè a ñóùåñòâóþò äâà ñîñòîÿíèÿ
p q~ ïðè óñëîâèè, ÷òî äëÿ ïåðåõîäà p pa
��� � ñóùåñòâóåò ïåðåõîä q qa
��� �
òàêîé, ÷òî � �p q~ . Àíàëîãè÷íî, åñëè äëÿ êàæäîãî ïåðåõîäà q qa
��� � ñóùåñò-
âóåò ñîñòîÿíèå �p òàêîå, ÷òî p pa
��� � ïðè ( , )� � �p q R, äëÿ ïðîèçâîëüíîé
àêòèâíîñòè a ñóùåñòâóþò äâà ñîñòîÿíèÿ p q~ ïðè óñëîâèè, ÷òî äëÿ ïåðå-
õîäà q qa
��� � ñóùåñòâóåò ïåðåõîä p pa
��� � òàêîé, ÷òî � �p q~ .
Èòàê, ïðÿìîå óòâåðæäåíèå äàííîé òåîðåìû íåïîñðåäñòâåííî âûòåêàåò
èç îïðåäåëåíèÿ ñòðîãîãî âçàèìíîãî ïîäîáèÿ. Äëÿ äîêàçàòåëüñòâà îáðàò-
íîãî óòâåðæäåíèÿ íåîáõîäèìî ïîêàçàòü, ÷òî ñòðîãîå âçàèìíîå ïîäîáèå
p q~ ñîäåðæèò îòíîøåíèå ( , )p q . Äîêàçàòåëüñòâî óïîìÿíóòîãî ôàêòà áàçè-
ðóåòñÿ íà êîíñòðóêòèâíîì ïîäõîäå ê ôîðìèðîâàíèþ ìíîæåñòâà R îòíîøå-
íèé âçàèìíîãî ïîäîáèÿ. Äëÿ äîêàçàòåëüñòâà p q~ ïðåæäå âñåãî íåîáõîäè-
ìî âêëþ÷èòü âî ìíîæåñòâî R îòíîøåíèå ( , )p q , ïîñêîëüêó äëÿ òîãî ÷òîáû
ïðÿìîå äîêàçàòåëüñòâî áûëî êîððåêòíûì, êàæäîìó ïåðåõîäó p pa
��� � èç
ñîñòîÿíèÿ p äîëæåí ñîîòâåòñòâîâàòü ïåðåõîä q qa
��� � èç ñîñòîÿíèÿ q äëÿ
íåêîòîðîãî ñîñòîÿíèÿ �q òàêîãî, ÷òî ( , )� � �p q R. Ñôîðìèðóåì ñíà÷àëà ìíî-
æåñòâî R ïóòåì îáúåäèíåíèÿ âñåõ îòíîøåíèé âçàèìíîãî ïîäîáèÿ â ìàðêè-
ðîâàííîé ñèñòåìå ñ ïåðåõîäàìè ( , ,{ })� A a Aa
��� � . Ïîñêîëüêó â ñîîò-
âåòñòâèè ñ òåîðåìîé 2 ñòðîãîå âçàèìíîå ïîäîáèå ÿâëÿåòñÿ íàèáîëüøèì
âçàèìíûì ïîäîáèåì, R p q R� �( , ) . Ñëåäîâàòåëüíî, ìíîæåñòâî îòíîøåíèé
R ñîäåðæèò ýëåìåíò ( , )p q . Òåîðåìà äîêàçàíà.
Îïèðàÿñü íà òåîðåìó 2, ìîæíî ñäåëàòü âûâîä î òîì, ÷òî â õîäå ýâî-
ëþöèè ñòðîãî âçàèìíî ïîäîáíûå ñèñòåìû îñòàþòñÿ ñòðîãî âçàèìíî ïîäîá-
íûìè. Íà ýòîì ôàêòå áàçèðóåòñÿ îïðåäåëåíèå ñòðîãî âçàèìíî ïîäîáíûõ
ïðîöåññîâ.
Ãðàôè÷åñêîå èçîáðàæåíèå ñòðîãîãî âçàèìíîãî ïîäîáèÿ ñîñòîÿíèé p è
q ïîêàçàíî íà ðèñ. 2, a.
Îïðåäåëåíèå 4. Äâà ïðîöåññà, P è Q, íàçûâàþò ñòðîãî âçàèìíî ïîäîá-
íûìè è îáîçíà÷àþò P Q~ òîëüêî ïðè óñëîâèè, åñëè äëÿ ïðîèçâîëüíîé
àêòèâíîñòè a ñóùåñòâóåò îòíîøåíèå ñòðîãîãî âçàèìíîãî ïîäîáèÿ R òàêîå,
÷òî ïðîöåññû P è Q ñòðîãî âçàèìíî ïîäîáíû, ò. å. PRQ (ðèñ. 2, á).
Á. Á. Íåñòåðåíêî, Ì. À. Íîâîòàðñêèé
12 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 1
a a
a á
a a
p Pp' P'
q Q
~ ~ ~~
q' Q'
Ðèñ. 2. Ñòðîãîå âçàèìíîå ïîäîáèå ñîñòîÿíèé p è q (à) è ïðîöåññîâ P è Q (á)
Ìû ðàññìîòðåëè îïðåäåëåíèå êëàññè÷åñêîãî ñòðîãîãî âçàèìíîãî ïî-
äîáèÿ è åãî ñâîéñòâà. Ñîãëàñíî îïðåäåëåíèþ 3 îñîáåííîñòü äàííîãî âèäà
ýêâèâàëåíòíîñòè ñîñòîèò â òîì, ÷òî îíà âûïîëíÿåòñÿ äëÿ âñåõ áåç èñêëþ-
÷åíèÿ ñðàâíèâàåìûõ ñîñòîÿíèé. Íî íà ïðàêòèêå èíîãäà âàæíî ðàññìàò-
ðèâàòü ñòðîãîå âçàèìíîå ïîäîáèå òîëüêî ïîäìíîæåñòâ ïðîöåññîâ, åñëè,
íàïðèìåð, èçâåñòíî, ÷òî îñòàëüíûå ïðîöåññû ñðàâíèâàåìûõ ñèñòåì ñîîò-
âåòñòâóþò óñëîâèÿì ñòðîãîãî âçàèìíîãî ïîäîáèÿ.
Îïðåäåëåíèå 5. Ïóñòü â ìàðêèðîâàííîé ñèñòåìå ñ ïåðåõîäàìè
( , ,{ })� A a Aa
��� � ñóùåñòâóåò îòíîøåíèå S �
� � è ïðîöåññû P Q, � � ñ
äîïóñòèìûìè ñîñòîÿíèÿìè p p P, �� , q q Q, �� ïðè( , )p q S� . Òîãäà, åñëè äëÿ
ïðîèçâîëüíîé àêòèâíîñòè a äëÿ êàæäîãî ïåðåõîäà p pa
��� � ñóùåñòâóåò ñîñ-
òîÿíèå �q òàêîå, ÷òî q qa
��� � ïðè � �p S q~ ~ , à äëÿ êàæäîãî ïåðåõîäà q qa
��� �
ñóùåñòâóåò ñîñòîÿíèå �p òàêîå, ÷òî p pa
��� � ïðè � �p S q~ ~ , òî îòíîøåíèå S
áóäåì íàçûâàòü êâàçèñòðîãèì âçàèìíûì ïîäîáèåì, åñëè a Act� .
Ãðàôè÷åñêîå èçîáðàæåíèå êâàçèñòðîãîãî âçàèìíîãî ïîäîáèÿ ñîñòîÿíèé p
è q ïîêàçàíî íà ðèñ. 3. Ñîîòíîøåíèå ìåæäó ñòðîãèì âçàèìíûì ïîäîáèåì è
êâàçèñòðîãèì âçàèìíûì ïîäîáèåì îïðåäåëèì ñëåäóþùåé òåîðåìîé.
Òåîðåìà 4. Åñëè â ìàðêèðîâàííîé ñèñòåìå ñ ïåðåõîäàìè ( , ,� A
{ })
a a A��� � îòíîøåíèå S — ýòî îòíîøåíèå êâàçèñòðîãîãî âçàèìíîãî
ïîäîáèÿ, òî ïîëíîå îáúåäèíåíèå âñåõ âîçìîæíûõ îòíîøåíèé êâàçèñòðî-
ãîãî âçàèìíîãî ïîäîáèÿ ñî ñòðîãèì âçàèìíûì ïîäîáèåì (~ )�S ÿâëÿåòñÿ
îòíîøåíèåì ñòðîãîãî âçàèìíîãî ïîäîáèÿ è S �~.
Ä î ê à ç à ò å ë ü ñ ò â î. Ïóñòü â ìàðêèðîâàííîé ñèñòåìå ñ ïåðåõîäàìè
ñóùåñòâóþò ïðîöåññû P Q, � � ñ äîïóñòèìûìè ñîñòîÿíèÿìè p p P, �� è
q q Q, �� . Îáîçíà÷èì K S� �(~ ) è ðàññìîòðèì pKq, ãäå ( , )p q K� . Èç óñëî-
âèÿ pKq î÷åâèäíî, ÷òî p q~ è pSq. Îòíîøåíèå p q~ ÿâëÿåòñÿ ýêâèâà-
ëåíòíûì îòíîøåíèåì ïî óñëîâèþ. Äëÿ äîêàçàòåëüñòâà ýêâèâàëåíòíîñòè
pSq íåîáõîäèìî ïîêàçàòü, ÷òî ýòî îòíîøåíèå, â ñîîòâåòñòâèè ñ îïðåäåëå-
íèåì 1, ÿâëÿåòñÿ ðåôëåêñèâíûì, ñèììåòðè÷íûì è òðàíçèòèâíûì.
Ýêâèâàëåíòíîå ïðåäñòàâëåíèå ìîäåëåé ñëîæíûõ äèñêðåòíûõ ñèñòåì
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 1 13
a
a
S S
p p'
q
~
~
~
~
q'
Ðèñ. 3. Êâàçèñòðîãîå âçàèìíîå
ïîäîáèå ñîñòîÿíèé p è q
P
S
3
t
1
t
2
S
2
b
a Q
S
1
a b
Ðèñ. 4. Ãðàôè÷åñêîå ïðåäñòàâëåíèå ýêâèâàëåíòíûõ
ìîäåëåé
 ñîîòâåòñòâèè ñ îïðåäåëåíèåì 5 ââåäåì çàìåíó �p íà p è �q íà q. Åñëè
ñóùåñòâóåò îáùàÿ àêòèâíîñòü a, òî îíà ÿâëÿåòñÿ ïðè÷èíîé òîæäåñòâåííûõ
ïåðåõîäîâ p pa
��� è q qa
��� . Ïîýòîìó â çàäàííîé ñèñòåìå ïîäìíîæåñòâî I
ìíîæåñòâà S ñîäåðæèò áèíàðíûå îòíîøåíèÿ I p p q q�{( , ),( , )}. Ïîñêîëüêó
I S� ñîäåðæèò ýëåìåíòû îòíîøåíèÿ èäåíòè÷íîñòè, îíè ÿâëÿþòñÿ ðåôëåê-
ñèâíûìè.
Ñèììåòðè÷íîñòü êâàçèñòðîãîãî âçàèìíîãî ïîäîáèÿ, ò. å. ýêâèâàëåíòíîñòü
îòíîøåíèé pSq è qSp âûòåêàåò èç ñèììåòðè÷íîñòè îïðåäåëåíèÿ 5. Ñòðîãîå
äîêàçàòåëüñòâî äàííîãî ôàêòà àíàëîãè÷íî ïðèâåäåííîìó â òåîðåìå 1.
Òðàíçèòèâíîñòü ñòðîãîãî âçàèìíîãî ïîäîáèÿ ñîñòîÿíèé pSq ïðåäïî-
ëàãàåò íàëè÷èå ñîñòîÿíèÿ z òàêîãî, ÷òî pSzSq. Ïóñòü ñóùåñòâóåò ïåðåõîä
p pa
��� �. Òîãäà ñîãëàñíî îïðåäåëåíèþ 5 äëÿ íåêîòîðîãî z ñóùåñòâóåò
ïåðåõîä z za
��� � è � �p S z , ïîñêîëüêó pSz. Àíàëîãè÷íî, åñëè ñóùåñòâóåò
ïåðåõîä z za
��� �, òî äëÿ íåêîòîðîãî q ñïðàâåäëèâî íàëè÷èå ïåðåõîäà
q qa
��� � è � �z Sq ïðè óñëîâèè zSq. Îòñþäà � �p Sq ïðè pSq. Ñëåäîâàòåëüíî, K
ÿâëÿåòñÿ îòíîøåíèåì ñòðîãîãî âçàèìíîãî ïîäîáèÿ. Íî S K� , ïîýòîìó
S �~. Òåîðåìà äîêàçàíà.
Ïðÿìîé àëãîðèòì îïðåäåëåíèÿ ñòðîãîãî âçàèìíîãî ïîäîáèÿ ìîäå-
ëåé ñîñòîèò â íåïîñðåäñòâåííîì ïðèìåíåíèè îïðåäåëåíèÿ 3 êî âñåì ñîñòîÿ-
íèÿì, îáðàçóþùèì áèíàðíûå îòíîøåíèÿ. Ðàññìîòðèì ìàðêèðîâàííóþ ñèñòå-
ìó ñ ïåðåõîäàìè ( , ,{ })� A a Aa
��� � , êîòîðàÿ âêëþ÷àåò ïðîöåññû P Q, � � ñ
äîïóñòèìûìè ñîñòîÿíèÿìè { , , }s s s P
1 2 3
� è { , }t t Q
1 2
� íà ìíîæåñòâå àêòèâ-
íîñòåé A a b�{ , }, è ìíîæåñòâà ïåðåõîäîâ:
a s s s s t t��� �{( , ),( , ),( , )}
1 2 1 3 1 2
,
b s s s s t t��� �{( , ),( , ),( , )}
2 3 3 3 2 2
.
Ïðèìåð ãðàôè÷åñêîãî ïðåäñòàâëåíèÿ äàííîé ñèñòåìû ìîäåëåé, ïðåäñòàâ-
ëåííûõ ïðîöåññàìè P è Q, ïîêàçàí íà ðèñ. 4.
Îïðåäåëèì ñòðîãîå âçàèìíîå ïîäîáèå ñîñòîÿíèé s t
1 1
~ , çàäàâ áèíàðíîå
îòíîøåíèå R s t s t s t�{( , ),( , ),( , )}
1 1 2 2 3 2
. Íóæíî äîêàçàòü, ÷òî R ÿâëÿåòñÿ îòíî-
øåíèåì ñòðîãîãî âçàèìíîãî ïîäîáèÿ, ò. å. ñîîòâåòñòâóåò óñëîâèþ îïðåäåëå-
íèÿ 3. Ñ ýòîé öåëüþ äëÿ êàæäîé ïàðû ñîñòîÿíèé, âõîäÿùåé â îòíîøåíèå R,
íåîáõîäèìî èññëåäîâàòü âñå âîçìîæíûå ïåðåõîäû ïåðâîãî ñîñòîÿíèÿ è îïðå-
äåëèòü, ñîâïàäàþò ëè îíè ñ ñîîòâåòñòâóþùèìè ïåðåõîäàìè âòîðîãî ñîñòîÿ-
íèÿ. Ñîâïàäåíèå ïåðåõîäîâ ñëåäóåò ïîíèìàòü êàê òîò ôàêò, ÷òî îíè ïðîèñõî-
äÿò ïîä äåéñòâèåì îäíîé è òîé æå àêòèâíîñòè. Äàëüíåéøèå øàãè àëãîðèòìà
ñîñòîÿò â ïîñëåäîâàòåëüíîé ïðîâåðêå âñåõ ýëåìåíòîâ îòíîøåíèÿ R.
Ýëåìåíò ( , )s t R
1 1
� .
1. Ïåðåõîäû èç ñîñòîÿíèÿ s
1
:
s sa
1 2
��� ñîîòâåòñòâóåò t ta
1 2
��� ïðè ( , )s t R
2 2
� ;
s sa
1 3
��� ñîîòâåòñòâóåò t ta
1 2
��� ïðè ( , )s t R
3 2
� .
Á. Á. Íåñòåðåíêî, Ì. À. Íîâîòàðñêèé
14 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 1
2. Ïåðåõîäû èç ñîñòîÿíèÿ t
1
:
t ta
1 2
��� ñîîòâåòñòâóåò s sa
1 2
��� ïðè ( , )s t R
2 2
� ;
t ta
1 2
��� ñîîòâåòñòâóåò s sa
1 3
��� ïðè ( , )s t R
3 2
� .
Ýëåìåíò ( , )s t R
2 2
� .
1. Ïåðåõîäû èç ñîñòîÿíèÿ s
2
:
s sb
2 3
��� ñîîòâåòñòâóåò t tb
2 2
��� ïðè ( , )s t R
3 2
� .
2. Ïåðåõîäû èç ñîñòîÿíèÿ t
2
:
t tb
2 2
��� ñîîòâåòñòâóåò s sb
2 3
��� ïðè ( , )s t R
3 2
� .
Ýëåìåíò ( , )s t R
3 2
� .
1. Ïåðåõîäû èç ñîñòîÿíèÿ s
3
.
s sb
3 3
��� ñîîòâåòñòâóåò t tb
2 2
��� ïðè ( , )s t R
3 2
� .
2. Ïåðåõîäû èç ñîñòîÿíèÿ t
2
:
t tb
2 2
��� ñîîòâåòñòâóåò s sb
3 3
��� ïðè ( , )s t R
3 2
� .
Ñëåäîâàòåëüíî, R ÿâëÿåòñÿ îòíîøåíèåì ñòðîãîãî âçàèìíîãî ïîäîáèÿ,
ò. å. s t
1 1
~ . Àíàëîãè÷íî ìîæåò áûòü äîêàçàíî ñòðîãîå âçàèìíîå ïîäîáèå
s t
2 2
~ è s t
3 2
~ . Äëÿ ýòîãî íåîáõîäèìî îïðåäåëèòü ñîîòâåòñòâóþùèå
áèíàðíûå îòíîøåíèÿ.  ïåðâîì ñëó÷àå R s t s t�{( , ), ( , )}
2 2 3 2
, à âî âòî-
ðîì — R s t�{ , }
3 2
. Ïðîâåðêà ñîîòâåòñòâèÿ ïåðåõîäîâ äàåò âîçìîæíîñòü
óáåäèòüñÿ â òîì, ÷òî óïîìÿíóòûå ñîñòîÿíèÿ ÿâëÿþòñÿ ñòðîãî âçàèìíî
ïîäîáíûìè.
Òàêîé ïîäõîä ê îïðåäåëåíèþ ñòðîãîãî âçàèìíîãî ïîäîáèÿ äîñòàòî÷íî
ãðîìîçäêèé, ïîñêîëüêó ÷èñëî ïðîâåðîê âîçðàñòàåò ïðîïîðöèîíàëüíî 2
2n
,
ãäå n — ÷èñëî ñîñòîÿíèé, ïîäëåæàùèõ ïðîâåðêå. Åãî ïðàêòè÷åñêîå ïðèìå-
íåíèå âîçìîæíî òîëüêî íà íåáîëüøèõ ìîäåëÿõ. Ïîýòîìó àêòóàëüíûì ÿâëÿåò-
ñÿ ïîèñê àëãîðèòìîâ, ïîçâîëÿþùèõ ñîêðàòèòü ÷èñëî ïðîâåðîê.
Óñêîðåííûé àëãîðèòì îïðåäåëåíèÿ ñòðîãîãî âçàèìíîãî ïîäîáèÿ.
Àëüòåðíàòèâíûì ïîäõîäîì ê óñòàíîâëåíèþ ñòðîãîãî âçàèìíîãî ïîäîáèÿ
ÿâëÿåòñÿ ïîèñê õîòÿ áû îäíîé ïàðû ñîñòîÿíèé s t�~ , ïðîòèâîðå÷àùåé óñëî-
âèþ ñòðîãîãî âçàèìíîãî ïîäîáèÿ ìîäåëåé. Òàêîé ïîèñê ìîæåò áûòü ïðîâå-
äåí â âèäå ïîñëåäîâàòåëüíîãî àëãîðèòìà (ðèñ. 5), ñ ïîìîùüþ êîòîðîãî
ñíà÷àëà íåîáõîäèìî äîêàçàòü, ÷òî s t�~ . Åñëè ýòîò ôàêò íå äîêàçàí, òî
ñëåäóþùèé øàã ñîñòîèò â äîêàçàòåëüñòâå s t~ .
Ïóñòü ( , ,{ })� A a Aa
��� � — ìàðêèðîâàííàÿ ñèñòåìà ñ ïåðåõîäàìè,
âêëþ÷àþùàÿ ïðîöåññû P Q, � � ñ äîïóñòèìûìè ñîñòîÿíèÿìè { }s Pi i
n
�
�
1
è { }t Qi i
m
�
�
1
ïðè n m N, � , ãäå N — ìíîæåñòâî íàòóðàëüíûõ ÷èñåë.
Ýêâèâàëåíòíîå ïðåäñòàâëåíèå ìîäåëåé ñëîæíûõ äèñêðåòíûõ ñèñòåì
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 1 15
Ñèñòåìà òàêæå âêëþ÷àåò ìíîæåñòâî àêòèâíîñòåé A ak k
z
�
�
{ }
1
, z N� , è
ìíîæåñòâî ïåðåõîäîâ
a
��� �
� �, a A� . Òîãäà óñêîðåííûé àëãîðèòì
îïðåäåëåíèÿ ñòðîãîãî âçàèìíîãî ïîäîáèÿ íà÷èíàåòñÿ ñ ðàññìîòðåíèÿ
ïåðâîé ïàðû ñîñòîÿíèé ( , )s t
1 1
�
� �, êîòîðàÿ âñåãäà ÿâëÿåòñÿ ïåðâîé
òåêóùåé ïàðîé ñîñòîÿíèé.
Îáîçíà÷èì ïðîèçâîëüíóþ òåêóùóþ ïàðó ñîñòîÿíèé ( , )s t è çàäàäèì
ïîñëåäîâàòåëüíîñòü øàãîâ åå îáðàáîòêè:
1. Âûïîëíèòü ïåðåõîä s sa
i��� èç ñîñòîÿíèÿ s â íåêîòîðîå ïðîèçâîëü-
íîå ñîñòîÿíèå si ��, 1� �i n.
2. Ïðè óñëîâèè, ÷òî ïåðåõîä s sa
i��� óñïåøíî âûïîëíåí, âûïîëíèòü
ïåðåõîä t ta
j��� èç ñîñòîÿíèÿ t â íåêîòîðîå ïðîèçâîëüíîå ñîñòîÿíèå
t j ��, 1� �j m .
3. Ïðè óñëîâèè, ÷òî óñïåøíî âûïîëíåíû ïåðåõîäû s sa
i��� è t ta
j��� ,
óñòàíîâèòü íîâóþ òåêóùóþ ïàðó ñîñòîÿíèé ( , ) : ( , )s t s ti j� .
Á. Á. Íåñòåðåíêî, Ì. À. Íîâîòàðñêèé
16 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 1
( , ) := ( , )s t s t
1 1
s t
1 1
~
s t
1 1
~
Äà
Äà
Äà
Äà
Íåò
Íåò
Íåò
Íåò
i j:= 0, := 0
i i:= + 1
i n<
j m<
j j:= + 1
Íà÷àëî
Êîíåö
s si
t tj
a
a
/
Ðèñ. 5. Áëîê-ñõåìà àëãîðèòìà îïðåäåëåíèÿ ñòðîãîãî âçàèìíîãî ïîäîáèÿ
Àëãîðèòì ìîæåò èìåòü íåñêîëüêî âàðèàíòîâ ðàçâèòèÿ â çàâèñèìîñòè
îò âûáîðà ïåðåõîäà, êîòîðûé ïðîèñõîäèò íà ïåðâîì øàãå îáðàáîòêè òåêó-
ùåé ïàðû ñîñòîÿíèé. Ôóíêöèîíèðîâàíèå àëãîðèòìà ïðîäîëæàåòñÿ, ïîêà
íå áóäåò äîñòèãíóòà ìàêñèìàëüíî âîçìîæíàÿ ïîñëåäîâàòåëüíîñòü ïàð ñîñ-
òîÿíèé, íà÷èíàÿ ñ íà÷àëüíîé ïàðû ( , )s t
1 1
. Àëãîðèòì îñòàíàâëèâàåòñÿ ïðè
íåâîçìîæíîñòè âûïîëíåíèÿ ïåðåõîäà íà ïåðâîì èëè íà âòîðîì øàãå îáðà-
áîòêè òåêóùåé ïàðû ñîñòîÿíèé. Åñëè íåçàâèñèìî îò ñòðàòåãèè âûáîðà
ïåðåõîäà àëãîðèòì îñòàíàâëèâàåòñÿ íà ïåðâîì ýòàïå îáðàáîòêè òåêóùåé
ïàðû ñîñòîÿíèé, òî ñ÷èòàþò, ÷òî s t
1 1
~ , à â ñëó÷àå îñòàíîâêè íà âòîðîì
øàãå — s t
1 1�~ . Åñëè âñåãäà âîçìîæíî âûïîëíåíèå ïåðåõîäà êàê íà ïåðâîì,
òàê è íà âòîðîì øàãå, ñ÷èòàþò, ÷òî ñîñòîÿíèÿ s
1
è t
1
ÿâëÿþòñÿ ñòðîãî
âçàèìíî ïîäîáíûìè.
Âûâîäû. Âîçðàñòàþùàÿ ñëîæíîñòü äèñêðåòíûõ ñèñòåì òðåáóåò íåïðå-
ðûâíîãî ñîâåðøåíñòâîâàíèÿ ôîðìàëüíûõ ñðåäñòâ èõ îïèñàíèÿ. Îäíèì èç
ñîâðåìåííûõ ñðåäñòâ òàêîãî îïèñàíèÿ ÿâëÿþòñÿ àëãåáðû ïðîöåññîâ. Äàëü-
íåéøåå ðàçâèòèå àëãåáð ïðîöåññîâ íàïðàâëåíî íà ïîâûøåíèå àäåêâàòíîñòè
ïðåäñòàâëåíèÿ îáúåêòîâ ìîäåëèðîâàíèÿ ïóòåì ðàñøèðåíèÿ ñèíòàêñè÷åñêèõ
êîíñòðóêöèé è ñåìàíòè÷åñêèõ ïðàâèë. Ïðåäëîæåííàÿ àëãåáðà ïðîöåññîâ ñîç-
äàíà äëÿ ìîäåëèðîâàíèÿ ñëîæíûõ äèñêðåòíûõ âû÷èñëèòåëüíûõ ñèñòåì,
îðèåíòèðîâàííûõ íà ðåàëèçàöèþ ïàðàëëåëüíûõ àëãîðèòìîâ ñ ðåàëüíîé ðàáî-
÷åé íàãðóçêîé. Òàêîé õàðàêòåð ðàáî÷åé íàãðóçêè òðåáóåò îñîáîãî âíèìàíèÿ ê
ýêâèâàëåíòíîñòè ïðåäñòàâëåíèÿ îáúåêòà ìîäåëèðîâàíèÿ. Íà îñíîâå îáùåé
òåîðèè ñèñòåì íàéäåíû ïîäõîäû ê îïðåäåëåíèþ ïîâåäåí÷åñêîé ýêâèâà-
ëåíòíîñòè, çàäàíû óñëîâèÿ ñóùåñòâîâàíèÿ ñòðîãîãî âçàèìíîãî ïîäîáèÿ è
îïðåäåëåíû åãî îñíîâíûå ñâîéñòâà.
Èçëîæåííûå òåîðåòè÷åñêèå èññëåäîâàíèÿ ïîçâîëèëè ñîçäàòü óñêî-
ðåííûé àëãîðèòì ïðîâåðêè ñòðîãîãî âçàèìíîãî ïîäîáèÿ êàê ìåæäó ñèñòå-
ìîé è åå ìîäåëüþ, òàê è ìåæäó ðàçëè÷íûìè ìîäåëÿìè äàííîé ñèñòåìû.
The process algebra is considered which is on the parallel structure orientated description. The
structures function with real working load. The basic concepts are determined for behavioral
equivalence of models submitted by labeled transition systems. Definition is formed and the basic
properties are stated for strong mutual model similarity. The direct and accelerated algorithms are
developed for determination of strong mutual similarity on the basis of the received properties.
1. Áó÷ Ã., ßêîáñîí À., Ðàìáî Äæ. UML. Êëàññèêà CS. — ÑÏá. : Ïèòåð, 2006. — 736 ñ.
2. Èëüèí Â. Â. Ìîäåëèðîâàíèå áèçíåñ-ïðîöåññîâ. Ïðàêòè÷åñêîå èñïîëüçîâàíèå ARIS. —
Ì. : Èçä. äîì «Âèëüÿìñ» , 2006. — 176 ñ.
3. Õîàð ×. Âçàèìîäåéñòâóþùèå ïîñëåäîâàòåëüíûå ïðîöåññû. — Ì. : Ìèð, 1989. — 264 ñ.
4. Bergstra J. A., Middelburg C. A., Stefanescu Ch. Network algebra for asynchronous data-
flow // International Journal of Computer Mathematics. — 1997. — Vol. 65. — P. 57—88.
Ýêâèâàëåíòíîå ïðåäñòàâëåíèå ìîäåëåé ñëîæíûõ äèñêðåòíûõ ñèñòåì
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 1 17
5. De Nicola R. Extensional Equivalence for Transition Systems // Acta Informatica.— 1987. —
Vol. 24, ¹ 2 .— P. 211—237.
6. Main M. Trace, failure and testing equivalences for communicating processes // Interna-
tional Journal of Parallel Programming. — 1987. — Vol. 16, ¹ 5.— P. 383—400.
7. Milner R. Communication and Concurrency. —N. Y. : Prentice Hall, 1995. — 272 p.
Ïîñòóïèëà 11.04.07;
ïîñëå äîðàáîòêè 13.09.07
ÍÅÑÒÅÐÅÍÊÎ Áîðèñ Áîðèñîâè÷, ä-ð òåõí. íàóê, çàì. äèðåêòîðà Èí-òà ìàòåìàòèêè ÍÀÍ
Óêðàèíû.  1965 ã. îêîí÷èë Êèåâñêèé ïîëèòåõíè÷åñêèé èí-ò. Îáëàñòü íàó÷íûõ èññëåäîâàíèé —
ðàçðàáîòêà ïàðàëëåëüíûõ ìåòîäîâ è èññëåäîâàíèå íåëèíåéíûõ ïðîöåññîâ.
ÍÎÂÎÒÀÐÑÊÈÉ Ìèõàèë Àíàòîëüåâè÷, êàíä. òåõí. íàóê, ñò. íàó÷. ñîòð. Èí-òà ìàòåìàòèêè
ÍÀÍ Óêðàèíû.  1979 ã. îêîí÷èë Êèåâñêèé ïîëèòåõíè÷åñêèé èí-ò. Îáëàñòü íàó÷íûõ èññëåäî-
âàíèé — ðàçðàáîòêà è èññëåäîâàíèå ôîðìàëüíûõ ñðåäñòâ îïèñàíèÿ ïàðàëëåëüíûõ ïðîöåññîâ.
Á. Á. Íåñòåðåíêî, Ì. À. Íîâîòàðñêèé
18 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 1
|