К вопросу о полиномиальной сложности проблемы эквивалентности в алгебраических моделях программ
Розглянуто алгебраїчні моделі програм, для яких встановлено розв’язність проблеми еквівалентності. Запропоновано новий алгоритм, що допускає еквівалентність в цих моделях і походить з відомого алгоритму Мура для кінцевих автоматів. Описано клас моделей, для яких запропонований алгоритм модифікується...
Збережено в:
| Дата: | 2012 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/84140 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | К вопросу о полиномиальной сложности проблемы эквивалентности в алгебраических моделях программ / Р.И. Подловченко // Кибернетика и системный анализ. — 2012. — Т. 48, № 5. — С. 17-24. — Бібліогр.: 1 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-84140 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-841402015-07-04T03:01:56Z К вопросу о полиномиальной сложности проблемы эквивалентности в алгебраических моделях программ Подловченко, Р.И. Кибернетика Розглянуто алгебраїчні моделі програм, для яких встановлено розв’язність проблеми еквівалентності. Запропоновано новий алгоритм, що допускає еквівалентність в цих моделях і походить з відомого алгоритму Мура для кінцевих автоматів. Описано клас моделей, для яких запропонований алгоритм модифікується в алгоритм поліноміальної складності. Algebraic models of programs for which the decidability of equivalence checking problem was proved are considered. A new equivalence checking algorithm stemmed from the well-known Moore’s technique for finite state automata is introduced. It is shown that for some subclasses of models this algorithm reduces to a polynomial-time equivalence checking procedure. 2012 Article К вопросу о полиномиальной сложности проблемы эквивалентности в алгебраических моделях программ / Р.И. Подловченко // Кибернетика и системный анализ. — 2012. — Т. 48, № 5. — С. 17-24. — Бібліогр.: 1 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/84140 519.71 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Кибернетика Кибернетика |
| spellingShingle |
Кибернетика Кибернетика Подловченко, Р.И. К вопросу о полиномиальной сложности проблемы эквивалентности в алгебраических моделях программ Кибернетика и системный анализ |
| description |
Розглянуто алгебраїчні моделі програм, для яких встановлено розв’язність проблеми еквівалентності. Запропоновано новий алгоритм, що допускає еквівалентність в цих моделях і походить з відомого алгоритму Мура для кінцевих автоматів. Описано клас моделей, для яких запропонований алгоритм модифікується в алгоритм поліноміальної складності. |
| format |
Article |
| author |
Подловченко, Р.И. |
| author_facet |
Подловченко, Р.И. |
| author_sort |
Подловченко, Р.И. |
| title |
К вопросу о полиномиальной сложности проблемы эквивалентности в алгебраических моделях программ |
| title_short |
К вопросу о полиномиальной сложности проблемы эквивалентности в алгебраических моделях программ |
| title_full |
К вопросу о полиномиальной сложности проблемы эквивалентности в алгебраических моделях программ |
| title_fullStr |
К вопросу о полиномиальной сложности проблемы эквивалентности в алгебраических моделях программ |
| title_full_unstemmed |
К вопросу о полиномиальной сложности проблемы эквивалентности в алгебраических моделях программ |
| title_sort |
к вопросу о полиномиальной сложности проблемы эквивалентности в алгебраических моделях программ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2012 |
| topic_facet |
Кибернетика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/84140 |
| citation_txt |
К вопросу о полиномиальной сложности проблемы эквивалентности в алгебраических моделях программ / Р.И. Подловченко // Кибернетика и системный анализ. — 2012. — Т. 48, № 5. — С. 17-24. — Бібліогр.: 1 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT podlovčenkori kvoprosuopolinomialʹnojsložnostiproblemyékvivalentnostivalgebraičeskihmodelâhprogramm |
| first_indexed |
2025-07-06T11:05:40Z |
| last_indexed |
2025-07-06T11:05:40Z |
| _version_ |
1836895375198257152 |
| fulltext |
ÓÄÊ 519.71
Ð.È. ÏÎÄËÎÂ×ÅÍÊÎ
Ê ÂÎÏÐÎÑÓ Î ÏÎËÈÍÎÌÈÀËÜÍÎÉ ÑËÎÆÍÎÑÒÈ ÏÐÎÁËÅÌÛ
ÝÊÂÈÂÀËÅÍÒÍÎÑÒÈ Â ÀËÃÅÁÐÀÈ×ÅÑÊÈÕ ÌÎÄÅËßÕ ÏÐÎÃÐÀÌÌ
Êëþ÷åâûå ñëîâà: àëãåáðàè÷åñêàÿ ìîäåëü ïðîãðàìì, ñõåìà ïðîãðàìì, ýêâèâà-
ëåíòíîñòü, àëãîðèòìè÷åñêàÿ ðàçðåøèìîñòü, âû÷èñëèòåëüíàÿ ñëîæíîñòü.
Íàñòîÿùàÿ ñòàòüÿ ïðèìûêàåò ê ðàáîòå [1], â êîòîðîé óñòàíîâëåíà ðàçðåøè-
ìîñòü ïðîáëåìû ýêâèâàëåíòíîñòè ñõåì ïðîãðàìì, ïðèíàäëåæàùèõ àëãåáðàè-
÷åñêèì ìîäåëÿì ïðîãðàìì îïðåäåëåííîãî òèïà, à èìåííî: óðàâíîâåøåííûì
ïîëóãðóïïîâûì ìîäåëÿì ïðîãðàìì ñ ëåâûì ñîêðàùåíèåì è ðàçðåøèìîé ýêâè-
âàëåíòíîñòüþ îïåðàòîðíûõ öåïî÷åê. Àëãîðèòì, ðàçðåøàþùèé ýêâèâàëåíòíîñòü
ñõåì ïðîãðàìì, ïî âðåìåííîé ñëîæíîñòè îêàçàëñÿ ýêñïîíåíöèàëüíûì îòíîñè-
òåëüíî ðàçìåðîâ ñõåì, ò.å. ìàëîýôôåêòèâíûì â ïðàêòèêå ïðîãðàììèðîâàíèÿ.
 ñâÿçè ñ ýòèì âîçíèêàåò çàäà÷à: âûäåëèòü èç íàéäåííîãî ìíîæåñòâà àëãåá-
ðàè÷åñêèõ ìîäåëåé ïðîãðàìì òàêèå ìîäåëè, äëÿ êîòîðûõ ñóùåñòâóåò ïðèåìëå-
ìûé ïî ñëîæíîñòè àëãîðèòì, ðàñïîçíàþùèé ýêâèâàëåíòíîñòü ñõåì ïðîãðàìì.
Ðåøåíèå äàííîé çàäà÷è ïðîâîäèòñÿ ñëåäóþùèì îáðàçîì. Äëÿ ìíîæåñòâà
ìîäåëåé èç [1] êîíñòðóèðóåòñÿ àëãîðèòì, ðàñïîçíàþùèé ýêâèâàëåíòíîñòü ñõåì
â ìîäåëè ìåòîäîì, îòëè÷àþùèìñÿ îò ðàññìîòðåííîãî â óêàçàííîé ðàáîòå.
 îñíîâó íîâîãî ìåòîäà ïîëîæåíà èäåÿ, âïåðâûå âîïëîùåííàÿ â àëãîðèòìå
Ìóðà, ðàñïîçíàþùåì ýêâèâàëåíòíîñòü êîíå÷íûõ àâòîìàòîâ. Ýòà èäåÿ ñîñòîèò
â ñëåäóþùåì: ïðîñìîòð ïðîöåññà ôóíêöèîíèðîâàíèÿ ñõåìû îñóùåñòâëÿåòñÿ
ñ ïîìîùüþ àíàëèçà ïðîëàãàåìûõ ìàðøðóòîâ â ñõåìàõ. Îäíàêî ñêîíñòðóèðîâàí-
íûé àëãîðèòì ïðè ýòîì òàêæå ýêñïîíåíöèàëåí ïî ñëîæíîñòè. Ïîýòîìó âûäåëÿåòñÿ
äîñòàòî÷íî øèðîêèé êëàññ ìîäåëåé, äëÿ êîòîðûõ ïóòåì ìîäèôèêàöèè äàííîãî àëãî-
ðèòìà ïîñòðîåí íîâûé àëãîðèòì, ðàñïîçíàþùèé ýêâèâàëåíòíîñòü ñõåì ïðîãðàìì
ñ ïîëèíîìèàëüíîé ñëîæíîñòüþ îòíîñèòåëüíî ñëîæíîñòè ðàçðåøåíèÿ ýêâèâàëåíò-
íîñòè îïåðàòîðíûõ öåïî÷åê. Ïîñëåäíåå îçíà÷àåò, ÷òî â êîýôôèöèåíòû ïîëèíîìà,
ñîñòàâëÿþùåãî îöåíêó ñëîæíîñòè àëãîðèòìà, âõîäÿò, â îáùåì ñëó÷àå, îöåíêè ñëîæ-
íîñòè àëãîðèòìà, ðàñïîçíàþùåãî ýêâèâàëåíòíîñòü îïåðàòîðíûõ öåïî÷åê.
Èçëîæåíèþ àëãîðèòìîâ, ðàçðåøàþùèõ ïðîáëåìó ýêâèâàëåíòíîñòè äëÿ ìîäå-
ëåé ïðîãðàìì è ïðåäñòàâëÿþùèõ îñíîâíûå ðåçóëüòàòû ïðîâåäåííîãî èññëåäîâà-
íèÿ, ïðåäøåñòâóþò ðàçä. 1 è 2.
 ðàçä. 1 îïèñûâàþòñÿ îñíîâíûå ïîíÿòèÿ, èñïîëüçóåìûå â äàííîé ñòàòüå.
Èñõîäíûì äëÿ ýòîãî ÿâëÿåòñÿ ñëåäóþùèé ôàêò (òåîðåìà 1): â ëþáîé àëãåáðàè÷åñêîé
ìîäåëè ïðîãðàìì ïðîáëåìà ýêâèâàëåíòíîñòè ñâîäèòñÿ ê ïðîáëåìå ýêâèâàëåíòíîñòè
â ìíîæåñòâå ïðèíàäëåæàùèõ ìîäåëè ìàòðè÷íûõ ñõåì ïðîãðàìì; ñâîäÿùèé àëãî-
ðèòì ïîëèíîìèàëåí ïî ñëîæíîñòè. Íà ýòîì îñíîâàíèè îïðåäåëÿþòñÿ ñèíòàêñèñ è
ñåìàíòèêà ìàòðè÷íûõ ñõåì, ÿâëÿþùèõñÿ îáúåêòàìè ïðîâîäèìûõ èññëåäîâàíèé. Äà-
åòñÿ îïèñàíèå óðàâíîâåøåííîé ïîëóãðóïïîâîé ìîäåëè ïðîãðàìì ñ ëåâûì ñîêðàùå-
íèåì è ôîðìóëèðóåòñÿ òåîðåìà 2 î ðàçðåøèìîñòè â íåé ýêâèâàëåíòíîñòè ñõåì ïðî-
ãðàìì ïðè óñëîâèè, ÷òî ýêâèâàëåíòíîñòü îïåðàòîðíûõ öåïî÷åê ðàçðåøèìà.
 ðàçä. 2 ïðèâîäÿòñÿ íåîáõîäèìûå óñëîâèÿ ýêâèâàëåíòíîñòè ìàòðè÷íûõ
ñõåì, óñòàíîâëåííûå â [1]. Îíè èñïîëüçóþòñÿ â àëãîðèòìå, ðàñïîçíàþùåì ýêâè-
âàëåíòíîñòü ìàòðè÷íûõ ñõåì â óðàâíîâåøåííîé ïîëóãðóïïîâîé ìîäåëè ïðî-
ãðàìì ñ ëåâûì ñîêðàùåíèåì è ðàçðåøèìîé ýêâèâàëåíòíîñòüþ îïåðàòîðíûõ öå-
ïî÷åê (òåîðåìà 3). Äîêàçàòåëüñòâî òåîðåìû 3 ñîñòàâëÿåò ðàçä. 3.
 ðàçä. 4 ê ýêâèâàëåíòíîñòè îïåðàòîðíûõ öåïî÷åê ïðåäúÿâëÿåòñÿ åùå îäíî
òðåáîâàíèå: îáëàäàòü ñâîéñòâîì ÷àñòè÷íîãî ïðàâîãî ñîêðàùåíèÿ. Îïèñûâàåòñÿ
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5 17
© Ð.È. Ïîäëîâ÷åíêî, 2012
èçâëåêàåìîå èç ýòîãî ñâîéñòâà äîáàâî÷íîå íåîáõîäèìîå óñëîâèå ýêâèâàëåíòíîñ-
òè ìàòðè÷íûõ ñõåì, è ñ ó÷åòîì åãî ìîäèôèöèðóåòñÿ àëãîðèòì, ïðåäñòàâëåííûé
â òåîðåìå 3. Íîâûé àëãîðèòì ðàñïîçíàåò ýêâèâàëåíòíîñòü ìàòðè÷íûõ ñõåì
â óðàâíîâåøåííîé ïîëóãðóïïîâîé ìîäåëè ïðîãðàìì ñ ëåâûì è ÷àñòè÷íûì ïðà-
âûì ñîêðàùåíèåì è ðàçðåøèìîé ýêâèâàëåíòíîñòüþ îïåðàòîðíûõ öåïî÷åê
ñ ïðèåìëåìîé ñëîæíîñòüþ (òåîðåìà 4).
Ê îñíîâíûì ðåçóëüòàòàì, èçëîæåííûì â ðàçä. 3 è 4, îòíîñèòñÿ è ìåòîäîëî-
ãèÿ èõ ïîëó÷åíèÿ, ñ ïîìîùüþ êîòîðîé èç ìíîæåñòâà óðàâíîâåøåííûõ ïîëóãðóï-
ïîâûõ ìîäåëåé ïðîãðàìì ñ ëåâûì è ÷àñòè÷íûì ïðàâûì ñîêðàùåíèåì ìîæíî âû-
äåëÿòü ìîäåëè ñ ïðèåìëåìîé ñëîæíîñòüþ ðàñïîçíàâàíèÿ ýêâèâàëåíòíîñòè ñõåì.
1. ÎÑÍÎÂÍÛÅ ÏÎÍßÒÈß È ÔÀÊÒÛ
Àëãåáðàè÷åñêàÿ ìîäåëü ïðîãðàìì, ââåäåííàÿ â [1], ñòðîèòñÿ íàä äâóìÿ êîíå÷íû-
ìè è íåïåðåñåêàþùèìèñÿ àëôàâèòàìè — Y è P. Ýëåìåíòû àëôàâèòà Y íàçûâà-
þòñÿ îïåðàòîðíûìè ñèìâîëàìè, ýëåìåíòû àëôàâèòà P — ëîãè÷åñêèìè ïåðåìåí-
íûìè; êàæäàÿ ïåðåìåííàÿ ïðèíèìàåò çíà÷åíèå èç ìíîæåñòâà { }0 1, . Îáúåêòàìè
ìîäåëè ÿâëÿþòñÿ ñõåìû ïðîãðàìì. Ìîäåëü ïðåäñòàâëÿåò ñîáîé ìíîæåñòâî ñõåì
ïðîãðàìì íàä Y, P ñ ââåäåííûì íà íåì îòíîøåíèåì ýêâèâàëåíòíîñòè ñõåì.
Ïðîáëåìà ïðîâåðêè ýêâèâàëåíòíîñòè ñõåì ïðîãðàìì â ìîäåëè, ñîñòîÿùàÿ
â ïîñòðîåíèè ðàçðåøàþùåãî ýêâèâàëåíòíîñòü àëãîðèòìà, îòíîñèòñÿ ê ÷èñëó ôóí-
äàìåíòàëüíûõ. Èìååò ìåñòî ñëåäóþùàÿ òåîðåìà.
Òåîðåìà 1. Ïðîáëåìà ýêâèâàëåíòíîñòè â ëþáîé àëãåáðàè÷åñêîé ìîäåëè ïðî-
ãðàìì ñâîäèòñÿ ê ïðîáëåìå ýêâèâàëåíòíîñòè â ìíîæåñòâå ìàòðè÷íûõ ñõåì, ïðè-
íàäëåæàùèõ ìîäåëè; ïðè ýòîì ñâîäÿùèé àëãîðèòì ïîëèíîìèàëåí ïî ñëîæíîñòè
îòíîñèòåëüíî ðàçìåðîâ ñõåì.
Äîêàçàòåëüñòâî òåîðåìû 1 äàíî â [1].
Òàêèì îáðàçîì, ïîèñê ïðèåìëåìîãî ïî ñëîæíîñòè àëãîðèòìà, ðàçðåøàþùåãî
ïðîáëåìó ýêâèâàëåíòíîñòè â àëãåáðàè÷åñêîé ìîäåëè ïðîãðàìì, ñâîäèòñÿ ê ïî-
ñòðîåíèþ àëãîðèòìà, ðàñïîçíàþùåãî ýêâèâàëåíòíîñòü ìàòðè÷íûõ ñõåì èç äàí-
íîé ìîäåëè. Îñíîâûâàÿñü íà ýòîì, îãðàíè÷èìñÿ îïèñàíèåì ìàòðè÷íûõ ñõåì
(â [1] ïðèâåäåíî îïðåäåëåíèå ñõåìû ïðîãðàììû îáùåãî âèäà).
Ñèíòàêñè÷åñêè ìàòðè÷íàÿ ñõåìà íàä Y, P ïðåäñòàâëÿåò ñîáîé êîíå÷íûé îðè-
åíòèðîâàííûé è ðàçìå÷åííûé ãðàô, âåðøèíû êîòîðîãî ïîäðàçäåëÿþòñÿ íà âõîä
ñõåìû, âûõîä ñõåìû, ïóñòîé öèêë è ïðåîáðàçîâàòåëè; ïðè ýòîì âõîä, âûõîä è
ïóñòîé öèêë ïðèñóòñòâóþò îáÿçàòåëüíî. Èç ëþáîé âåðøèíû, êðîìå âûõîäà è ïóñ-
òîãî öèêëà, èñõîäÿò äóãè â êîëè÷åñòâå, ðàâíîì ÷èñëó ýëåìåíòîâ â ìíîæåñòâå X ,
ãäå X x x� �{ P { }}| : ,0 1 . Êàæäàÿ äóãà ïîìå÷åíà ýëåìåíòîì èç X , ïðè÷åì ðàç-
ëè÷íûå äóãè íåñóò ðàçíûå ìåòêè. Âî âõîäå ñõåìû íåò îêàí÷èâàþùèõñÿ â íåì
äóã. Êàæäûé ïðåîáðàçîâàòåëü â ñõåìå èìååò â êà÷åñòâå ìåòêè ñèìâîë èç Y.
Äàëåå ýëåìåíòû ìíîæåñòâà X íàçûâàþòñÿ íàáîðàìè çíà÷åíèé ëîãè÷åñêèõ
ïåðåìåííûõ èç P, èëè, êðàòêî, íàáîðàìè.
Ñåìàíòè÷åñêè êàæäàÿ ìàòðè÷íàÿ ñõåìà íàä Y, P ÿâëÿåòñÿ íîñèòåëåì îòîáðàæå-
íèÿ, â îáùåì ñëó÷àå — ÷àñòè÷íîãî, ìíîæåñòâà L, ñîñòîÿùåãî èç âñåõ ôóíêöèé ðàç-
ìåòêè íàä Y, P, â ìíîæåñòâî Y * , ñîñòîÿùåå èç âñåõ ñëîâ íàä àëôàâèòîì Y. Ôóíêöèåé
ðàçìåòêè íàä Y, P íàçûâàåòñÿ âñþäó îïðåäåëåííîå îòîáðàæåíèå ìíîæåñòâà Y * â ìíî-
æåñòâî X . Äàëåå ýëåìåíòû ìíîæåñòâà Y * íàçûâàþòñÿ îïåðàòîðíûìè öåïî÷êàìè.
Ðåàëèçóåìîå ìàòðè÷íîé ñõåìîé îòîáðàæåíèå îñóùåñòâëÿåòñÿ ïîñðåäñòâîì
ïðîöåäóðû åå âûïîëíåíèÿ íà ôóíêöèÿõ ðàçìåòêè.
Ïóñòü � �L . Ïðîöåäóðà âûïîëíåíèÿ ñõåìû íà �, âêëþ÷àþùàÿ îáõîä ñõåìû,
íà÷èíàþùèéñÿ â åå âõîäå, è ïîñòðîåíèå îïåðàòîðíîé öåïî÷êè, îñóùåñòâëÿåòñÿ
ïî ñëåäóþùèì ïðàâèëàì.
Ïóñòü � 0 — âõîä ñõåìû. Òîãäà ïî ôóíêöèè � îïðåäåëÿåòñÿ íàáîð x0 , ðàâ-
íûé ��, ãäå � — ïóñòàÿ îïåðàòîðíàÿ öåïî÷êà, è âûõîä èç âåðøèíû � 0 ñîâåðøà-
åòñÿ ïî èñõîäÿùåé èç íåå äóãå ñ ìåòêîé x0 .
18 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5
Äîïóñòèì, ÷òî ïðè îáõîäå äîñòèãíóòà âåðøèíà � ñõåìû, h — ïîñòðîåííàÿ
ê ýòîìó ìîìåíòó îïåðàòîðíàÿ öåïî÷êà. Òîãäà, åñëè � — ïðåîáðàçîâàòåëü ñ ìåò-
êîé y, öåïî÷êà h òðàíñôîðìèðóåòñÿ â öåïî÷êó hy, íàõîäèòñÿ íàáîð �( )hy è âûõîä
èç âåðøèíû � ñîâåðøàåòñÿ ïî äóãå, ïîìå÷åííîé ýòèì íàáîðîì. Åñëè � — âûõîä
ñõåìû èëè ïóñòîé öèêë, òî îáõîä ñõåìû ïðåêðàùàåòñÿ.  ïåðâîì ñëó÷àå ãîâîðèò-
ñÿ, ÷òî ñõåìà îñòàíîâèëàñü íà ôóíêöèè � ñ ðåçóëüòàòîì h, âî âòîðîì —
âûïîëíåíèå ñõåìû íà � ñ÷èòàåòñÿ áåçðåçóëüòàòíûì. Òàêèì îáðàçîì îïðåäåëÿåò-
ñÿ îòîáðàæåíèå ñõåìîé ìíîæåñòâà L â ìíîæåñòâî Y * .
Êàê áûëî îòìå÷åíî, îòäåëüíàÿ àëãåáðàè÷åñêàÿ ìîäåëü ïðîãðàìì îïðåäåëÿåò-
ñÿ ââåäåíèåì îòíîøåíèÿ ýêâèâàëåíòíîñòè ìåæäó ñõåìàìè ïðîãðàìì. Êàæäîå îò-
íîøåíèå ýêâèâàëåíòíîñòè ñõåì èíäóöèðóåòñÿ äâóìÿ ïàðàìåòðàìè: îòíîøåíèåì
ýêâèâàëåíòíîñòè � â ìíîæåñòâå Y * ; ïîäìíîæåñòâîì L ìíîæåñòâà L.
Îïèøåì åãî äëÿ ìàòðè÷íûõ ñõåì. Ìàòðè÷íûå ñõåìû G G1 2, ïî îïðåäåëåíèþ
( , )� L -ýêâèâàëåíòíû òîãäà è òîëüêî òîãäà, êîãäà, êàêîé áû íè áûëà ôóíêöèÿ � èç L ,
êàæäûé ðàç ïðè îñòàíîâêå îäíîé èç ñõåì G G1 2, íà � îñòàíàâëèâàåòñÿ è äðóãàÿ; ðå-
çóëüòàòàìè èõ âûïîëíåíèÿ ÿâëÿþòñÿ �-ýêâèâàëåíòíûå îïåðàòîðíûå öåïî÷êè.
Ñôîðìóëèðóåì òåîðåìó, äîêàçàííóþ â [1].
Òåîðåìà 2. Â óðàâíîâåøåííîé ïîëóãðóïïîâîé ìîäåëè ïðîãðàìì ñ ëåâûì ñî-
êðàùåíèåì è ðàçðåøèìîé ýêâèâàëåíòíîñòüþ îïåðàòîðíûõ öåïî÷åê ðàçðåøèìà
ïðîáëåìà ýêâèâàëåíòíîñòè â ìíîæåñòâå ïðèíàäëåæàùèõ ìîäåëè ìàòðè÷íûõ
ñõåì; ðàçðåøàþùèé àëãîðèòì èìååò ýêñïîíåíöèàëüíóþ ñëîæíîñòü îòíîñèòåëüíî
ðàçìåðîâ ñðàâíèâàåìûõ ñõåì.
Ïàðàìåòðàìè óðàâíîâåøåííîé ïîëóãðóïïîâîé ìîäåëè ïðîãðàìì ñ ëåâûì ñîêðà-
ùåíèåì ÿâëÿþòñÿ � è L, óäîâëåòâîðÿþùèå ñëåäóþùèì òðåáîâàíèÿì: � óðàâíîâåøåí-
íàÿ, ïîëóãðóïïîâàÿ, îáëàäàþùàÿ ñâîéñòâîì ëåâîãî ñîêðàùåíèÿ; L ñîñòîèò èç âñåõ
�-ñîãëàñîâàííûõ ôóíêöèé ðàçìåòêè èç L. Îïðåäåëèì èñïîëüçóåìûå çäåñü ïîíÿòèÿ.
Ýêâèâàëåíòíîñòü � â ìíîæåñòâå Y * íàçûâàåòñÿ:
— óðàâíîâåøåííîé, åñëè, êàêèìè áû íè áûëè öåïî÷êè h h1 2, èç Y * , âûïîë-
íÿåòñÿ ñîîòíîøåíèå h h h h1 2~ | | | |
�
� �1 2 , ãäå | |h — äëèíà öåïî÷êè h èç Y * ;
— ïîëóãðóïïîâîé, åñëè, êàêèìè áû íè áûëè îïåðàòîðíûå öåïî÷êè
h h h h1, , ,2 3 4 èç Y * , âûïîëíÿåòñÿ ñîîòíîøåíèå ( ~ ) ( ~ ) ~h h h h h h h h1 2 3 4 1 3 2 4
� � �
� � ;
— îáëàäàþùåé ñâîéñòâîì ëåâîãî ñîêðàùåíèÿ, åñëè, êàêèìè áû íè áûëè öåïî÷-
êè h h h h1, , ,2 3 4 , âûïîëíÿåòñÿ ñîîòíîøåíèå ( ~ ) ( ~ ) ~h h h h h h h h1 3 2 4 1 2 3 4
� � �
� � .
Çäåñü è äàëåå ñâÿçêà ~
�
ñòàâèòñÿ ìåæäó �-ýêâèâàëåíòíûìè öåïî÷êàìè.
Ôóíêöèÿ ðàçìåòêè � èç L íàçûâàåòñÿ �-ñîãëàñîâàííîé, åñëè äëÿ ëþáûõ
h h1, 2 èç Y * âûïîëíÿåòñÿ ñîîòíîøåíèå h h h h1 2~ ( ) ( )
�
� �� �1 2 .
2. ÍÅÎÁÕÎÄÈÌÛÅ ÓÑËÎÂÈß ÝÊÂÈÂÀËÅÍÒÍÎÑÒÈ ÌÀÒÐÈ×ÍÛÕ ÑÕÅÌ
ÈÇ ÓÐÀÂÍÎÂÅØÅÍÍÎÉ ÏÎËÓÃÐÓÏÏÎÂÎÉ ÌÎÄÅËÈ ÏÐÎÃÐÀÌÌ Ñ ËÅÂÛÌ
ÑÎÊÐÀÙÅÍÈÅÌ
Ìîäåëü ïðîãðàìì îáîçíà÷èì M L( , )� . Àëãîðèòì, ðàñïîçíàþùèé ýêâèâàëåíò-
íîñòü ìàòðè÷íûõ ñõåì èç M L( , )� , ñòðîèò â íèõ ñî÷åòàåìûå ìàðøðóòû, ïðîâå-
ðÿÿ ïðè ýòîì íåîáõîäèìûå óñëîâèÿ ýêâèâàëåíòíîñòè ñõåì.
Ìàðøðóòîì â ìàòðè÷íîé ñõåìå íàçûâàåòñÿ îðèåíòèðîâàííûé ïóòü â ñõåìå,
íà÷èíàþùèéñÿ â åå âõîäå.
Ïóñòü wi — ìàðøðóò â ìàòðè÷íîé ñõåìå Gi , i �1 2, . Íàçîâåì w w1 2, ñî÷åòàå-
ìûìè, åñëè â L ñóùåñòâóåò ôóíêöèÿ ðàçìåòêè òàêàÿ, ÷òî âûïîëíåíèå íà íåé ñõåì
G G1 2, ïðîêëàäûâàåò â íèõ ïóòè, íà÷èíàþùèåñÿ ìàðøðóòàìè w w1 2, ñîîòâåòñòâåí-
íî (ïîëàãàåì äàëåå, ÷òî ýòà ôóíêöèÿ ðàçìåòêè ïðîêëàäûâàåò ìàðøðóòû w w1 2, ).
Ñôîðìóëèðóåì íåîáõîäèìûå óñëîâèÿ ýêâèâàëåíòíîñòè ìàòðè÷íûõ ñõåì
â ìîäåëè M L( , )� .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5 19
Óñëîâèå 1. Êîíå÷íûå ðàâíîâåëèêèå ñî÷åòàåìûå ìàðøðóòû â ýêâèâàëåíòíûõ
ìàòðè÷íûõ ñõåìàõ èç ìîäåëè M L( , )� îêàí÷èâàþòñÿ â âåðøèíàõ îáùåãî òèïà.
Âñÿêîìó êîíå÷íîìó îðèåíòèðîâàííîìó ïóòè â ìàòðè÷íîé ñõåìå ñîïîñòàâèì
íåñîìóþ èì îïåðàòîðíóþ öåïî÷êó, ïîëó÷åííóþ âûïèñûâàíèåì îäèí çà äðóãèì
îïåðàòîðíûõ ñèìâîëîâ, êîòîðûå ìåòÿò ïðåîáðàçîâàòåëè, ïðèíàäëåæàùèå ïóòè,
ïðè ïðîñìîòðå ñàìîãî ïóòè îò íà÷àëà ê êîíöó; åñëè ïóòü çàâåðøàåòñÿ â ïðåîáðà-
çîâàòåëå, òî ìåòÿùèé åãî îïåðàòîðíûé ñèìâîë ó÷èòûâàòü íå áóäåì. Åñëè ïóòü —
ýòî w, òî íåñîìóþ èì öåïî÷êó îáîçíà÷èì h w( ) .
Îáîçíà÷èì [ , ]w x ïðîäîëæåíèå êîíå÷íîãî ìàðøðóòà w, íå îêàí÷èâàþùåãîñÿ
â âûõîäå ñõåìû èëè â ïóñòîì öèêëå, íà äóãó ñ ìåòêîé x, ãäå x X� .
Óñëîâèå 2. Ïóñòü w w1 2, — êîíå÷íûå ðàâíîâåëèêèå ñî÷åòàåìûå ìàðøðóòû
â ýêâèâàëåíòíûõ ìàòðè÷íûõ ñõåìàõ èç ìîäåëè M L( , )� , èìåþùèå ïðîäîëæåíèå.
Òîãäà, åñëè h w h w( ) ~ ( )1 2
�
, ñî÷åòàåìûìè â ñõåìàõ ÿâëÿþòñÿ ìàðøðóòû [ , ]w x1 ,
[ , ]w x2 ïðè ëþáîì íàáîðå x èç X , â ïðîòèâíîì ñëó÷àå ñî÷åòàåìû ìàðøðóòû
[ , ]w x1 1 , [ , ]w x2 2 äëÿ ëþáûõ íàáîðîâ x x1 2, èç X .
Ñîïðÿæåííûìè â ìàòðè÷íûõ ñõåìàõ èç ìîäåëè M L( , )� íàçûâàþòñÿ èõ âåð-
øèíû � �1 2, , â êîòîðûõ îêàí÷èâàþòñÿ ñî÷åòàåìûå ìàðøðóòû, íåñóùèå �-ýêâèâà-
ëåíòíûå öåïî÷êè.
Óñëîâèå 3. Ïóñòü � �1 2, — ñîïðÿæåííûå ïðåîáðàçîâàòåëè â ýêâèâàëåíòíûõ
ìàòðè÷íûõ ñõåìàõ èç ìîäåëè M L( , )� , ïîìå÷åííûå ðàçëè÷íûìè îïåðàòîðíûìè
ñèìâîëàìè. Òîãäà èç âåðøèí � �1 2, â ñõåìàõ âûðàñòàþò êóñòû îáùåãî ìàðêåðà.
Êóñòîì â ìàòðè÷íîé ñõåìå, âûðàñòàþùèì èç ïðåîáðàçîâàòåëÿ �, íàçûâàåòñÿ
ïîäãðàô ñõåìû, èíäóöèðóåìûé ìíîæåñòâîì V ïðåîáðàçîâàòåëåé ñõåìû è ñîäåð-
æàùèé âñå èíöèäåíòíûå èì äóãè. Ïðè ýòîì êàê âåðøèíû èç V , òàê è èíöèäåíò-
íûå èì äóãè ñîõðàíÿþò ïðèñâîåííûå èì â ñõåìå ìåòêè, à ñàì ïîäãðàô óäîâëåò-
âîðÿåò ñëåäóþùèì òðåáîâàíèÿì: âåðøèíà � ïðèíàäëåæèò ìíîæåñòâó V ; âñå âåð-
øèíû èç V ðàçáèâàþòñÿ íà óðîâíè ïî ïðèçíàêó èõ óäàëåííîñòè îò �; óðîâíè
íóìåðóþòñÿ ÷èñëàìè 0 1, , ,� k, ãäå k � 1; óðîâåíü ñ íîìåðîì 0 ñîñòîèò èç âåðøè-
íû �; êàêîé áû íè áûëà âåðøèíà, ïðèíàäëåæàùàÿ óðîâíþ ñ íîìåðîì i,
i k� 0 1 1, , ,� , âñå äóãè èç íåå âåäóò â âåðøèíû óðîâíÿ ñ íîìåðîì i
1; âñå ïóòè
èç âåðøèíû � ê âåðøèíàì k-ãî óðîâíÿ íåñóò ïîëíûå îïåðàòîðíûå öåïî÷êè,
�-ýêâèâàëåíòíûå ìåæäó ñîáîé. Êëàññ �-ýêâèâàëåíòíîñòè ýòèõ öåïî÷åê
íàçûâàåòñÿ ìàðêåðîì äàííîãî êóñòà.
Ïîëíîé öåïî÷êîé, êîòîðóþ íåñåò ïóòü, îêàí÷èâàþùèéñÿ â ïðåîáðàçîâàòåëå,
íàçûâàåòñÿ öåïî÷êà, ïîëó÷åííàÿ ïðèïèñûâàíèåì ñïðàâà ñèìâîëà, ñîïîñòàâëåííî-
ãî ýòîìó ïðåîáðàçîâàòåëþ, ê öåïî÷êå, êîòîðóþ íåñåò äàííûé ïóòü.
Äàëåå êóñòû, âûðàñòàþùèå èç ñîïðÿæåííûõ ïðåîáðàçîâàòåëåé � �1 2, ñîãëàñ-
íî óñëîâèþ 3, íàçûâàþòñÿ ñîïðÿæåííûìè.
Óñëîâèìñÿ íàçûâàòü x-ïðååìíèêîì êóñòà, âûðàñòàþùåãî èç âåðøèíû �, òó
âåðøèíó, â êîòîðóþ âåäåò äóãà ñ ìåòêîé x èç âåðøèíû, ïðèíàäëåæàùåé ïîñëåä-
íåìó óðîâíþ êóñòà; çäåñü x X� .
Óñëîâèå 4. Ïóñòü F F1 2, — ñîïðÿæåííûå êóñòû â ýêâèâàëåíòíûõ ìàòðè÷íûõ
ñõåìàõ èç ìîäåëè M L( , )� . Òîãäà, êàêèì áû íè áûë íàáîð x èç X , x-ïðååìíèêàìè
êóñòîâ F F1 2, ÿâëÿþòñÿ ñîïðÿæåííûå âåðøèíû îáùåãî òèïà.
Óñëîâèÿ 1–3 äîêàçàíû â [1], óñëîâèå 4 — î÷åâèäíîå ñëåäñòâèå óñëîâèÿ 3.
3. ÀËÃÎÐÈÒÌ ÐÀÑÏÎÇÍÀÂÀÍÈß ÝÊÂÈÂÀËÅÍÒÍÎÑÒÈ ÌÀÒÐÈ×ÍÛÕ ÑÕÅÌ
ÈÇ ÓÐÀÂÍÎÂÅØÅÍÍÎÉ ÏÎËÓÃÐÓÏÏÎÂÎÉ ÌÎÄÅËÈ ÏÐÎÃÐÀÌÌ
Ñ ËÅÂÛÌ ÑÎÊÐÀÙÅÍÈÅÌ
Òåîðåìà 3. Äëÿ óðàâíîâåøåííîé ïîëóãðóïïîâîé ìîäåëè M L( , )� ñ ëåâûì ñî-
êðàùåíèåì è ðàçðåøèìîé ýêâèâàëåíòíîñòüþ � ñóùåñòâóåò àëãîðèòì, ðàñïîçíà-
þùèé ýêâèâàëåíòíîñòü åå ìàòðè÷íûõ ñõåì ïóòåì ñðàâíåíèÿ ñî÷åòàåìûõ ìàð-
øðóòîâ â ñõåìàõ.
20 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5
Äîêàçàòåëüñòâî òåîðåìû ñîñòîèò èç îïèñàíèÿ àëãîðèòìà �.
Àëãîðèòì � ñòðîèò ñïèñêè S S1 2, , ñîñòîÿùèå èç ïàð ñîïðÿæåííûõ âåðøèí
ñõåì G G1 2, , ïîìåùàÿ â S1 ïàðó èç âõîäîâ ñõåì, à òàêæå íåêîòîðûå ïàðû îäèíà-
êîâî ïîìå÷åííûõ ïðåîáðàçîâàòåëåé, â S 2 — ïàðû ðàçíîïîìå÷åííûõ ïðåîáðàçî-
âàòåëåé. Ñïèñêè S S1 2, íå ñîäåðæàò ïîâòîðÿþùèõñÿ ïàð; â êàæäîé ïàðå ïåðâàÿ
êîìïîíåíòà — âåðøèíà èç G1.
Âíà÷àëå àëãîðèòì � ïîìåùàåò â S1 ïàðó, ñîñòîÿùóþ èç âõîäîâ ñõåì G G1 2, ,
à ñïèñîê S 2 îáúÿâëÿåò ïóñòûì. Ðàáîòà àëãîðèòìà ïîäðàçäåëÿåòñÿ íà øàãè. Íà
êàæäîì øàãå îáðàáàòûâàåòñÿ ïàðà, âõîäÿùàÿ ëèáî â ñïèñîê S1, ëèáî â ñïèñîê S 2 .
Øàã ìîæåò çàêîí÷èòüñÿ îñòàíîâêîé àëãîðèòìà � ïðè âûÿâëåíèè íåýêâèâàëåíò-
íîñòè ñõåì G G1 2, ; òàêîé øàã ñ÷èòàåòñÿ íåóäà÷íî çàâåðøåííûì.  ñëó÷àå ïîëî-
æèòåëüíîãî çàâåðøåíèÿ øàãà ñïèñêè S S1 2, ïîïîëíÿþòñÿ, åñëè ýòî âîçìîæíî.
Åñëè êàæäûé øàã, âûïîëíÿåìûé àëãîðèòìîì �, óñïåøíî çàâåðøåí è â ñïèñêàõ
S S1 2, íå îñòàëîñü íåîáðàáîòàííûõ ïàð, òî àëãîðèòì � îáúÿâëÿåò ñõåìû G G1 2,
ýêâèâàëåíòíûìè è ïðåêðàùàåò ðàáîòó. Êîíå÷íîñòü ñïèñêîâ S S1 2, ãàðàíòèðóåò
çàâåðøåíèå ðàáîòû àëãîðèòìà.
Îïèøåì øàã ðàáîòû àëãîðèòìà �.
Ñëó÷àé 1. Îáðàáàòûâàåìàÿ ïàðà ( , )� �1 2 âõîäèò â ñïèñîê S1. Òîãäà àëãîðèòì �
âûïîëíÿåò äåéñòâèå ïî ïðîäîëæåíèþ ñî÷åòàåìûõ ìàðøðóòîâ, çàâåðøàþùèõñÿ
â âåðøèíàõ � �1 2, . Ïåðåáèðàþòñÿ îäèí çà äðóãèì íàáîðû èç X è îïðåäåëÿþòñÿ
x-ïðååìíèêè âåðøèí � �1 2, . Åñëè îíè ðàçíîòèïíû, òî íàðóøåíî óñëîâèå 1 è àë-
ãîðèòì � îñòàíàâëèâàåòñÿ, âûÿâèâ íåýêâèâàëåíòíîñòü ñõåì G G1 2, . Åñëè äëÿ ëþ-
áîãî x x-ïðååìíèêè âåðøèí � �1 2, îäíîòèïíû, òî òå èç íèõ, êîòîðûå ÿâëÿþòñÿ
ïðåîáðàçîâàòåëÿìè, ñîñòàâëÿþò ïàðû ñîïðÿæåííûõ âåðøèí, ïîäëåæàùèå ïðî-
âåðêå: íóæíî ëè âêëþ÷èòü ïàðó â ñïèñîê S1 èëè â ñïèñîê S 2 . Ïðè ïîïîëíåíèè
ñïèñêîâ âêëþ÷àþòñÿ òîëüêî íå ñîäåðæàùèåñÿ â íèõ ïàðû.
Ñëó÷àé 2. Îáðàáàòûâàåìàÿ ïàðà ( , )� �1 2 âõîäèò â ñïèñîê S 2 . Òîãäà â öåëÿõ
ïðîäîëæåíèÿ ñî÷åòàåìûõ ìàðøðóòîâ, çàêàí÷èâàþùèõñÿ â âåðøèíàõ � �1 2, , àëãî-
ðèòì � ïðîâåðÿåò âûïîëíåíèå óñëîâèÿ 3. Ñòðîèòñÿ òàáëèöà, ýëåìåíòàìè êîòîðîé
ÿâëÿþòñÿ ÷åòâåðêè âèäà
( , , , )u u h h1 2 1 2 , (1)
â êîòîðûõ u u1 2, — âåðøèíû ñõåì G G1 2, ñîîòâåòñòâåííî, h h1 2, — öåïî÷êè èç Y * .
Ïåðâàÿ ñòðîêà òàáëèöû ñîäåðæèò åäèíñòâåííóþ ÷åòâåðêó ( , , , )� �1 2 1 2y y , ãäå
yi — ìåòêà âåðøèíû � i , i �1 2, .
Ïóñòü ïîñòðîåíà j-ÿ ñòðîêà òàáëèöû, j � 1. Îíà îáúÿâëÿåòñÿ ïîñëåäíåé â òàá-
ëèöå, åñëè â ïðèíàäëåæàùèõ åé ÷åòâåðêàõ âñå ó÷àñòâóþùèå â íèõ îïåðàòîðíûå öå-
ïî÷êè ýêâèâàëåíòíû ìåæäó ñîáîé. Äëÿ ïðîâåðêè ïðèìåíÿåòñÿ àëãîðèòì, ðàñïîçíà-
þùèé ýêâèâàëåíòíîñòü îòíîøåíèÿ �. Òîãäà óñëîâèå 3 íà äàííîì øàãå âûïîëíåíî.
Åñëè j-ÿ ñòðîêà íå ïîñëåäíÿÿ, ïðåäïðèíèìàþòñÿ äåéñòâèÿ ïî ïîñòðîåíèþ ( )j
1 -é
ñòðîêè. Ïðîñìàòðèâàþòñÿ îäíà çà äðóãîé ÷åòâåðêè, ïðèíàäëåæàùèå j-é ñòðîêå.
Ïóñòü (1) — äîñòèãíóòàÿ â ïðîöåññå ïîñòðîåíèÿ ÷åòâåðêà. Åñëè h h1 2~
�
, òî
äëÿ (1) ïåðåáèðàþòñÿ âñå íàáîðû èç X ; ýòî ïîäñêàçûâàåò óñëîâèå 2 äëÿ ïðîäîë-
æåíèÿ ñî÷åòàåìûõ ìàðøðóòîâ, îêàí÷èâàþùèõñÿ â âåðøèíàõ u u1 2, . Äëÿ î÷åðåä-
íîãî íàáîðà x íàõîäÿòñÿ x-ïðååìíèêè âåðøèí u u1 2, ; îáîçíà÷èì èõ � �u u1 2, ñîîòâåò-
ñòâåííî. Åñëè îíè íå ïðåîáðàçîâàòåëè, òî íàðóøåíî óñëîâèå 3 è àëãîðèòì � îñòà-
íàâëèâàåòñÿ, âûÿâèâ íåýêâèâàëåíòíîñòü ñõåì G G1 2, .
Äîïóñòèì, ÷òî � �u u1 2, — ïðåîáðàçîâàòåëè, � �y y1 2, — ïðèïèñàííûå èì îïåðà-
òîðíûå ñèìâîëû. Òîãäà ôîðìèðóåòñÿ ÷åòâåðêà
( , , , )� � � �u u h h1 2 1 2 , (2)
ãäå � � �h h yi i i , i �1 2, .  ñëó÷àå, êîãäà ÷åòâåðêà (2) íå ñîâïàäàåò íè ñ îäíîé
óæå ïîñòðîåííîé ÷åòâåðêîé ( )j
1 -é ñòðîêè, óñëîâèåì åå âêëþ÷åíèÿ â ýòó
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5 21
ñòðîêó ÿâëÿåòñÿ òðåáîâàíèå: �u1 íå ñîâïàäàåò ñ ïåðâîé êîìïîíåíòîé íè â îä-
íîé èç ÷åòâåðîê âñåõ ïðåäûäóùèõ ñòðîê òàáëèöû, à �u2 — ñî âòîðîé êîìïîíåí-
òîé. Î÷åâèäíî, ÷òî íàðóøåíèå ýòîãî òðåáîâàíèÿ îçíà÷àåò íàðóøåíèå óñëîâèÿ 3,
ò.å. àëãîðèòì � îñòàíàâëèâàåòñÿ, êîíñòàòèðóÿ íåýêâèâàëåíòíîñòü ñõåì G G1 2, .
Âêëþ÷åíèåì ÷åòâåðêè (2) â ( )j
1 -þ ñòðîêó îïåðàöèè àëãîðèòìà � ñ âûáðàí-
íûì íàáîðîì x äëÿ ÷åòâåðêè (1) çàâåðøåíû. Åñëè íå èñ÷åðïàíû íàáîðû â X , òî äëÿ
÷åòâåðêè (1) ðàññìàòðèâàåòñÿ äðóãîé íàáîð, à åñëè îíè èñ÷åðïàíû, òî èç j-é ñòðîêè
áåðåòñÿ ñëåäóþùàÿ ÷åòâåðêà, è òàê äî ïîëíîãî èñ÷åðïàíèÿ j-é ñòðîêè â ñèòóàöèè,
êîãäà àëãîðèòì � íå îñòàíîâèëñÿ, îáíàðóæèâ íåýêâèâàëåíòíîñòü ñõåì G G1 2, .
Åñëè â ÷åòâåðêå (1) îòíîøåíèå h h1 2~
�
íå âûïîëíÿåòñÿ, òî ðàáîòà àëãîðèòìà �
îòëè÷àåòñÿ îò îïèñàííîé âûøå òîëüêî òåì, ÷òî ñîãëàñíî óñëîâèþ 2 ïåðåáèðàþò-
ñÿ ïàðû èç X X� è äëÿ î÷åðåäíîé ïàðû x x1 2, ñòðîÿòñÿ x1-ïðååìíèê âåðøèíû u1
è x2-ïðååìíèê âåðøèíû u2 .
Ïðåäïîëîæèì, ÷òî óñëîâèå 3, ïðîâåðÿåìîå äëÿ ïàðû ( , )� �1 2 , âûïîëíåíî.
Òîãäà àëãîðèòì � ïðîâåðÿåò, âûïîëíåíî ëè óñëîâèå 4. Ïðîñìàòðèâàþòñÿ íàáîðû
èç X , è äëÿ î÷åðåäíîãî íàáîðà x óñòàíàâëèâàåòñÿ, èìåþò ëè îáùèé òèï x-ïðååì-
íèêè âñåõ âåðøèí, ïðèíàäëåæàùèõ ÷åòâåðêàì ïîñëåäíåé ñòðîêè ïîñòðîåííîé
òàáëèöû. Åñëè íå èìåþò, òî àëãîðèòì � îñòàíàâëèâàåòñÿ, êîíñòàòèðóÿ
íåýêâèâàëåíòíîñòü ñõåì G G1 2, .
Äîïóñòèì, ÷òî óñëîâèå 4 äëÿ ïàðû ( , )� �1 2 âûïîëíåíî. Òîãäà àëãîðèòìîì
ïîñòðîåíî ìíîæåñòâî ïàð ñîïðÿæåííûõ âåðøèí ñõåì G G1 2, . Ïàðû ñîïðÿæåííûõ
ïðåîáðàçîâàòåëåé, íå ñîäåðæàùèåñÿ â ñïèñêàõ S S1 2, , ïîïîëíÿþò ýòè ñïèñêè.
Î÷åâèäíî, ÷òî àëãîðèòì � äåéñòâèòåëüíî ðàñïîçíàåò, ÿâëÿþòñÿ èëè íåò ýêâè-
âàëåíòíûìè ñõåìû G G1 2, .
Òåîðåìà 3 äîêàçàíà.
Ðàññìîòðèì òåïåðü îöåíêó âðåìåííîé ñëîæíîñòè àëãîðèòìà �. Èç îïèñàíèÿ
äàííîãî àëãîðèòìà âèäíî, ÷òî â íåì íàèáîëåå åìêîé ÿâëÿåòñÿ ðàáîòà ïî ïðîâåð-
êå óñëîâèÿ 3. Ñîçäàâàåìàÿ ïðè ýòîì òàáëèöà ÷åòâåðîê òàêîâà, ÷òî â íåé êàæäàÿ
ñëåäóþùàÿ ñòðîêà ïî ñâîåé äëèíå ìîæåò ïðåâûøàòü äëèíó ïðåäûäóùåé ñòðîêè
â | |X 2 ðàç, ãäå | |X — ÷èñëî ýëåìåíòîâ â ìíîæåñòâå X . Ïîñêîëüêó êîëè÷åñòâî
ñòðîê â òàáëèöå ìîæåò äîñòèãàòü âåëè÷èíû n, ãäå n — ìàêñèìóì ÷èñëà âåðøèí
â ñõåìàõ G G1 2, , ïðèõîäèì ê çàêëþ÷åíèþ: â îáùåì ñëó÷àå àëãîðèòì � ýêñïîíåí-
öèàëåí ïî ñëîæíîñòè.
 ñëåäóþùåì ðàçäåëå ðàññìàòðèâàåòñÿ ïîäìíîæåñòâî óðàâíîâåøåííûõ ïî-
ëóãðóïïîâûõ ìîäåëåé ïðîãðàìì ñ ëåâûì ñîêðàùåíèåì, äëÿ êîòîðîãî àëãîðèòì �
ïðè ïîäõîäÿùåé åãî ìîäèôèêàöèè áóäåò èìåòü ïðèåìëåìóþ ñëîæíîñòü.
4. ÑËÓ×ÀÉ ÓÐÀÂÍÎÂÅØÅÍÍÎÉ ÏÎËÓÃÐÓÏÏÎÂÎÉ ÌÎÄÅËÈ ÏÐÎÃÐÀÌÌ
Ñ ËÅÂÛÌ È ×ÀÑÒÈ×ÍÛÌ ÏÐÀÂÛÌ ÑÎÊÐÀÙÅÍÈÅÌ
Ââåäåì åùå îäíî îãðàíè÷åíèå íà ïàðàìåòð � ìîäåëè M L( , )� . Ïîëàãàåì, ÷òî
ýêâèâàëåíòíîñòü � îáëàäàåò ñâîéñòâîì ÷àñòè÷íîãî ïðàâîãî ñîêðàùåíèÿ, åñëè,
êàêèìè áû íè áûëè îïåðàòîðíûå öåïî÷êè h h1 2, è h èç Y * , âûïîëíÿåòñÿ èì-
ïëèêàöèÿ
h h h h h h1 2 1 2~ ~
� �
� . (3)
Èìååò ìåñòî ñëåäóþùàÿ ëåììà.
Ëåììà 1. Ïóñòü G — ìàòðè÷íàÿ ñõåìà èç ìîäåëè M L( , )� , äëÿ êîòîðîé � îá-
ëàäàåò ñâîéñòâîì ÷àñòè÷íîãî ïðàâîãî ñîêðàùåíèÿ, F — êóñò â ñõåìå G, � — ïðå-
îáðàçîâàòåëü, ÿâëÿþùèéñÿ åãî âíóòðåííåé âåðøèíîé. Òîãäà, êàêèìè áû íè áûëè
ïóòè, âåäóùèå èç êîðíÿ êóñòà F â ïðåîáðàçîâàòåëü �, îíè íåñóò �-ýêâèâàëåíòíûå
îïåðàòîðíûå öåïî÷êè.
Äîêàçàòåëüñòâî. Îáîçíà÷èì w w1 2, ïóòè, âåäóùèå â ïðåîáðàçîâàòåëü � èç
êîðíÿ êóñòà F , è ïóñòü h h1 2, — îïåðàòîðíûå öåïî÷êè, íåñîìûå ïóòÿìè w w1 2, ñî-
22 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5
îòâåòñòâåííî. Îáîçíà÷èì w êàêîé-ëèáî ïóòü èç � ê ïîñëåäíåìó óðîâíþ êóñòà F ,
è ïóñòü h — íåñîìàÿ èì ïîëíàÿ îïåðàòîðíàÿ öåïî÷êà. Ñîãëàñíî îïðåäåëåíèþ êóñòà
âûïîëíÿåòñÿ îòíîøåíèå h h h h1 2~
�
, îòêóäà íà îñíîâàíèè (3) ñëåäóåò óòâåðæäåíèå
ëåììû. Ëåììà 1 äîêàçàíà.
Äîêàæåì ñëåäóþùóþ òåîðåìó.
Òåîðåìà 4. Äëÿ óðàâíîâåøåííîé ïîëóãðóïïîâîé ìîäåëè M L( , )� ñ ëåâûì è
÷àñòè÷íûì ïðàâûì ñîêðàùåíèåì ñóùåñòâóåò àëãîðèòì, ðàñïîçíàþùèé ýêâèâà-
ëåíòíîñòü åå ìàòðè÷íûõ ñõåì ñ ïîëèíîìèàëüíîé ñëîæíîñòüþ îòíîñèòåëüíî
ñëîæíîñòè ðàñïîçíàâàíèÿ ýêâèâàëåíòíîñòè îïåðàòîðíûõ öåïî÷åê.
Äîêàçàòåëüñòâî. Îïèøåì àëãîðèòì �, íà âõîä êîòîðîãî ïîñòóïàþò ìàòðè÷-
íûå ñõåìû G G1 2, èç ìîäåëè M L( , )� .
Àëãîðèòì � ÿâëÿåòñÿ ìîäèôèêàöèåé àëãîðèòìà �, à èìåííî: ïðè ïðîâåðêå
óñëîâèÿ 3 äîïîëíèòåëüíî ê äåéñòâèÿì àëãîðèòìà � äîáàâëÿþòñÿ äåéñòâèÿ, îá-
óñëîâëåííûå òåì, ÷òî ýêâèâàëåíòíîñòü � îáëàäàåò ñâîéñòâîì ÷àñòè÷íîãî ïðàâîãî
ñîêðàùåíèÿ, à çíà÷èò, ïðèìåíèìà ëåììà 1.
Îïèøåì äîïîëíèòåëüíûå äåéñòâèÿ. Ïóñòü ïðè ôîðìèðîâàíèè ( )j
1 -é ñòðî-
êè ïîñòðîåíà ÷åòâåðêà (2). Òîãäà ïðîñìàòðèâàíèåì ÷åòâåðîê, óæå ñîäåðæàùèõñÿ
â ( )j
1 -é ñòðîêå, óñòàíàâëèâàåòñÿ, èìååòñÿ ëè ÷åòâåðêà ñ ïåðâîé êîìïîíåíòîé �u1.
Åñëè òàêèå ÷åòâåðêè åñòü, òî ôèêñèðóåòñÿ áëèæàéøàÿ èç íèõ ê íà÷àëó ñòðîêè.
Ïóñòü òðåòüÿ êîìïîíåíòà âûáðàííîé ÷åòâåðêè — öåïî÷êà h. Òîãäà åñëè îòíîøå-
íèå �h h1 ~
�
íå âûïîëíÿåòñÿ, òî àëãîðèòì � îñòàíàâëèâàåòñÿ, êîíñòàòèðóÿ íåýêâèâà-
ëåíòíîñòü ñõåì G G1 2, .  ïðîòèâíîì ñëó÷àå â ÷åòâåðêå (2) öåïî÷êà �h1 çàìåíÿåòñÿ öå-
ïî÷êîé h . Àíàëîãè÷íûå äåéñòâèÿ âûïîëíÿþòñÿ àëãîðèòìîì � äëÿ êîìïîíåíòû �u2 .
Àëãîðèòì � îïèñàí.
Ðàññìîòðèì âåðõíþþ îöåíêó åãî âðåìåííîé ñëîæíîñòè. Ïóñòü
n n n� max ( , )1 2 , ãäå ni — ÷èñëî âåðøèí â ñõåìå Gi , i �1 2, . Îáîçíà÷èì �0 àëãî-
ðèòì, ðàñïîçíàþùèé �-ýêâèâàëåíòíîñòü îïåðàòîðíûõ öåïî÷åê èç Y * . Ïðåäïî-
ëàãàåì èçâåñòíîé ôóíêöèþ f k( ), îïðåäåëÿþùóþ îöåíêó ñëîæíîñòè àëãîðèòìà �0
ïðè ðàñïîçíàâàíèè èì �-ýêâèâàëåíòíîñòè öåïî÷åê, äëèíà êîòîðûõ ðàâíà k, ãäå k —
íàòóðàëüíîå ÷èñëî. Îòìåòèì, ÷òî ôóíêöèÿ f k( ) íåóáûâàþùàÿ.
Âûäåëèì â àëãîðèòìå � åãî ïîäàëãîðèòìû:
— � �, ïðîâåðÿþùèé âûïîëíèìîñòü óñëîâèÿ 3;
— � ��, ïðîâåðÿþùèé âûïîëíèìîñòü óñëîâèÿ 4.
Îòíåñåì ê àòîìàðíûì ñëåäóþùèå îïåðàöèè àëãîðèòìà �: óñòàíîâëåíèå òèïà
âåðøèíû ñõåìû; ñðàâíåíèå òèïîâ âåðøèí íà ðàâåíñòâî; ñðàâíåíèå âåðøèí ñõåì
íà ðàâåíñòâî; îòûñêàíèå x-ïðååìíèêà âåðøèíû ñõåìû; ïðèïèñûâàíèå ê öåïî÷êå
îïåðàòîðíîãî ñèìâîëà.
Ïîñêîëüêó èíòåðåñ ïðåäñòàâëÿåò âåðõíÿÿ îöåíêà ñëîæíîñòè àëãîðèòìà �,
à íàèáîëåå ñëîæíûì â � ÿâëÿåòñÿ ïîäàëãîðèòì � �, ïðåäïîëàãàåì, ÷òî ñïèñîê S1
ïóñò, à ñïèñîê S 2 ñîäåðæèò n n1 2 ýëåìåíòîâ.
Òàêèì îáðàçîì, àëãîðèòì � �, à òàêæå àëãîðèòì � �� ïðèìåíÿþòñÿ n n1 2 ðàç.
Îöåíèì ñâåðõó ÷èñëî äåéñòâèé, âûïîëíÿåìûõ àëãîðèòìîì � �.  òàáëèöå ÷åò-
âåðîê, êîòîðóþ ñòðîèò àëãîðèòì � �, íå áîëåå n ñòðîê è íå áîëåå n2 ýëåìåíòîâ;
ïåðâîå î÷åâèäíî, à âòîðîå ñëåäóåò èç äîïîëíèòåëüíûõ äåéñòâèé àëãîðèòìà �.
Ïóñòü (1) — ðàññìàòðèâàåìàÿ àëãîðèòìîì � � ÷åòâåðêà, íå ïðèíàäëåæàùàÿ íè
ïåðâîé, íè ïîñëåäíåé ñòðîêå òàáëèöû. Äëÿ íåå ïðîâåðÿåòñÿ, ýêâèâàëåíòíû èëè
íåò öåïî÷êè h h1 2, , çàòåì îòûñêèâàþòñÿ x-ïðååìíèêè, ñîñòàâëÿþùèå ïàðû â êî-
ëè÷åñòâå, íå áîëüøåì | |X 2 . Äëÿ êàæäîé ïàðû ïðèìåíÿåòñÿ îïåðàöèÿ, óñòàíàâëè-
âàþùàÿ, ñîñòîèò ëè îíà èç ïðåîáðàçîâàòåëåé. Çíà÷èò, îáùåå êîëè÷åñòâî äåé-
ñòâèé ïðè ïîëîæèòåëüíîì èñõîäå íå ïðåâûøàåò ÷èñëà N N f n X0 0
22, ( ) | |�
.
Ó÷èòûâàåì, ÷òî äëèíû öåïî÷åê h h1 2, íå ïðåâûøàþò ÷èñëà n; ê f n( ) äîáàâëÿåòñÿ
÷èñëî àòîìàðíûõ îïåðàöèé.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5 23
Ïóñòü ïîñòðîåíà ÷åòâåðêà òèïà (2). Àëãîðèòì � � îñóùåñòâëÿåò ïåðâóþ ïðî-
âåðêó: ïðèíàäëåæèò ëè õîòÿ áû îäíà èç âåðøèí � �u u1 2, êàêîé-ëèáî ÷åòâåðêå èç
ñòðîê òàáëèöû, ïðåäøåñòâóþùèõ ðàññìàòðèâàåìîé ñòðîêå. Ïðè ïîëîæèòåëüíîì
èñõîäå âûïîëíÿþòñÿ îïåðàöèè â êîëè÷åñòâå, íå ïðåâûøàþùåì ÷èñëà N1,
N n1
22� log( ) , ïîñêîëüêó â ïðåäøåñòâóþùèõ ñòðîêàõ íå áîëåå ÷åì n2 ÷åòâåðîê.
Äàëåå àëãîðèòì � � âûïîëíÿåò âòîðóþ ïðîâåðêó: ñîâïàäàåò ëè �u1 ñ ïåðâîé
êîìïîíåíòîé êàêîé-ëèáî ÷åòâåðêè, ïðèíàäëåæàùåé ðàññìàòðèâàåìîé ñòðîêå;
åñëè ñîâïàäàåò è â îáíàðóæåííîé ÷åòâåðêå òðåòüÿ êîìïîíåíòà — öåïî÷êà h, òî
öåïî÷êè �h1 è h ñðàâíèâàþòñÿ íà �-ýêâèâàëåíòíîñòü.  ñëó÷àå, åñëè îíè �-ýêâè-
âàëåíòíû, îñóùåñòâëÿåòñÿ çàìåíà öåïî÷êè �h1 öåïî÷êîé h . Ïðè ïîëîæèòåëüíîì
èñõîäå êàê âòîðîé ïðîâåðêè, òàê è ïîñëåäóþùåé çà íåé çàìåíû öåïî÷êè àëãî-
ðèòì � � âûïîëíÿåò êîëè÷åñòâî îïåðàöèé, íå ïðåâûøàþùåå ÷èñëà N 2 ,
N n f n n2
2
�
log( ) ( ( ) ). Çäåñü ó÷èòûâàåòñÿ, ÷òî êîëè÷åñòâî ïðîâåðÿåìûõ ÷åòâå-
ðîê íå ïðåâûøàåò ÷èñëà n2 , à öåïî÷êè �h1, h èìåþò äëèíó, íå ïðåâûøàþùóþ n ;
çàìåíà öåïî÷êè �h1 öåïî÷êîé h âûïîëíÿåòñÿ íå áîëåå ÷åì çà n îïåðàöèé.
Òðåòüÿ ïðîâåðêà, îñóùåñòâëÿåìàÿ àëãîðèòìîì �� , îòëè÷àåòñÿ îò ïðåäûäóùåé
òåì, ÷òî âìåñòî �u1 ðàññìàòðèâàåòñÿ �u2 . Îíà ïîòðåáóåò êîëè÷åñòâî îïåðàöèé, íå
ïðåâûøàþùåå ÷èñëà N 2 .
Ïðè ïîëîæèòåëüíîì èñõîäå âòîðîé è òðåòüåé ïðîâåðîê â ñëó÷àå, êîãäà îáíà-
ðóæåííûå äëÿ �u1 è �u2 ÷åòâåðêè íå ñîâïàäàþò, ÷åòâåðêà (2), âîçìîæíî ïîäïðàâ-
ëåííàÿ, âêëþ÷àåòñÿ â ðàññìàòðèâàåìóþ ñòðîêó.
Òàêèì îáðàçîì, ðàáîòà àëãîðèòìà � � ñ ÷åòâåðêîé (2) çàâåðøåíà.
Åñëè ðàññìàòðèâàåìàÿ ñòðîêà ïîëíîñòüþ ïîñòðîåíà, òî àëãîðèòì � � âûïîë-
íÿåò ÷åòâåðòóþ ïðîâåðêó: ÿâëÿåòñÿ ëè ýòà ñòðîêà ïîñëåäíåé â òàáëèöå. Ïðè ýòîì
ïðîñìàòðèâàþòñÿ âñå ÷åòâåðêè äàííîé ñòðîêè (èõ íå áîëåå n2), è äëÿ êàæäîé,
âîçìîæíî äâàæäû, âûïîëíÿåòñÿ àëãîðèòì �0 (åñëè â ÷åòâåðêå òðåòüÿ è ÷åòâåðòàÿ
êîìïîíåíòû �-ýêâèâàëåíòíû, òî îäíà èç íèõ ñðàâíèâàåòñÿ íà �-ýêâèâàëåíòíîñòü
ñ îïåðàòîðíîé öåïî÷êîé, âõîäÿùåé â ïåðâóþ ÷åòâåðêó äàííîé ñòðîêè). Ïðè ïî-
ëîæèòåëüíîì èñõîäå ÷åòâåðòîé ïðîâåðêè àëãîðèòì � � âûïîëíÿåò êîëè÷åñòâî îïå-
ðàöèé, íå ïðåâûøàþùåå ÷èñëà N 3 , N n f n3
22� ( ) .
Òàêèì îáðàçîì, ñëîæíîñòü àëãîðèòìà � � îãðàíè÷åíà ñâåðõó ÷èñëîì
n N N N N2
0 1 2 32( )
, ïîñêîëüêó ïðè ïîñòðîåíèè òàáëèöû êàæäàÿ èç ÷åòâå-
ðîê òèïà (1) èëè (2) âñòðå÷àåòñÿ íå áîëåå n2 ðàç.
Ðàññìîòðèì àëãîðèòì ���. Îí àíàëèçèðóåò âñå ÷åòâåðêè ïîñëåäíåé ñòðîêè
òàáëèöû; äëÿ ïåðâîé èç íèõ ôèêñèðóåòñÿ òèï x-ïðååìíèêîâ âåðøèí, âõîäÿùèõ
â ÷åòâåðêó, è òàê äëÿ ëþáîãî x èç X (â ïðåäïîëîæåíèè, ÷òî òèïû ñîâïàäàþò). Äà-
ëåå äëÿ êàæäîé ïîñëåäóþùåé ÷åòâåðêè è ëþáîãî x èç X ñðàâíèâàþòñÿ òèïû x-ïðå-
åìíèêîâ âåðøèí, âõîäÿùèõ â ýòó ÷åòâåðêó, è ïðîâåðÿåòñÿ, ñîâïàäàåò ëè èõ îáùèé
òèï ñ òèïîì x-ïðååìíèêîâ âåðøèí èç ïåðâîé ÷åòâåðêè. Îïèñàííûå äåéñòâèÿ ïî-
òðåáóþò êîëè÷åñòâî îïåðàöèé, íå ïðåâûøàþùåå ÷èñëà N 4 , N n X4
22� | | .
Êðîìå òîãî, àëãîðèòì � �� ðåøàåò âîïðîñ: âêëþ÷èòü ëè ïàðó x-ïðååìíèêîâ âåð-
øèí â ñëó÷àå, êîãäà îíà ñîñòàâëåíà ïðåîáðàçîâàòåëÿìè, â ñïèñîê S 2 . Íà ýòî òðåáó-
åòñÿ êîëè÷åñòâî îïåðàöèé, íå ïðåâîñõîäÿùåå ÷èñëà N 5 , N n n X5
2 2
� log( ) | | .
Àíàëèçèðóÿ ïîëó÷åííûå âåðõíèå îöåíêè ñëîæíîñòè àëãîðèòìîâ � � è ��� è
ó÷èòûâàÿ, ÷òî àëãîðèòìû âûïîëíÿþòñÿ íå áîëåå n2 ðàç, ïðèõîäèì ê çàêëþ÷å-
íèþ: óòâåðæäåíèå òåîðåìû 4 î ñëîæíîñòè àëãîðèòìà � ñïðàâåäëèâî.
Îòìåòèì, ÷òî ñòàðøåå (ïî çàâèñèìîñòè îò n) ñëàãàåìîå â ïîëó÷åííîé îöåíêå
èìååò âèä Cn f n6 ( ) , ãäå C — êîíñòàíòà, íå çàâèñÿùàÿ îò n .
Òåîðåìà 4 äîêàçàíà.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ï î ä ë î â ÷ å í ê î Ð . È . Òåõíèêà ñëåäîâ â ðàçðåøåíèè ïðîáëåìû ýêâèâàëåíòíîñòè â àëãåáðàè÷åñêèõ
ìîäåëÿõ ïðîãðàìì // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2009. — ¹ 5. — Ñ. 25–37.
Ïîñòóïèëà 18.02.2011
24 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5
|