Техника следов в разрешении проблемы эквивалентности в алгебраических моделях программ
Розглянуто алгебраїчні моделі послідовних програм без процедур. Досліджено питання застосування техніки слідів для розв’язання проблеми еквівалентності в таких моделях. Виділено моделі, що названі зрівноваженими півгрупами з лівим скороченням, до яких дійсно застосовна техніка слідів при розв’язанні...
Збережено в:
| Дата: | 2009 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/44398 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Техника следов в разрешении проблемы эквивалентности в алгебраических моделях программ / Р.И. Подловченко // Кибернетика и системный анализ. — 2009. — № 5. — С. 25-37. — Бібліогр.: 9 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-44398 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-443982013-06-02T03:02:45Z Техника следов в разрешении проблемы эквивалентности в алгебраических моделях программ Подловченко, Р.И. Кибернетика Розглянуто алгебраїчні моделі послідовних програм без процедур. Досліджено питання застосування техніки слідів для розв’язання проблеми еквівалентності в таких моделях. Виділено моделі, що названі зрівноваженими півгрупами з лівим скороченням, до яких дійсно застосовна техніка слідів при розв’язанні в них проблеми еквівалентності. Algebraic models of sequential programs without procedures are considered. The question of applicability of the technique of traces to equivalence checking problems for such models is investigated. Models called balanced left-cancellative semigroups are singled out for which the technique of traces provides an effective decision procedure. 2009 Article Техника следов в разрешении проблемы эквивалентности в алгебраических моделях программ / Р.И. Подловченко // Кибернетика и системный анализ. — 2009. — № 5. — С. 25-37. — Бібліогр.: 9 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/44398 519.1 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 |
2009 |
| topic_facet |
Кибернетика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/44398 |
| citation_txt |
Техника следов в разрешении проблемы эквивалентности в алгебраических моделях программ / Р.И. Подловченко // Кибернетика и системный анализ. — 2009. — № 5. — С. 25-37. — Бібліогр.: 9 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT podlovčenkori tehnikasledovvrazrešeniiproblemyékvivalentnostivalgebraičeskihmodelâhprogramm |
| first_indexed |
2025-07-04T02:49:28Z |
| last_indexed |
2025-07-04T02:49:28Z |
| _version_ |
1836682962773475328 |
| fulltext |
ÓÄÊ 519.1
Ð.È. ÏÎÄËÎÂ×ÅÍÊÎ
ÒÅÕÍÈÊÀ ÑËÅÄÎÂ Â ÐÀÇÐÅØÅÍÈÈ ÏÐÎÁËÅÌÛ
ÝÊÂÈÂÀËÅÍÒÍÎÑÒÈ Â ÀËÃÅÁÐÀÈ×ÅÑÊÈÕ ÌÎÄÅËßÕ ÏÐÎÃÐÀÌÌ
Êëþ÷åâûå ñëîâà: àëãåáðàè÷åñêàÿ ìîäåëü ïðîãðàìì, ïðîâåðêà ýêâèâàëåíòíîñòè,
òåõíèêà ñëåäîâ.
ÂÂÅÄÅÍÈÅ
Àëãåáðàè÷åñêèå ìîäåëè ïðîãðàìì ââåäåíû â [1] êàê îáîáùåíèå ñóùåñòâóþùèõ
ê òîìó âðåìåíè ìîäåëåé ïðîãðàìì äâóõ òèïîâ: ïðåäëîæåííûõ À.À. Ëÿïóíîâûì
è Þ.È. ßíîâûì â [2, 3] è Â.Ì. Ãëóøêîâûì è À.À. Ëåòè÷åâñêèì â [4].
Ê îñíîâíûì ïðîáëåìàì â ìîäåëÿõ ïðîãðàìì îòíîñèòñÿ ïðîáëåìà ôóíêöèî-
íàëüíîé ýêâèâàëåíòíîñòè ïðèíàäëåæàùèõ ìîäåëÿì ñõåì ïðîãðàìì. Åå ðåøåíèÿ,
ïîëó÷åííûå äëÿ ìîäåëåé ïðîãðàìì, ïðåäøåñòâóþùèõ àëãåáðàè÷åñêèì, åñòåñòâåí-
íûì îáðàçîì àäàïòèðóþòñÿ â ðåøåíèÿ äëÿ ïîñëåäíèõ.
Èíòåðåñ âûçâàëî ðåøåíèå, ïîëó÷åííîå À.À. Ëåòè÷åâñêèì â [5] äëÿ ñëó÷àÿ, êîã-
äà ïîëóãðóïïà îïåðàòîðîâ, èíäóöèðóþùàÿ ìîäåëü ïðîãðàìì, îáëàäàåò íåðàçëîæè-
ìîé åäèíèöåé è ëåâûì ñîêðàùåíèåì. Ñëîæíîñòü ðåøåíèÿ ýêñïîíåíöèàëüíà. Âîç-
íèêëà èäåÿ: âûäåëèòü èç ïîëóãðóïï ñ íåðàçëîæèìîé åäèíèöåé è ëåâûì ñîêðàùåíè-
åì äîñòàòî÷íî øèðîêèé êëàññ ïîëóãðóïï ñ ïîëèíîìèàëüíîé ñëîæíîñòüþ ðåøåíèÿ
ïðîáëåìû ýêâèâàëåíòíîñòè â èíäóöèðóåìûõ èìè ìîäåëÿõ ïðîãðàìì.
Èäåÿ ïîëèíîìèàëüíîãî ðåøåíèÿ âîñõîäèò ê ïðèìåíåíèþ òåõíèêè ñëåäîâ, èç-
âåñòíîé â òåîðèè ìàòåìàòè÷åñêèõ ìîäåëåé âû÷èñëåíèé [6].
Íàñòîÿùàÿ ðàáîòà ïîñâÿùåíà îïðåäåëåíèþ òðåáîâàíèé, ïðåäúÿâëÿåìûõ ê àë-
ãåáðàè÷åñêèì ìîäåëÿì ïðîãðàìì è äîñòàòî÷íûõ äëÿ èñïîëüçîâàíèÿ òåõíèêè ñëåäîâ
ïðè ðàçðåøåíèè ïðîáëåìû ýêâèâàëåíòíîñòè.
Ñ ïîìîùüþ èññëåäîâàíèé, ïðîâåäåííûõ â äàííîé ñòàòüå, óñòàíàâëèâàåòñÿ, ÷òî
òàêèì òðåáîâàíèÿì óäîâëåòâîðÿþò òàê íàçûâàåìûå óðàâíîâåøåííûå ïîëóãðóïïî-
âûå ìîäåëè ïðîãðàìì ñ ëåâûì ñîêðàùåíèåì. Çäåñü îãðàíè÷èìñÿ ôàêòîì ïðèìåíè-
ìîñòè äëÿ ýòèõ ìîäåëåé òåõíèêè ñëåäîâ ïðè ðàçðåøåíèè â íèõ ïðîáëåìû ýêâèâà-
ëåíòíîñòè. (Â ñëåäóþùåé ðàáîòå îïèøåì àëãîðèòì ðàçðåøåíèÿ ýêâèâàëåíòíîñòè.)
Îïðåäåëèì, ÷òî ïðåäñòàâëÿåò ñîáîé àëãåáðàè÷åñêàÿ ìîäåëü ïðîãðàìì. Ïðåæäå
âñåãî, îòìåòèì êîíöåïöèè, íà êîòîðûõ áàçèðóåòñÿ ââåäåíèå ýòîé ìîäåëè. Îíè
çàêëþ÷àþòñÿ â ñëåäóþùåì:
1) ìîäåëèðîâàíèå ïðîãðàìì áîëåå ïðîñòûìè îáúåêòàìè — ñõåìàìè ïðîãðàìì
îïèðàåòñÿ íà ÿâíóþ ïðåäâàðèòåëüíóþ ôîðìàëèçàöèþ ïîíÿòèÿ ïðîãðàììû;
2) ñðåäè ðàçëè÷íûõ ñïîñîáîâ ïîñòðîåíèÿ ïî ïðîãðàììå åå ñõåìû îòáèðàþòñÿ
òå, êîòîðûå îáëàäàþò ñâîéñòâîì: èç ýêâèâàëåíòíîñòè ñõåì âñåãäà âûòåêàåò ýêâèâà-
ëåíòíîñòü ïðîãðàìì, ïðåäñòàâëÿåìûõ ýòèìè ñõåìàìè.
Ñëåäîâàíèå ïðèâåäåííûì êîíöåïöèÿì ïîçâîëèò èçó÷àòü ñåìàíòè÷åñêèå
ñâîéñòâà ïðîãðàìì íà èõ ñõåìàõ.
Ðåàëèçàöèÿ äàííûõ êîíöåïöèé îñóùåñòâëÿåòñÿ ñëåäóþùèì îáðàçîì.
Ôèêñèðóåòñÿ ôîðìàëèçàöèÿ ïîñëåäîâàòåëüíîé ïðîãðàììû íàä âûáðàííûì áà-
çèñîì îïåðàòîðîâ è ëîãè÷åñêèõ óñëîâèé. Åå îñîáåííîñòü ñîñòîèò â òîì, ÷òî îíà
âîñõîäèò ê ïðåäñòàâëåíèþ ôóíêöèîíàëüíîé ñîñòàâëÿþùåé ðåàëüíîé ïðîãðàììû,
çàïèñàííîé íà àëãîðèòìè÷åñêîì ÿçûêå âûñîêîãî óðîâíÿ; ýòà ñîñòàâëÿþùàÿ —
ðàçäåë îïåðàòîðîâ.
 ôîðìàëèçîâàííîé ïðîãðàììå, â îòëè÷èå îò ðåàëüíîé, ñòðóêòóðà ïðåäñòàâëå-
íà êîíå÷íûì ãðàôîì, âåðøèíû êîòîðîãî, èñêëþ÷àÿ âõîä è âûõîä, íàãðóæåíû áà-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5 25
� Ð.È. Ïîäëîâ÷åíêî, 2009
çèñíûìè îïåðàòîðàìè è ëîãè÷åñêèìè óñëîâèÿìè. Ïðè âûïîëíåíèè ïðîãðàìì ðåà-
ëèçóþòñÿ âñå ïðèíÿòûå â àëãîðèòìè÷åñêèõ ÿçûêàõ ïîñëåäîâàòåëüíûõ ïðîãðàìì
ñðåäñòâà êîìïîçèöèè îïåðàòîðîâ, êðîìå àïïàðàòà ïðîöåäóð. Âûïîëíÿåìàÿ ïðî-
ãðàììîé ôóíêöèÿ — îòîáðàæåíèå ìíîæåñòâà ñîñòîÿíèé ïàìÿòè â ñåáÿ, ÿâëÿþùååñÿ
â îáùåì ñëó÷àå ÷àñòè÷íûì. Ýêâèâàëåíòíîñòü ïðîãðàìì ââîäèòñÿ òðåáîâàíèåì
ñîâïàäåíèÿ âûïîëíÿåìûõ èìè ôóíêöèé.
Ñõåìà ïðîãðàììû ïîëó÷àåòñÿ èç ïðîãðàììû çàìåíîé áàçèñíûõ îïåðàòîðîâ
îïåðàòîðíûìè ñèìâîëàìè, à áàçèñíûõ ëîãè÷åñêèõ óñëîâèé — ëîãè÷åñêèìè ïåðå-
ìåííûìè. Òå è äðóãèå ñîñòàâëÿþò ñèìâîëüíûé áàçèñ, íàä êîòîðûì ñòðîÿòñÿ ñõåìû.
Òàêèì îáðàçîì, ãðàô ïðîãðàììû íàñëåäóåòñÿ â åå ñõåìå. Ýòèì äîñòèãàåòñÿ ïîëîæå-
íèå: âñÿêîå ïðåîáðàçîâàíèå ñòðóêòóðû ãðàôà ñõåìû îäíîâðåìåííî ÿâëÿåòñÿ è
ïðåîáðàçîâàíèåì ñòðóêòóðû ãðàôà ïðîãðàììû, äëÿ êîòîðîé ïîñòðîåíà ñõåìà.
Äëÿ ñåìàíòè÷åñêîé òðàêòîâêè ñõåì ïðîãðàìì ââîäèòñÿ óíèâåðñàëüíàÿ ïðîöå-
äóðà âûïîëíåíèÿ ñõåìû. Ðîëü íà÷àëüíûõ äàííûõ ïðè ýòîì èãðàåò òàê íàçûâàåìàÿ
ôóíêöèÿ ðàçìåòêè, êîòîðàÿ âñÿêîé öåïî÷êå îïåðàòîðíûõ ñèìâîëîâ ñîïîñòàâëÿåò
çíà÷åíèÿ âñåõ ëîãè÷åñêèõ ïåðåìåííûõ. Òàêèì îáðàçîì îáåñïå÷èâàåòñÿ äåòåðìèíè-
ðîâàííîñòü îáõîäà ñõåìû â ïðîöåññå åå âûïîëíåíèÿ íà ôóíêöèè ðàçìåòêè. Ðåçóëü-
òàòîì âûïîëíåíèÿ ñõåìû ÿâëÿåòñÿ öåïî÷êà îïåðàòîðíûõ ñèìâîëîâ, îïèñûâàþùàÿ
ïóòü åå îáõîäà â ñëó÷àå, êîãäà îáõîä çàâåðøàåòñÿ â âûõîäå ñõåìû.
Ýêâèâàëåíòíîñòü ñõåì ïðîãðàìì íàä âûáðàííûì ñèìâîëüíûì áàçèñîì îïðåäå-
ëÿåòñÿ äâóìÿ ïàðàìåòðàìè: ìíîæåñòâîì äîïóñòèìûõ ôóíêöèé ðàçìåòêè, íà êîòî-
ðûõ âûïîëíÿþòñÿ ñõåìû, è ýêâèâàëåíòíîñòüþ öåïî÷åê îïåðàòîðíûõ ñèìâîëîâ, èñ-
ïîëüçóåìîé ïðè ñðàâíåíèè ðåçóëüòàòîâ âûïîëíåíèÿ ñõåì. Äëÿ ýêâèâàëåíòíûõ ñõåì
îáëàñòè çàâåðøåíèÿ èõ âûïîëíåíèÿ äîëæíû ñîâïàäàòü, à ðåçóëüòàòû âûïîëíå-
íèÿ áûòü ýêâèâàëåíòíû.
Ïî îïðåäåëåíèþ àëãåáðàè÷åñêàÿ ìîäåëü ïðîãðàìì íàä çàäàííûì ñèìâîëüíûì
áàçèñîì — ìíîæåñòâî âñåõ ñõåì ïðîãðàìì íàä ýòèì áàçèñîì ñ ââåäåííûì íà ìíî-
æåñòâå îòíîøåíèåì ýêâèâàëåíòíîñòè ñõåì.
 âîçíèêøåì ïàðàìåòðè÷åñêîì ìíîæåñòâå àëãåáðàè÷åñêèõ ìîäåëåé ïðîãðàìì
èçó÷åíèþ ïîäëåæàò àïïðîêñèìèðóþùèå ìîäåëè. Äëÿ ìîäåëè ýòîãî òèïà ñóùåñòâóåò
êëàññ ïðîãðàìì, ïîëó÷åííûé èíòåðïðåòàöèåé ñèìâîëüíîãî áàçèñà áàçèñîì îïåðàòîðîâ
è ëîãè÷åñêèõ óñëîâèé è òàêîé, ÷òî èç ýêâèâàëåíòíîñòè ñõåì, ïðèíàäëåæàùèõ ìîäåëè,
âñåãäà ñëåäóåò ýêâèâàëåíòíîñòü ïðîãðàìì, ïðåäñòàâëåííûõ ýòèìè ñõåìàìè.
Àïïðîêñèìèðóþùèå ìîäåëè ïîçâîëÿþò ïðèìåíèòü ê ïðîãðàììàì, ìîäåëèðóå-
ìûì ñõåìàìè, ðåçóëüòàòû ñåìàíòè÷åñêîãî àíàëèçà ñõåì.
 [7] ïîëó÷åíû äîñòàòî÷íûå óñëîâèÿ òîãî, ÷òî àëãåáðàè÷åñêàÿ ìîäåëü ïðî-
ãðàìì ÿâëÿåòñÿ àïïðîêñèìèðóþùåé. Èìè âûäåëåí øèðîêèé êëàññ ìîäåëåé.
Ïðîáëåìà ýêâèâàëåíòíîñòè â ìîäåëè ñîñòîèò â ïîñòðîåíèè àëãîðèòìà, êîòî-
ðûé, ïîëó÷èâ íà ñâîé âõîä ïàðó ñõåì èç ìîäåëè, îïðåäåëÿåò, ýêâèâàëåíòíû îíè èëè
íåò. Åñëè òàêîé àëãîðèòì íàéäåí, òî ïðîáëåìà ýêâèâàëåíòíîñòè íàçûâàåòñÿ ðàçðå-
øèìîé. Ëåãêî óâèäåòü, ÷òî àëãîðèòì, ðàñïîçíàþùèé ýêâèâàëåíòíîñòü â àïïðîêñè-
ìèðóþùåé ìîäåëè, ïðèãîäåí äëÿ ïðèìåíåíèÿ åãî ê àïïðîêñèìèðóåìûì åþ
ïðîãðàììàì.
Äàííàÿ ñòàòüÿ ñîñòîèò èç òðåõ ðàçäåëîâ. Â íàçâàíèè ýòèõ ðàçäåëîâ îòðàæåíû
ðåøàåìûå â íèõ çàäà÷è.
Êàê îòìå÷àëîñü, ñàì ôàêò ðàçðåøèìîñòè íå ÿâëÿåòñÿ íîâûì â òåîðèè ìîäåëåé
ïðîãðàìì. Îäíàêî òî îáñòîÿòåëüñòâî, ÷òî ðàçðåøèìîñòü óñòàíîâëåíà òåõíèêîé ñëå-
äîâ, ïðåäïîëàãàåò ïîñòðîåíèå ðàçðåøàþùåãî àëãîðèòìà ïîëèíîìèàëüíîé ñëîæíîñòè.
ÀËÃÅÁÐÀÈ×ÅÑÊÀß ÌÎÄÅËÜ ÏÐÎÃÐÀÌÌ, ÀÏÏÐÎÊÑÈÌÈÐÓÞÙÈÅ
ÌÎÄÅËÈ È u-ÑÕÅÌÛ Â ÍÈÕ
Êàæäàÿ àëãåáðàè÷åñêàÿ ìîäåëü ïðîãðàìì ñòðîèòñÿ íàä äâóìÿ êîíå÷íûìè è íåïå-
ðåñåêàþùèìèñÿ àëôàâèòàìè — Y è P. Ýëåìåíòû Y íàçûâàþòñÿ îïåðàòîðíûìè
ñèìâîëàìè, ýëåìåíòû P — ëîãè÷åñêèìè ïåðåìåííûìè. Êàæäàÿ ëîãè÷åñêàÿ
26 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5
ïåðåìåííàÿ ïðèíèìàåò çíà÷åíèÿ èç ìíîæåñòâà { }0 1, . Äàëåå àëôàâèòû Y è P îñòà-
þòñÿ íåèçìåííûìè è ïîýòîìó íå óïîìèíàþòñÿ â íàèìåíîâàíèÿõ çàâèñÿùèõ îò
íèõ ïîíÿòèé è êîíñòðóêöèé.
Îáúåêòàìè ìîäåëè ÿâëÿþòñÿ ñõåìû ïðîãðàìì. Ñõåìà çàäàåòñÿ êîíå÷íûì îðèåí-
òèðîâàííûì ãðàôîì. Â íåì âûäåëåíû äâå âåðøèíû: âõîä — âåðøèíà áåç âõîäÿùèõ â
íåå äóã è ñ åäèíñòâåííîé èñõîäÿùåé äóãîé è âûõîä — âåðøèíà áåç èñõîäÿùèõ äóã.
Îñòàëüíûå âåðøèíû ãðàôà, åñëè òàêîâûå èìåþòñÿ, ïî ñâîåìó òèïó äåëÿòñÿ íà ïðåîá-
ðàçîâàòåëè è ðàñïîçíàâàòåëè. Èç êàæäîãî ïðå-
îáðàçîâàòåëÿ èñõîäèò îäíà äóãà, è åìó ñîïîñ-
òàâëåí ñèìâîë èç Y . Èç êàæäîãî ðàñïîçíàâàòåëÿ
èñõîäÿò äâå äóãè, íåñóùèå ìåòêè 0 è 1 ñîîòâå-
òñòâåííî, è åìó ñîïîñòàâëåíà ëîãè÷åñêàÿ ïåðå-
ìåííàÿ èç P.
Ïðèìåð ñõåìû ïðèâåäåí íà ðèñ. 1. Îíà
ïðåäñòàâëÿåò ñîáîé êîìïîçèöèþ äâóõ öèêëîâ:
îäíîãî — ñ ïðåäóñëîâèåì p1, à äðóãîãî —
ñ ïîñòóñëîâèåì p2 .
Ôóíêöèîíàëüíîå îïèñàíèå ñõåìû ñâÿçà-
íî ñ ïðîöåññîì åå âûïîëíåíèÿ, êîòîðîå îñó-
ùåñòâëÿåòñÿ íà òàê íàçûâàåìîé ôóíêöèè ðàçìåòêè. Îïðåäåëèì åå.
Ââåäåì ìíîæåñòâî X , X x x P� �{ { }}| : ,0 1 , ýëåìåíòû êîòîðîãî áóäåì íàçûâàòü
íàáîðàìè çíà÷åíèé âñåõ ëîãè÷åñêèõ ïåðåìåííûõ, èëè ïðîñòî íàáîðàìè.
Ââåäåì ìíîæåñòâî Y * , ýëåìåíòû êîòîðîãî — ñëîâà â àëôàâèòå Y , íàçûâàåìûå
äàëåå îïåðàòîðíûìè öåïî÷êàìè.
Ïî îïðåäåëåíèþ ôóíêöèÿ ðàçìåòêè — îòîáðàæåíèå ìíîæåñòâà Y * â ìíîæåñ-
òâî X . Ìíîæåñòâî âñåõ ôóíêöèé ðàçìåòêè íàä Y è P îáîçíà÷èì L.
Îïèøåì âûïîëíåíèå ñõåìû íà ôóíêöèè ðàçìåòêè.
Ïóñòü G — ñõåìà íàä Y è P, � — ôóíêöèÿ èç L. Ïðîöåññ âûïîëíåíèÿ G íà �
ñîñòîèò â ïðîäâèæåíèè ïî ñõåìå G, ñîïðîâîæäàåìîì íàêîïëåíèåì îïåðàòîðíîé öå-
ïî÷êè. Îáõîä ñõåìû îñóùåñòâëÿåòñÿ äåòåðìèíèðîâàííûì îáðàçîì ïî ñëåäóþùèì
ïðàâèëàì. Îí íà÷èíàåòñÿ âî âõîäå ñõåìû G ïðè ïóñòîé îïåðàòîðíîé öåïî÷êå è èäåò
â íàïðàâëåíèè äóãè, èñõîäÿùåé èç ïîñåùàåìîé âåðøèíû ñõåìû.  ñëó÷àå, êîãäà
ýòî — âõîä èëè ïðåîáðàçîâàòåëü, èñõîäÿùàÿ äóãà åäèíñòâåííà. Ïðîõîæäåíèå ÷åðåç
ïðåîáðàçîâàòåëü ñîïðîâîæäàåòñÿ ïðèïèñûâàíèåì ñïðàâà ê òåêóùåé îïåðàòîðíîé
öåïî÷êå ñèìâîëà, ñîïîñòàâëåííîãî ýòîìó ïðåîáðàçîâàòåëþ. Ïåðåõîä ÷åðåç ðàñïîç-
íàâàòåëü íå èçìåíÿåò òåêóùåé îïåðàòîðíîé öåïî÷êè è ñîñòîèò â âûáîðå îäíîé èç
äâóõ èñõîäÿùèõ èç íåãî äóã, à èìåííî: âûáèðàåòñÿ äóãà, ïîìå÷åííàÿ ÷èñëîì �h p( ),
ãäå h — òåêóùàÿ îïåðàòîðíàÿ öåïî÷êà, à p — ïðèïèñàííàÿ ðàñïîçíàâàòåëþ ëîãè-
÷åñêàÿ ïåðåìåííàÿ. Âûïîëíåíèå ñõåìû çàâåðøàåòñÿ ïðè äîñòèæåíèè åå âûõîäà.
 ýòîì ñëó÷àå ïîëàãàåì, ÷òî ñõåìà G îñòàíîâèëàñü íà ôóíêöèè �, è ðåçóëüòàòîì åå
âûïîëíåíèÿ ñ÷èòàåì íàêîïëåííóþ ê ìîìåíòó îñòàíîâêè îïåðàòîðíóþ öåïî÷êó.
Î ïóòè â ñõåìå G, êîòîðûì èäåò åå âûïîëíåíèå íà ôóíêöèè �, ãîâîðèì êàê î ïðî-
êëàäûâàåìîì â G ôóíêöèåé � .
Àëãåáðàè÷åñêàÿ ìîäåëü ïðîãðàìì íàä Y è P ïî îïðåäåëåíèþ ïðåäñòàâëÿåò ñî-
áîé ìíîæåñòâî ñõåì ïðîãðàìì íàä Y è P ñ çàäàííûì íà ýòîì ìíîæåñòâå îòíîøåíè-
åì ýêâèâàëåíòíîñòè ñõåì. Ýêâèâàëåíòíîñòü ñõåì îïðåäåëÿåòñÿ äâóìÿ ïàðàìåòðàìè:
ýêâèâàëåíòíîñòüþ � â Y * è ïîäìíîæåñòâîì L ìíîæåñòâà L. Äëÿ çàäàííûõ ïàðà-
ìåòðîâ � è L äâå ñõåìû íàçûâàþòñÿ ýêâèâàëåíòíûìè, åñëè, êàêîé áû íè áûëà ôóíê-
öèÿ ðàçìåòêè � èç L, âñÿêèé ðàç, êàê íà íåé îñòàíàâëèâàåòñÿ îäíà èç ñõåì, îñòàíàâ-
ëèâàåòñÿ è äðóãàÿ, ðåçóëüòàòû èõ âûïîëíåíèÿ — �-ýêâèâàëåíòíûå öåïî÷êè.
Äëÿ îïðåäåëåííîãî ïàðàìåòðè÷åñêîãî ìíîæåñòâà ìîäåëåé îñíîâíîé ÿâëÿåòñÿ
ïðîáëåìà ýêâèâàëåíòíîñòè.
 [8] ðàññìîòðåíû ôîðìàëüíûå ïðîãðàììû íàä áàçèñîì Y è P, ãäå ñèìâîëû èç
Y òðàêòóþòñÿ êàê îïåðàòîðû, à ïåðåìåííûå èç P — êàê ëîãè÷åñêèå óñëîâèÿ. Ôîð-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5 27
p1
p2
y2
y1
1
1
0
0
Ðèñ. 1
ìàëüíîé ïðîãðàììå ñîïîñòàâëÿåòñÿ åå ñõåìà, ñîõðàíÿþùàÿ óïðàâëÿþùèé ãðàô
ïðîãðàììû è îñâîáîæäåííàÿ îò òðàêòîâêè ñèìâîëîâ èç Y è ïåðåìåííûõ èç P
êîíêðåòíûìè êîíñòðóêöèÿìè.
Ñ÷èòàåì, ÷òî àëãåáðàè÷åñêàÿ ìîäåëü ïðîãðàìì íàä Y è P àïïðîêñèìèðóåò
êëàññ ïðîãðàìì íàä Y è P (ñ òðàêòîâêîé ïîñëåäíèõ), åñëè èç ýêâèâàëåíòíîñòè ñõåì,
ïðèíàäëåæàùèõ ìîäåëè, âñåãäà ñëåäóåò ýêâèâàëåíòíîñòü ïðîãðàìì, äëÿ êîòîðûõ
ïîñòðîåíû ýòè ñõåìû. Ìîäåëü íàçûâàåòñÿ àïïðîêñèìèðóþùåé, åñëè ñóùåñòâóåò
êëàññ ïðîãðàìì, àïïðîêñèìèðóåìûé åþ.
 [7] îïðåäåëåíû òðåáîâàíèÿ, ïðåäúÿâëÿåìûå ê ïàðàìåòðàì àëãåáðàè÷åñêîé
ìîäåëè ïðîãðàìì è äîñòàòî÷íûå äëÿ òîãî, ÷òîáû ìîäåëü áûëà àïïðîêñèìèðóþùåé.
×àñòíûé ñëó÷àé ýòèõ òðåáîâàíèé ôèêñèðóåòñÿ ñëåäóþùåé òåîðåìîé.
Òåîðåìà 1. Ïóñòü � è L — ïàðàìåòðû àëãåáðàè÷åñêîé ìîäåëè ïðîãðàìì íàä Y è P.
Åñëè ýêâèâàëåíòíîñòü � ïîëóãðóïïîâàÿ, à ìíîæåñòâî L ñîñòîèò èç âñåõ �-ñîãëàñî-
âàííûõ ôóíêöèé ðàçìåòêè èç L, òî äàííàÿ ìîäåëü ÿâëÿåòñÿ àïïðîêñèìèðóþùåé.
Îïóñêàÿ äîêàçàòåëüñòâî ýòîé òåîðåìû, îïèøåì èñïîëüçóåìûå â íåé ïîíÿòèÿ.
Îòìåòèì, ÷òî ïðè ââåäåíèè îòíîøåíèÿ ýêâèâàëåíòíîñòè � â Y * èñõîäíîé ÿâ-
ëÿåòñÿ ñëåäóþùàÿ ñèòóàöèÿ: ìíîæåñòâî Y * ñ ââåäåííîé â íåì îïåðàöèåé êîíêàòå-
íàöèè îïåðàòîðíûõ öåïî÷åê ïðåäñòàâëÿåò ñîáîé ïîëóãðóïïó ñ îáðàçóþùèìè —
ñèìâîëàìè èç Y è ñ åäèíèöåé, ðîëü êîòîðîé èãðàåò ïóñòàÿ öåïî÷êà èç Y * .
Îòíîøåíèå � íàçûâàåòñÿ ïîëóãðóïïîâûì, åñëè äëÿ ëþáûõ öåïî÷åê
h h h h1 2 3 4, , , èç Y * âûïîëíÿåòñÿ èìïëèêàöèÿ
( ~ )&( ~ ) ~h h h h h h h h1 2 3 4 1 3 2 4
� � �
� ;
çäåñü çàïèñü ~
�
èñïîëüçóåòñÿ äëÿ îòíîøåíèÿ ýêâèâàëåíòíîñòè �.
Íàçâàíèå «ïîëóãðóïïîâàÿ ýêâèâàëåíòíîñòü» îòðàæàåò ñëåäóþùåå: èíäóöèðóå-
ìûå åþ êëàññû ýêâèâàëåíòíûõ öåïî÷åê ñàìè îáðàçóþò ïîëóãðóïïó.
Ôóíêöèÿ ðàçìåòêè � èç L íàçûâàåòñÿ �-ñîãëàñîâàííîé, åñëè äëÿ ëþáûõ îïåðà-
òîðíûõ öåïî÷åê h h1 2, èç Y * èìååò ìåñòî èìïëèêàöèÿ
h h h h1 2 1 2~
�
� �� � .
Ðàññìàòðèâàåì àëãåáðàè÷åñêèå ìîäåëè ïðîãðàìì, óäîâëåòâîðÿþùèå òðåáîâà-
íèÿì òåîðåìû 1; îíè íàçûâàþòñÿ ïîëóãðóïïîâûìè. Ýòèì âûïîëíÿåòñÿ îáÿçà-
òåëüñòâî: ðàññìàòðèâàòü òîëüêî àïïðîêñèìèðóþùèå ìîäåëè.
Ôîðìóëèðóÿ ñëåäóþùóþ òåîðåìó, èñïîëüçóåì ðåçóëüòàò, óñòàíîâëåííûé,
â ÷àñòíîñòè, â [9].
Òåîðåìà 2. Êàêîé áû íè áûëà àëãåáðàè÷åñêàÿ ìîäåëü ïðîãðàìì íàä Y è P, ïðî-
áëåìà ýêâèâàëåíòíîñòè â ìîäåëè ñâîäèìà ê ïðîáëåìå ýêâèâàëåíòíîñòè â ìíîæåñòâå
u-ñõåì, ïðèíàäëåæàùèõ ýòîé ìîäåëè.
Ïîñêîëüêó äàëåå ðàññìàòðèâàþòñÿ èìåííî u-ñõåìû, îïðåäåëèì èõ. Ââåäåì ïî-
íÿòèÿ è êîíñòðóêöèè, èñïîëüçóåìûå ïðè ýòîì.
Íàïîìíèì îïðåäåëåíèå ôðàãìåíòà ñõåìû; îíî äàíî, íàïðèìåð, â [8]. Ôðàãìåíòîì
ñõåìû íàçûâàåòñÿ ïîäãðàô ñõåìû, èíäóöèðîâàííûé íåêîòîðûì ìíîæåñòâîì âåðøèí
ñõåìû, íàçûâàåìûõ âíóòðåííèìè âåðøèíàìè ôðàãìåíòà, è óäîâëåòâîðÿþùèé òðåáîâà-
íèÿì: âìåñòå ñ êàæäîé âíóòðåííåé âåðøèíîé ïîäãðàôó ïðèíàäëåæàò âñå èíöèäåíòíûå
åé äóãè; êàê âíóòðåííèå âåðøèíû, òàê è èíöèäåíòíûå èì äóãè íàñëåäóþò ìåòêè, ïðè-
ïèñàííûå èì â ñõåìå. Äóãà, êîòîðàÿ èñõîäèò èç âåðøèíû ôðàãìåíòà, íå ÿâëÿþùåéñÿ
âíóòðåííåé, è âåäåò âî âíóòðåííþþ âåðøèíó ôðàãìåíòà, íàçûâàåòñÿ âõîäÿùåé â íåãî,
åå íà÷àëî — âíåøíèì âõîäîì âî ôðàãìåíò, êîíåö — âíóòðåííèì âõîäîì. Äóãà, êîòî-
ðàÿ âåäåò â âåðøèíó ôðàãìåíòà, íå ÿâëÿþùóþñÿ âíóòðåííåé, íî èñõîäèò èç âíóòðåí-
íåé âåðøèíû, íàçûâàåòñÿ èñõîäÿùåé èç ôðàãìåíòà, åå íà÷àëî — âíóòðåííèì âûõîäîì
èç ôðàãìåíòà, êîíåö — âíåøíèì âûõîäîì.
28 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5
Íà ðèñ. 2 ïðèâåäåí ôðàãìåíò
ñõåìû íàä Y è P, íàçûâàåìûé äå-
ðåâîì ðàñïîçíàâàòåëåé, ïðîèç-
ðàñòàþùèì èç âåðøèíû � ñõåìû.
Ïðåäïîëàãàåòñÿ, ÷òî � — ëèáî
âõîä ñõåìû, ëèáî ïðåîáðàçîâà-
òåëü, è � — åäèíñòâåííûé âíåø-
íèé âõîä ôðàãìåíòà. Ëîãè÷åñêèå
ïåðåìåííûå p pm1 ,... , ðàçëè÷íû
è â ñîâîêóïíîñòè äàþò ìíîæåñ-
òâî P. Äóãè, èñõîäÿùèå èç ðàñ-
ïîçíàâàòåëåé ñ ïåðåìåííîé pm ,
ÿâëÿþòñÿ èñõîäÿùèìè èç ôðàãìåíòà.
Ïóñòûì öèêëîì â ñõåìå íàçûâàåòñÿ ðàñïîçíàâàòåëü, èñõîäÿùèå èç êîòîðîãî
äóãè âåäóò â íåãî æå.
Ïî îïðåäåëåíèþ u-ñõåìîé íàçûâàåòñÿ òàêàÿ ñõåìà íàä Y è P, ñòðóêòóðà êîòî-
ðîé óäîâëåòâîðÿåò ñëåäóþùèì òðåáîâàíèÿì:
1) èç âõîäà ñõåìû è ëþáîãî ïðèíàäëåæàùåãî åé ïðåîáðàçîâàòåëÿ ïðîèçðàñòàåò
ñâîå ñîáñòâåííîå äåðåâî ðàñïîçíàâàòåëåé;
2) âñÿêèé ïðèíàäëåæàùèé ñõåìå ðàñïîçíàâàòåëü ëèáî ñîäåðæèòñÿ â îäíîì
èç óïîìÿíóòûõ äåðåâüåâ ðàñïîçíàâàòåëåé, ëèáî ÿâëÿåòñÿ ïóñòûì öèêëîì;
3) âñÿêèé ïðåîáðàçîâàòåëü, ïðèíàäëåæàùèé ñõåìå, ïðèíàäëåæèò êàêîìó-ëèáî
îðèåíòèðîâàííîìó ïóòè èç åå âõîäà â âûõîä.
Ëåãêî óâèäåòü, ÷òî â u-ñõåìå, êàêèì áû íè áûëî ïðèíàäëåæàùåå åé äåðåâî ðàñ-
ïîçíàâàòåëåé, ëþáàÿ èñõîäÿùàÿ èç äåðåâà ðàñïîçíàâàòåëåé äóãà âåäåò ëèáî â âûõîä
ñõåìû, ëèáî â ïðåîáðàçîâàòåëü, ëèáî â ïóñòîé öèêë.
Òåîðåìà 1 áàçèðóåòñÿ íà ëåììå 1, äîêàçàííîé â [9].
Ëåììà 1. Ñóùåñòâóåò àëãîðèòì, êîòîðûé ïî ëþáîé ñõåìå íàä Y è P ñòðîèò
u-ñõåìó, è ïîñëåäíÿÿ ýêâèâàëåíòíà èñõîäíîé â ëþáîé àëãåáðàè÷åñêîé ìîäåëè ïðî-
ãðàìì íàä Y è P.
Îïóñêàåì îïèñàíèå ýòîãî àëãîðèòìà, ïðèâîäÿ íà ðèñ. 3 u-ñõåìó, ïîñòðîåííóþ
ñ åãî ïîìîùüþ äëÿ ñõåìû ñ ðèñ. 1.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5 29
p1
p2 p2
0 1
0 1 0 1
. . . . . . . . . . . . . .
. . . . . . .pm
0 1
pm
0 1
õ
Ðèñ. 2
p1
p2 p2
0 1
0 1 0 1
p1
p2 p2
0 1
0 1 0 1
p1
p2 p2
0 1
0 1 0 1
y
1
y2
Ðèñ. 3
ÒÅÕÍÈÊÀ ÑËÅÄÎÂ È ÄÎÑÒÀÒÎ×ÍÛÅ ÓÑËÎÂÈß ÅÅ ÏÐÈÌÅÍÈÌÎÑÒÈ
ÄËß ÐÀÑÏÎÇÍÀÂÀÍÈß ÝÊÂÈÂÀËÅÍÒÍÎÑÒÈ ÑÕÅÌ
Ïóñòü ïîëóãðóïïîâàÿ ìîäåëü ïðîãðàìì íàä Y è P èìååò ïàðàìåòðû � è L ;
îáîçíà÷èì åå M.
Ïðåäïîëàãàåì, ÷òî � — ðàçðåøèìàÿ ýêâèâàëåíòíîñòü â Y *, ò.å. ñóùåñòâóåò
àëãîðèòì, êîòîðûé, ïîëó÷èâ íà ñâîé âõîä äâå öåïî÷êè èç Y *, ðàñïîçíàåò, ýêâèâà-
ëåíòíû îíè èëè íåò.
Îïèðàÿñü íà òåîðåìó 2, ðàññìîòðèì u-ñõåìû, ïðèíàäëåæàùèå âûáðàííîé ìî-
äåëè, îáîçíà÷èâ M u èõ ìíîæåñòâî.
Öåëü äàííîãî ðàçäåëà ñîñòîèò â òîì, ÷òîáû âûÿâèòü òðåáîâàíèÿ, ïðåäúÿâëÿå-
ìûå ê ñõåìàì èç M u è äîñòàòî÷íûå äëÿ îòíîøåíèÿ ýêâèâàëåíòíîñòè ñõåì.
Îòíîøåíèå ýêâèâàëåíòíîñòè ñõåì G1, G2 èç M çàïèøåì â âèäå G G1 2~ è ââå-
äåì ðÿä ïîíÿòèé.
Ïóñòü G — ñõåìà èç M u , � — âõîä ñõåìû èëè ïðåîáðàçîâàòåëü, x — íàáîð èç X ;
x-ïåðåõîäîì èç âåðøèíû � íàçîâåì ïóòü, íà÷èíàþùèéñÿ â � è çàâåðøàþùèéñÿ òà-
êîé âåòâüþ äåðåâà ðàñïîçíàâàòåëåé, ïðîèçðàñòàþùåãî èç �, ìåòêè äóã êîòîðîãî ñî-
ñòàâëÿþò íàáîð x.
 ñõåìå G áóäåì ðàññìàòðèâàòü ïóòè, ñîñòîÿùèå èç ïðèìûêàþùèõ îäèí
ê äðóãîìó x-ïåðåõîäîâ. Ìàðøðóòîì íàçîâåì ïóòü, íà÷èíàþùèéñÿ âî âõîäå ñõå-
ìû G. Åñëè ìàðøðóò çàâåðøàåòñÿ â âûõîäå ñõåìû G, òî íàçîâåì åãî ìàðøðóòîì ÷å-
ðåç ñõåìó G.
Âñÿêèé êîíå÷íûé ìàðøðóò w (îí çàâåðøàåòñÿ èëè â âûõîäå, èëè â ïóñòîì öèê-
ëå, èëè â ïðåîáðàçîâàòåëå) ïðåäñòàâèì â âèäå
� � �0 1
0 1
� � �
x x
k
xk
� ,
ãäå � j
xj
� , j k� �0, , , — çàïèñü x j -ïåðåõîäà èç âåðøèíû � j . ×èñëî k � 1 íàçîâåì
íîðìîé ìàðøðóòà w è îáîçíà÷èì åå | | | |w ; èñïîëüçóåì îáîçíà÷åíèå x x wk � ( ).
Ñëîâî y y yi i ik1 2
... , ãäå yi j
— ñèìâîë, ñîïîñòàâëåííûé ïðåîáðàçîâàòåëþ � j ,
j k� �1, , , íàçîâåì öåïî÷êîé, íåñîìîé ìàðøðóòîì w, è îáîçíà÷èì h w( ) .
Ââåäåì îòíîøåíèå N-ýêâèâàëåíòíîñòè ñõåì G1, G2 èç M u , ãäå N — íàòóðàëü-
íîå ÷èñëî, îáîçíà÷àÿ åãî êàê G G
N
1 2~ .
Ïîëàãàåì: åñëè ìàðøðóò â ñõåìå ïðîêëàäûâàåòñÿ íåêîòîðîé ôóíêöèåé ðàçìåò-
êè èç L, òî î ëþáîì åãî ïîäìàðøðóòå áóäåì ãîâîðèòü êàê î òîæå ïðîêëàäûâàåìîì
ýòîé ôóíêöèåé, íàçûâàÿ ïåðâûé ìàðøðóò ïîëíûì.
Ïî îïðåäåëåíèþ ñõåìû G1, G2 èç M u N-ýêâèâàëåíòíû, åñëè, êàêîé áû íè
áûëà ôóíêöèÿ ðàçìåòêè èç L, îíà ïðîêëàäûâàåò â G1, G2 ðàâíîâåëèêèå ïî íîðìå
ìàðøðóòû w w1 2, , íîðìû êîòîðûõ íå ïðåâûøàþò ÷èñëà N è êîòîðûå îêàí÷èâàþò-
ñÿ â îäíîòèïíûõ âåðøèíàõ, ïðè÷åì â ñëó÷àå, êîãäà èõ òèï — âûõîäû ñõåì, âûïîë-
íÿåòñÿ
h w h w( )~ ( )1 2
�
.
Ñïðàâåäëèâî ñëåäóþùåå óòâåðæäåíèå.
Óòâåðæäåíèå 1. Åñëè G G u1 2, �M , òî äëÿ ëþáîãî íàòóðàëüíîãî N
G G G G
N
1 2 1 2~ ~� .
Çàìåòèì, ÷òî ðàâíîâåëèêîñòü ìàðøðóòîâ w w1 2, , ôèãóðèðóþùèõ â îïðåäåëå-
íèè îòíîøåíèÿ G G
N
1 2~ , ñëåäóåò èç îòíîøåíèÿ G G1 2~ è òîãî ñâîéñòâà u-ñõåì, ÷òî
êàæäûé ïðåîáðàçîâàòåëü â u-ñõåìå ïðèíàäëåæèò ìàðøðóòó ÷åðåç íåå.
 äàëüíåéøåì áóäåì îïèðàòüñÿ íà ñëåäóþùåå óòâåðæäåíèå.
30 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5
Óòâåðæäåíèå 2. Êàêèì áû íè áûëî íàòóðàëüíîå N , äëÿ ñõåì G1, G2 èç M u îò-
íîøåíèå èõ N-ýêâèâàëåíòíîñòè àëãîðèòìè÷åñêè ðàñïîçíàâàåìî.
Äåéñòâèòåëüíî, äëÿ ïðîâåðêè äîñòàòî÷íî ïðîñìîòðåòü âûïîëíåíèå ñõåì íà
ïîäôóíêöèÿõ ôóíêöèé èç L, îïðåäåëåííûõ íà îïåðàòîðíûõ öåïî÷êàõ äëèíû N . Âñå
òàêèå ïîäôóíêöèè ìîãóò áûòü ïîñòðîåíû, è èõ ÷èñëî êîíå÷íî.
Ââåäåì ïîíÿòèÿ, íåïîñðåäñòâåííî èñïîëüçóåìûå â ëåììå 3, ÿâëÿþùåéñÿ
îñíîâíîé â ýòîì ðàçäåëå.
Ïóñòü G1, G2 — ñõåìû èç M u è ni — ÷èñëî ïðåîáðàçîâàòåëåé â ñõåìå Gi , íà-
çûâàåìîå åå ðàçìåðîì, i � 1 2, . Ðàññìîòðèì ìàðøðóòû w w1 2, â G1, G2 ñîîòâåòñòâåí-
íî, íîðìû êîòîðûõ íå ìåíüøå ÷èñëà n n1 2 1� , ïîëàãàÿ, ÷òî â ñëó÷àå, êîãäà íîðìà
ðàâíà ÷èñëó n n1 2 1� , ìàðøðóò îêàí÷èâàåòñÿ â ïðåîáðàçîâàòåëå.
 ìàðøðóòàõ w w1 2, èìåþòñÿ ïîâòîðÿþùèåñÿ ïàðû ðàâíîóäàëåííûõ îò èõ íà-
÷àëà ïðåîáðàçîâàòåëåé. Ïóñòü � �1 1, — ïåðâàÿ èç íèõ, � i — ïðåîáðàçîâàòåëü èç Gi
i � 1 2, . Ðàçîáüåì ìàðøðóòû w w1 2, íà îòðåçêè, ïîëàãàÿ
w w w wi i i i� , i � 1 2, , (1)
ãäå ìàðøðóòû w w1 2, îêàí÷èâàþòñÿ ïåðâîé âñòðå÷åé ñ ïðåîáðàçîâàòåëÿìè �1,
�2 , à ìàðøðóòû w w1 1 è w w2 2 — ñëåäóþùåé âñòðå÷åé ñ íèìè.
Îòðåçêè w w1 2, íàçîâåì èíòåðâàëàìè ïîâòîðà â w w1 2, , ìàðøðóòû w w1 2, —
ïîäâîäÿùèìè ê èíòåðâàëàì ïîâòîðà, à ìàðøðóòû w w1 1 è w w2 2 — ïîëó÷åííûìè
ñîêðàùåíèåì ìàðøðóòîâ w w1 2, íà èíòåðâàëû ïîâòîðà. Îòðåçêó wi ïðèïèøåì îïå-
ðàòîðíóþ öåïî÷êó, ïîñòðîåííóþ óäàëåíèåì èç öåïî÷êè h w wi i( ) åå íà÷àëà — öå-
ïî÷êè h wi( ) ; ïðèïèñàííóþ öåïî÷êó íàçûâàåì íåñîìîé îòðåçêîì wi , i � 1 2, .
 äîêàçàòåëüñòâå ëåììû 3 èñïîëüçóåòñÿ ïîíÿòèå ñî÷åòàåìîñòè ìàðøðóòîâ è
ïðèìåíÿåòñÿ ëåììà 2, ôîðìóëèðóþùàÿ êðèòåðèé ñî÷åòàåìîñòè.
Ïóñòü w w1 2, — ìàðøðóòû â ñõåìàõ èç M u . Íàçîâåì èõ ñî÷åòàåìûìè, åñëè ñó-
ùåñòâóåò òàêàÿ ôóíêöèÿ ðàçìåòêè èç L , êîòîðàÿ ïðîêëàäûâàåò â ñõåìàõ ïóòè, íà÷è-
íàþùèåñÿ ýòèìè ìàðøðóòàìè.
Êðèòåðèé ñî÷åòàåìîñòè ìàðøðóòîâ óñòàíîâèì â ñëó÷àå, êîãäà ìîäåëü M îáëà-
äàåò ñëåäóþùèì ñâîéñòâîì: äëÿ ëþáûõ h èç Y *
h e h e~
�
� ,
ãäå e — ïóñòàÿ öåïî÷êà èç Y * . Íàçîâåì M ìîäåëüþ áåç ðàçëîæèìîé åäèíèöû.
Äîêàæåì ñëåäóþùóþ ëåììó.
Ëåììà 2. Â ïîëóãðóïïîâîé ìîäåëè ïðîãðàìì áåç ðàçëîæèìîé åäèíèöû ìàð-
øðóòû â ñõåìàõ ñî÷åòàåìû òîãäà è òîëüêî òîãäà, êîãäà äëÿ ëþáûõ èõ ñîáñòâåííûõ
ïîäìàðøðóòîâ u u1 2, âûïîëíÿåòñÿ òðåáîâàíèå
h u h u x u x u( ) ~ ( ) ( ) ( )1 2 1 2
�
� � .
Äîêàçàòåëüñòâî. Íåîáõîäèìîñòü òðåáîâàíèÿ ëåììû âûòåêàåò èç îïðåäåëåíèÿ
ôóíêöèé, ïðèíàäëåæàùèõ ìíîæåñòâó L .
Äîñòàòî÷íîñòü òðåáîâàíèÿ óñòàíàâëèâàåòñÿ ïîñòðîåíèåì ôóíêöèè èç L , ïðî-
êëàäûâàþùåé ïóòè â ñõåìàõ, êîòîðûå íà÷èíàþòñÿ ìàðøðóòàìè w w1 2, , óäîâëåòâî-
ðÿþùèìè òðåáîâàíèþ ëåììû.
Èñêîìàÿ ôóíêöèÿ � îïðåäåëÿåòñÿ ñëåäóþùèì îáðàçîì: äëÿ ëþáîé öåïî÷êè h
èç Y * èìååì
�
�
h
x u h h u u w
x�
( ), ~ ( ), — ð ;1 1 1 1åñëè ãäå ïîäìàðø óò ìàðøðóòà
( ), ~ ( ), — ð ;u h h u u w
x
2 2 2 2
0
åñëè ãäå ïîäìàðø óò ìàðøðóòà
â ïð
�
îòèâíîì ñëó àå ãäå íåêîòîðûé íàáîð èç, — .x X0
�
�
�
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5 31
÷
Êîððåêòíîñòü îïðåäåëåíèÿ ôóíêöèè � ñëåäóåò, âî-ïåðâûõ, èç íåðàçëîæèìîñòè
åäèíèöû, ñîãëàñíî ÷åìó âîçìîæíû òîëüêî òðè ñèòóàöèè, óêàçàííûå â îïðåäåëå-
íèè �, âî-âòîðûõ, èç ðàâåíñòâà x u x u( ) ( ),1 2� åñëè îäíîâðåìåííî èìåþò ìåñòî ïåð-
âûå äâå ñèòóàöèè; ýòî ðàâåíñòâî îáåñïå÷èâàåòñÿ ïðåäïîëîæåíèåì î òîì, ÷òî w w1 2,
óäîâëåòâîðÿþò òðåáîâàíèþ ëåììû.
Î÷åâèäíî, ÷òî � �L .
Ëåììà 2 äîêàçàíà.
Îòìåòèì, ÷òî ñî÷åòàåìîñòü êîíå÷íûõ ìàðøðóòîâ àëãîðèòìè÷åñêè ðàñïîçíàâà-
åìà â ñèëó àëãîðèòìè÷åñêîé ðàñïîçíàâàåìîñòè �-ýêâèâàëåíòíîñòè öåïî÷åê èç Y * .
Ïðåîáðàçîâàòåëè, ïðèíàäëåæàùèå ñõåìàì èç M u , íàçîâåì ñîïðÿæåííûìè,
åñëè â íèõ îêàí÷èâàþòñÿ ìàðøðóòû, íåñóùèå ýêâèâàëåíòíûå öåïî÷êè; ýòè ìàðøðó-
òû íàçûâàåì ïîäòâåðæäàþùèìè ñîïðÿæåííîñòü ïðåîáðàçîâàòåëåé.
Ñ÷èòàåì, ÷òî ïîëóãðóïïîâàÿ ìîäåëü ïðîãðàìì îáëàäàåò ëåâûì ñîêðàùåíèåì,
åñëè ýêâèâàëåíòíîñòü � â òàêîé ìîäåëè óäîâëåòâîðÿåò òðåáîâàíèþ: êàêèìè áû íè
áûëè öåïî÷êè h1, h2 , h3 , h4 èç Y * , èìååì
( ~ ) & ( ~ ) ~h h h h h h h h1 2 3 4 1 3 2 4
� � �
� .
Ëåììà 3. Ïóñòü M — ìîäåëü ñ íåðàçëîæèìîé åäèíèöåé è ëåâûì ñîêðàùåíè-
åì. Äîñòàòî÷íûìè óñëîâèÿìè îòíîøåíèÿ G G1 2~ , ãäå G1, G2 — ñõåìû èç M u ðàç-
ìåðîâ n n1 2, ñîîòâåòñòâåííî, ÿâëÿþòñÿ òðåáîâàíèÿ:
1) G G
n n
1
1
2
1 2
~
�
;
2) êàêîé áû íè áûëà ôóíêöèÿ èç L , ïðîêëàäûâàþùàÿ â G1, G2 ìàðøðóòû íîð-
ìû n n1 2 1� , ýòè ìàðøðóòû îáëàäàþò ñâîéñòâîì: èõ èíòåðâàëû ïîâòîðà íà÷èíàþò-
ñÿ â ñîïðÿæåííûõ ïðåîáðàçîâàòåëÿõ è íåñóò ýêâèâàëåíòíûå öåïî÷êè.
Äîêàçàòåëüñòâî. Ïóñòü G1, G2 — ñõåìû èç M u , äëÿ êîòîðûõ âûïîëíåíû òðå-
áîâàíèÿ 1) è 2). Ðàññìîòðèì ïðîèçâîëüíóþ ôóíêöèþ ðàçìåòêè � èç L è äîêàæåì
óòâåðæäåíèå: åñëè îäíà èç ñõåì G1, G2 îñòàíàâëèâàåòñÿ íà ôóíêöèè � , òî äðóãàÿ
îñòàíàâëèâàåòñÿ òîæå, è ðåçóëüòàòû èõ âûïîëíåíèÿ íà � — ýêâèâàëåíòíûå öå-
ïî÷êè.
Ïóñòü w w1 2, — ïîëíûå ìàðøðóòû, ïðîëàãàåìûå ôóíêöèåé � â ñõåìàõ G1, G2
ñîîòâåòñòâåííî. Ïðåäïîëîæèì, ÷òî íà � îñòàíàâëèâàåòñÿ ñõåìà G1, ò.å. w1 —
ìàðøðóò ÷åðåç íåå.
Åñëè | | | |w n n1 1 2 1� � , òî ñïðàâåäëèâîñòü óòâåðæäåíèÿ ñëåäóåò èç îòíîøå-
íèÿ 1).
Èç ýòîãî îòíîøåíèÿ òàêæå âûòåêàåò, ÷òî íåðàâåíñòâî | | | |w n n1 1 2 1� � âëå÷åò çà
ñîáîé íåðàâåíñòâî | | | |w n n2 1 2 1� � , òàê êàê ïîäìàðøðóòû ìàðøðóòîâ w w1 2, , èìå-
þùèå íîðìó n n1 2 1� , äîëæíû îêàí÷èâàòüñÿ â ïðåîáðàçîâàòåëÿõ.
Âîñïîëüçóåìñÿ â ýòîì ñëó÷àå ñâîéñòâîì 2), ïðåäñòàâèâ ìàðøðóòû w w1 2,
â ðàçáèâêå (1). Òîãäà ñîãëàñíî ñâîéñòâó 2) èìååì
h w h w( ) ~ ( ) 1 2
�
, (2)
h w h w( ) ~ ( ) 1 2
�
. (3)
Ñîêðàòèì w w1 2, íà èíòåðâàëû ïîâòîðà w w1 2, . Ïî ëåììå 2 ñîêðàùåííûå ìàð-
øðóòû w w1 1, w w2 2 ñî÷åòàåìû, ò.å. ñóùåñòâóåò ôóíêöèÿ â L , ïðîêëàäûâàþùàÿ ýòè
ìàðøðóòû; îáîçíà÷èì åå � .
Åñëè | | | | � �w w n n1 1 1 2 1, òî èç îòíîøåíèÿ 1) ñëåäóåò, ÷òî w w2 2 — ìàðøðóò ÷å-
ðåç G2 . Ñëåäîâàòåëüíî, w2 — òîæå ìàðøðóò ÷åðåç G2 .
Ïîêàæåì, ÷òî
h w h w( ) ~ ( )1 2
�
. (4)
32 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5
Ïîñêîëüêó
h w w h w w( ) ~ ( ) 1 1 2 2
�
(5)
è èìååò ìåñòî (2), ïðèìåíèâ ïðàâèëî ëåâîãî ñîêðàùåíèÿ, ïîëó÷èì
h w h w( ) ~ ( ) 1 2
�
.
Òîãäà èç (2), (3), (5) âûòåêàåò (4).
Òàêèì îáðàçîì, â ñëó÷àå, êîãäà | | | | � �w w n n1 1 1 2 1, óòâåðæäåíèå ñïðàâåäëèâî.
Åñëè æå | | | | � �w w n n1 1 1 2 1, òî â ïðîâåäåííûõ ðàíåå ðàññóæäåíèÿõ ðîëü ôóíê-
öèè � ïåðåäàåòñÿ ôóíêöèè � .
Äåéñòâóÿ îïèñàííûì îáðàçîì, ÷åðåç êîíå÷íîå ÷èñëî øàãîâ óáåäèìñÿ â ñïðà-
âåäëèâîñòè óòâåðæäåíèÿ.
Ëåììà 3 äîêàçàíà.
Òåõíèêà, ïðèìåíåííàÿ ïðè äîêàçàòåëüñòâå ëåììû 3, íàçûâàåòñÿ òåõíèêîé
ñëåäîâ.
Î÷åâèäíûì ÿâëÿåòñÿ ñëåäóþùåå óòâåðæäåíèå.
Óòâåðæäåíèå 3. Ïðîâåðêà óñëîâèé 1) è 2) èç ëåììû 3 ðåàëèçóåìà àëãîðèò-
ìàìè.
Ïîñòàâèì ñëåäóþùóþ áàçîâóþ çàäà÷ó: èç ìíîæåñòâà ïîëóãðóïïîâûõ ìîäåëåé
M ñ íåðàçëîæèìîé åäèíèöåé è ëåâûì ñîêðàùåíèåì âûäåëèòü ìîäåëè, äëÿ êîòîðûõ
ïðîáëåìà ýêâèâàëåíòíîñòè â M u ñâîäèòñÿ ê ïðîáëåìå ýêâèâàëåíòíîñòè â òàêîì
ïîäìíîæåñòâå ñõåì èç M u , â êîòîðîì óñëîâèÿ 1) è 2) ÿâëÿþòñÿ êðèòåðèåì îòíîøå-
íèÿ ýêâèâàëåíòíîñòè ñõåì.
Çàäà÷à íàçâàíà áàçîâîé ïîòîìó, ÷òî åå ðåøåíèåì îïðåäåëÿþòñÿ ìîäåëè, â êî-
òîðûõ òåõíèêîé ñëåäîâ óñòàíàâëèâàåòñÿ ðàçðåøèìîñòü ïðîáëåìû ýêâèâàëåíòíîñòè.
ÐÀÇÐÅØÈÌÎÑÒÜ ÒÅÕÍÈÊÎÉ ÑËÅÄÎÂ ÏÐÎÁËÅÌÛ ÝÊÂÈÂÀËÅÍÒÍÎÑÒÈ
 ÓÐÀÂÍÎÂÅØÅÍÍÎÉ ÏÎËÓÃÐÓÏÏÎÂÎÉ ÌÎÄÅËÈ ÏÐÎÃÐÀÌÌ Ñ ËÅÂÛÌ
ÑÎÊÐÀÙÅÍÈÅÌ
Ðåøèì áàçîâóþ çàäà÷ó.
Ïî îïðåäåëåíèþ ïîëóãðóïïîâàÿ ìîäåëü ïðîãðàìì ñ ïàðàìåòðàìè � è L íàçûâà-
åòñÿ óðàâíîâåøåííîé, åñëè â íåé èç �-ýêâèâàëåíòíîñòè öåïî÷åê ñëåäóåò ðàâåíñòâî
èõ äëèí.
Î÷åâèäíûì ÿâëÿåòñÿ ñëåäóþùåå óòâåðæäåíèå.
Óòâåðæäåíèå 4. Óðàâíîâåøåííàÿ ïîëóãðóïïîâàÿ ìîäåëü ïðîãðàìì èìååò íå-
ðàçëîæèìóþ åäèíèöó.
Òàêèì îáðàçîì, äëÿ ðàññìàòðèâàåìîé ìîäåëè ñïðàâåäëèâà ëåììà 3.
Ïîëàãàåì äàëåå, ÷òî M — óðàâíîâåøåííàÿ ïîëóãðóïïîâàÿ ìîäåëü ñ ëåâûì ñî-
êðàùåíèåì, è ïðîâåäåì àíàëèç ñòðóêòóðû ïðèíàäëåæàùèõ åé ýêâèâàëåíòíûõ ñõåì
èç M u .
Äëÿ ñõåìû G èç M u ââåäåì ïîíÿòèå êóñòà ñ êîðíåì â ïðåîáðàçîâàòåëå �, ïðè-
íàäëåæàùåì ñõåìå G. Ýòî ïî îïðåäåëåíèþ — ôðàãìåíò ñõåìû G, óäîâëåòâîðÿþ-
ùèé ñëåäóþùèì òðåáîâàíèÿì:
• � — âíóòðåííèé âõîä ôðàãìåíòà;
• âìåñòå ñ êàæäûì ïðåîáðàçîâàòåëåì, ÿâëÿþùèìñÿ âíóòðåííåé âåðøèíîé
ôðàãìåíòà, âíóòðåííèìè ÿâëÿþòñÿ è âñå ðàñïîçíàâàòåëè äåðåâà, ïðîèçðàñòàþùåãî
èç ýòîãî ïðåîáðàçîâàòåëÿ;
• âñå îðèåíòèðîâàííûå ïóòè èç âåðøèíû � ê âíóòðåííèì âûõîäàì ôðàãìåíòà
ïðîñòûå è ðàâíîâåëèêèå ïî äëèíå; ïðèíàäëåæàùèå èì ïðåîáðàçîâàòåëè ðàñïðåäå-
ëÿþòñÿ íà óðîâíè ïî ïðèíöèïó ðàâíîóäàëåííîñòè îò �;
• äëÿ ëþáîãî óðîâíÿ, êðîìå ïîñëåäíåãî, âûïîëíÿåòñÿ ñâîéñòâî: êàêèì áû íè
áûë íàáîð x èç X , x-ïðååìíèê ëþáîãî ïðåîáðàçîâàòåëÿ, ïðèíàäëåæàùåãî ýòîìó
óðîâíþ, íàõîäèòñÿ íà ñëåäóþùåì ïî óäàëåííîñòè îò � óðîâíå;
• âñå îðèåíòèðîâàííûå ïóòè èç �, çàâåðøàþùèåñÿ âûõîäÿùèìè äóãàìè ôðàã-
ìåíòà, íåñóò ýêâèâàëåíòíûå ìåæäó ñîáîé öåïî÷êè.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5 33
Êëàññ �-ýêâèâàëåíòíîñòè, êîòîðîìó ïðèíàäëåæàò óêàçàííûå öåïî÷êè, íàçûâà-
åòñÿ ìàðêåðîì êóñòà ñ êîðíåì â �.
Îñíîâíîé â äàííîì ðàçäåëå ÿâëÿåòñÿ ñëåäóþùàÿ ëåììà.
Ëåììà 4. Ïóñòü G1, G2 — ýêâèâàëåíòíûå u-ñõåìû, ïðèíàäëåæàùèå óðàâíîâå-
øåííîé ïîëóãðóïïîâîé ìîäåëè ñ ëåâûì ñîêðàùåíèåì, � �� , 2 — ñîïðÿæåííûå ïðå-
îáðàçîâàòåëè ñõåì G1, G2 ñîîòâåòñòâåííî, ïîìå÷åííûå ðàçëè÷íûìè îïåðàòîðíûìè
ñèìâîëàìè. Òîãäà � �� , 2 ÿâëÿþòñÿ êîðíÿìè êóñòîâ ñ îáùèì äëÿ íèõ ìàðêåðîì.
Äîêàçàòåëüñòâó ëåììû 4 ïðåäïîøëåì èñïîëüçóåìûå â íåì ïîíÿòèÿ.
Ïóñòü � �� , 2 — ñîïðÿæåííûå ïðåîáðàçîâàòåëè ñõåì G1, G2 è w w1 2, — ìàð-
øðóòû â G1, G2 ñîîòâåòñòâåííî, ïîäòâåðæäàþùèå ñîïðÿæåííîñòü. Ðàññìîòðèì
â ñõåìàõ ìàðøðóòû w w1 1 è w w2 2 . Åñëè îíè ñî÷åòàåìû, òî è ïóòè w w1 2, áóäåì íà-
çûâàòü ñî÷åòàåìûìè. Íîðìîé ïóòè wi , i � 1 2, , íàçîâåì ÷èñëî | | | | | | | |w w wi i i � ; öå-
ïî÷êîé, íåñîìîé ïóòåì wi , — öåïî÷êó, ïîëó÷åííóþ óäàëåíèåì èç h w wi i( ) åå íà÷à-
ëà h wi( ) ; îáîçíà÷èì åå h wi( ) ; â ñëó÷àå, êîãäà wi îêàí÷èâàåòñÿ â ïðåîáðàçîâàòåëå,
ïîëíîé öåïî÷êîé, íåñîìîé ïóòåì wi , íàçîâåì h w yi( ) , ãäå y — ñèìâîë, ïðèïèñàí-
íûé ýòîìó ïðåîáðàçîâàòåëþ.
Äîêàçàòåëüñòâî. Ïîëàãàåì âûïîëíåííîé ïîñûëêó ëåììû. Ïóñòü u u1 2, — ìàð-
øðóòû, ïîäòâåðæäàþùèå ñîïðÿæåííîñòü ïðåîáðàçîâàòåëåé � �� , 2 .  ñèëó óðàâíî-
âåøåííîñòè ïîëóãðóïïû | | | | | | | |u u1 2� .
Îáîçíà÷èì W 1 ìíîæåñòâî îðèåíòèðîâàííûõ ïóòåé èç �� â âûõîä ñõåìû G1,
èìåþùèõ ìèíèìàëüíóþ íîðìó. Íåïóñòîòà ìíîæåñòâà W 1 ñëåäóåò èç òîãî, ÷òî
G1 — u-ñõåìà.
Ðàññìîòðèì ñõåìó G2 . Èç îòíîøåíèÿ G G1 2~ è ñîïðÿæåííîñòè � �� , 2 ñëåäóåò,
÷òî äëÿ âñÿêîãî ìàðøðóòà u w1 1, ãäå w W1
1� , èìåþòñÿ ìàðøðóòû, ïðîäîëæàþùèå
ìàðøðóò u2 è íåñóùèå öåïî÷êè, ýêâèâàëåíòíûå öåïî÷êå h u w( )1 1 . Îáîçíà÷èì W 2
ìíîæåñòâî ïóòåé, ïðîäîëæàþùèõ â ýòèõ ìàðøðóòàõ ìàðøðóò u2 .
Èç óðàâíîâåøåííîñòè ðàññìàòðèâàåìîé ìîäåëè è ðàâåíñòâà | | | | | | | |u u1 2� ñëå-
äóåò, ÷òî íîðìà ëþáîãî ïóòè èç W 2 ñîâïàäàåò ñ íîðìîé ïóòåé èç W 1. Îòñþäà âûòå-
êàåò óòâåðæäåíèå: âñÿêèé ïóòü, ïðèíàäëåæàùèé îäíîìó èç ìíîæåñòâ W W1 2, , ñî-
÷åòàåì ñ êàêèì-ëèáî ïóòåì, ïðèíàäëåæàùèì äðóãîìó ìíîæåñòâó.
Ïîñêîëüêó h u h u( ) ~ ( )1 2
�
è èìååò ìåñòî ïðàâèëî ëåâîãî ñîêðàùåíèÿ, âñå ïóòè
èç W W1 2� íåñóò ýêâèâàëåíòíûå öåïî÷êè.
Îáîçíà÷èì k íîðìó ïóòåé èç W W1 2, .
Ïóñòü W j
i — ìíîæåñòâî ïóòåé íîðìû j, j k� �0, , , ÿâëÿþùèõñÿ íà÷àëüíûìè
îòðåçêàìè ïóòåé èç W i , è V j
i — ìíîæåñòâî âåðøèí, â êîòîðûõ îêàí÷èâàþòñÿ ïóòè
èç W j
i , i � 1 2, . Òàê êàê âñå ïóòè èç W W1 2� íåñóò ýêâèâàëåíòíûå öåïî÷êè, à ðàñ-
ñìàòðèâàåìàÿ ìîäåëü óðàâíîâåøåííàÿ, ñóùåñòâóåò íàèìåíüøåå èç ÷èñåë j, ãäå
j k� , äëÿ êîòîðîãî âñå ïóòè èç W W1 2� íåñóò ýêâèâàëåíòíûå ïîëíûå öåïî÷êè.
Îáîçíà÷èì ýòî ÷èñëî k. Èç òîãî, ÷òî ïðåîáðàçîâàòåëè � �� , 2 ïîìå÷åíû ðàçëè÷íûìè
îïåðàòîðíûìè ñèìâîëàìè, ñëåäóåò íåðàâåíñòâî k � 1.
Äîêàæåì, ÷òî äëÿ ëþáîãî j, j k� � �0 1 1, , , , âûïîëíÿþòñÿ ñâîéñòâà:
1) êàêîé áû íè áûëà âåðøèíà � èçV j
i è êàêèì áû íè áûë íàáîð x èç X , x-ïðååì-
íèêîì âåðøèíû � ÿâëÿåòñÿ âåðøèíà èç V
j
i
�1
, i � 1 2, ;
2) êàêèìè áû íè áûëè ïóòè w w1 2, , ãäå w Wi
j
i�
�1
, i � 1 2, , îíè ñîåäèíåíû
öåïüþ, ò.å. ñóùåñòâóåò ïîñëåäîâàòåëüíîñòü
w w w ll1 2 2, , , ,� � ,
34 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5
ñîñòîÿùàÿ èç ïóòåé ìíîæåñòâà W W
j j� �
�
1
1
1
2 , â êîòîðîé w w1
1� , w wl � 2 , è âñÿ-
êèå äâà ñîñåäíèõ ýëåìåíòà ïîñëåäîâàòåëüíîñòè — ñî÷åòàåìûå ïóòè.
Ñâîéñòâà 1) è 2) óñòàíîâèì èíäóêöèåé ïî j.
Ïóòü, ïîëó÷åííûé ïðîäîëæåíèåì ïóòè w íà x-ïåðåõîä èç ïîñëåäíåé åãî âåðøè-
íû, çàïèøåì êàê [ , ]w x , x X� .
Áàçèñ èíäóêöèè — j � 0.  ýòîì ñëó÷àå V i
0
ñîñòîèò èç îäíîé âåðøèíû,
à èìåííî � i , i � 1 2, . Òàê êàê � �� , 2 ïîìå÷åíû ðàçëè÷íûìè ñèìâîëàìè, âñÿêèé ïóòü
èç ìíîæåñòâà
{[ , ] | }w x x X
0
1 � (6)
ñî÷åòàåì ñ ëþáûì ïóòåì èç ìíîæåñòâà
{[ , ] | }w x x X
0
2 � , (7)
ãäå wi
0
ñîñòîèò òîëüêî èç âåðøèíû � i , i � 1 2, . Ýòî ñëåäóåò èç êðèòåðèÿ ñî÷åòàå-
ìîñòè ìàðøðóòîâ, óñòàíàâëèâàåìîãî ëåììîé 2 è äåéñòâóþùåãî äëÿ ðàññìàòðèâà-
åìîé ìîäåëè.
Î÷åâèäíî, ÷òî õîòÿ áû îäèí èç ïóòåé ìíîæåñòâà (6) ïðèíàäëåæèò ìíîæåñòâó
W
1
1 è, ñëåäîâàòåëüíî, ÿâëÿåòñÿ íà÷àëîì íåêîòîðîãî ïóòè èç W 1. Íî òîãäà âñå ïóòè
ìíîæåñòâà (7) ñî÷åòàåìû ñ ýòèì ïóòåì, íàõîäÿñü â ìíîæåñòâå W
1
2 . Â ìíîæåñòâî
W
1
2 ïîïàëè íà÷àëüíûå îòðåçêè ïóòåé èç W 2 , äëÿ êàæäîãî èç êîòîðûõ ñóùåñòâóåò
ñî÷åòàåìûé ïóòü èç W 1. Òàêèì îáðàçîì, äëÿ j = 0 ñâîéñòâà 1) è 2) èìåþò ìåñòî.
Øàã èíäóêöèè. Ïðåäïîëîæèì, ÷òî ñâîéñòâà 1) è 2) èìåþò ìåñòî äëÿ
j s� � �0 1 1, , , , ãäå s k� , è ðàññìîòðèì ñëó÷àé j s� .
Èç âûáîðà ÷èñëà k ñëåäóåò, ÷òî â ìíîæåñòâå W Ws s
1 2� èìåþòñÿ äâà ñî÷åòàå-
ìûõ ïóòè, íåñóùèõ íåýêâèâàëåíòíûå ïîëíûå öåïî÷êè; ïóñòü ýòî ïóòè w w1 2, . Ïðè-
ìåíèâ ê íèì ëåììó 2, ïîëó÷èì: êàêèìè áû íè áûëè x x1 2, èç X , ïóòè
[ , ], [ , ]w x w x1 1 2 2 ñî÷åòàåìû. Ñðåäè íèõ èìåþòñÿ ïóòè èç ìíîæåñòâà W W
s s� �
�
1
1
1
2 ,
ñëåäîâàòåëüíî, äëÿ ëþáîãî x èç X x-ïðååìíèêè âåðøèí, îêàí÷èâàþùèõ ïóòè
w w1 2, , ïðèíàäëåæàò ìíîæåñòâó V V
s s� �
�
1
1
1
2 .
Ïðåäïîëîæèì, ÷òî w Ws1
2� .
Âîçüìåì ïðîèçâîëüíóþ âåðøèíó � èç Vs
1, è ïóñòü w — ïóòü èç Ws
1, îêàí÷èâà-
þùèéñÿ â � . Ïîêàæåì, ÷òî x-ïðååìíèê âåðøèíû � , ãäå x — ïðîèçâîëüíûé ýëåìåíò
èç X , ïðèíàäëåæèò ìíîæåñòâó V
s�1
1 .
C ýòîé öåëüþ äëÿ ïóòåé [ , ]w x è [ , ]w x1 ïîñòðîèì ñîåäèíÿþùóþ öåïü. Âîñïîëü-
çóåìñÿ èíäóêòèâíûì ïðåäïîëîæåíèåì î ñóùåñòâîâàíèè öåïè, ñîåäèíÿþùåé w è
w1, è çàìåíèì êàæäûé åå ýëåìåíò w ïóòåì [ , ]w x , íå íàðóøàÿ èìåþùåãîñÿ ïîðÿäêà
èõ ñëåäîâàíèÿ â öåïè. Î÷åâèäíî, ÷òî ïîñòðîåííàÿ òàêèì îáðàçîì ïîñëåäîâàòåëü-
íîñòü ïóòåé — öåïü. È ïîñêîëüêó [ , ]w x1 ïðèíàäëåæèò W
s�1
2 , ïóòü [ , ]w x äîëæåí
ïðèíàäëåæàòü ìíîæåñòâó W
s�1
1 . Ýòî îçíà÷àåò, ÷òî x-ïðååìíèê âåðøèíû � íàõîäèò-
ñÿ â V
s�1
1 .
Îòñþäà, ïî ëåììå 2, ñëåäóåò, ÷òî è ëþáîé x-ïðååìíèê âåðøèí èç ìíîæåñòâà
Vs
2 ïðèíàäëåæèò ìíîæåñòâó V
s�1
2 . Òàêèì îáðàçîì, ñâîéñòâî 1) äåéñòâèòåëüíî èìååò
ìåñòî.
Ïîêàæåì òåïåðü, ÷òî äëÿ ëþáûõ ïóòåé [ , ],[ , ]w x w x 1 2 , ãäå w Ws � 1, w Ws � 2 ,
x x X1 2, � , ñóùåñòâóåò ñîåäèíÿþùàÿ èõ öåïü.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5 35
Ðàññìîòðèì ïóòè w w1 2, , íåñóùèå íåýêâèâàëåíòíûå ïîëíûå öåïî÷êè; w Ws1
2� ,
w Ws2
1� . Âîçüìåì äâå öåïè: ñîåäèíÿþùóþ w ñ w1 è ñîåäèíÿþùóþ w2 ñ w ; èõ ñó-
ùåñòâîâàíèå ñëåäóåò èç èíäóêòèâíîãî ïðåäïîëîæåíèÿ. Êàæäûé ýëåìåíò w ïåðâîé
öåïè çàìåíèì ïóòåì [ , ]w x1 , à êàæäûé ýëåìåíò w âòîðîé öåïè — ïóòåì [ , ]w x2 . Ëåã-
êî óâèäåòü, ÷òî â ðåçóëüòàòå ïîëó÷èì äâå öåïè: îäíà ñîåäèíÿåò [ , ]w x 1 ñ [ , ]w x1 1 ,
äðóãàÿ — [ , ]w x2 2 ñ [ , ] w x2 . Ïðèïèñûâàÿ ê ïåðâîé öåïè âòîðóþ è ïîëüçóÿñü òåì,
÷òî [ , ]w x1 1 è [ , ]w x2 2 ñî÷åòàåìû, ïîëó÷èì èñêîìóþ öåïü.
Èòàê, ñâîéñòâî 2) óñòàíîâëåíî, ò.å. èíäóêòèâíûé øàã ïîëíîñòüþ èñ÷åðïàí.
Ëåììà 4 äîêàçàíà.
Ñõåìó èç M u íàçîâåì ÷èñòîé, åñëè âî âñÿêîì ïðèíàäëåæàùåì åé êóñòå
ñ êîðíåì â ïðåîáðàçîâàòåëå ïîñëåäíèé ÿâëÿåòñÿ åäèíñòâåííûì âíóòðåííèì âõîäîì
êóñòà.
Ñïðàâåäëèâà ñëåäóþùàÿ ëåììà.
Ëåììà 5. Ïðîáëåìà ýêâèâàëåíòíîñòè â ìíîæåñòâå u-ñõåì, ïðèíàäëåæàùèõ
óðàâíîâåøåííîé ïîëóãðóïïîâîé ìîäåëè ïðîãðàìì ñ ëåâûì ñîêðàùåíèåì, ñâîäèòñÿ
ê ïðîáëåìå ýêâèâàëåíòíîñòè â ìíîæåñòâå ÷èñòûõ u-ñõåì èç ýòîé ìîäåëè.
Äîêàçàòåëüñòâî. Ïîêàæåì, ÷òî ñóùåñòâóåò àëãîðèòì, êîòîðûé äëÿ ïðîèçâîëü-
íîé ñõåìû èç M u ñòðîèò ýêâèâàëåíòíóþ åé ÷èñòóþ ñõåìó.
Ïóñòü G — ñõåìà èç M u . Ïðåäïîëàãàåìûé àëãîðèòì ðàáîòàåò ñëåäóþùèì îá-
ðàçîì. Ñíà÷àëà îí âûÿâëÿåò âñå ïðèíàäëåæàùèå ñõåìå ìàêñèìàëüíûå ïî ðàçìåðó
êóñòû ñ êîðíåì â ïðåîáðàçîâàòåëå.
Ïóñòü F — òàêîé êóñò ñ êîðíåì â �. Ñ íèì ïðîâîäèòñÿ ðàáîòà, åñëè â F èìåþò-
ñÿ âíóòðåííèå âõîäû, îòëè÷íûå îò �. Êàæäûé èç íèõ îïðåäåëÿåò ñâîé ïîäôðàãìåíò
ôðàãìåíòà F. Ñ÷èòàåì, ÷òî ðàíã ïîäôðàãìåíòà, öåëèêîì ïðèíàäëåæàùåãî äðóãîìó
ïîäôðàãìåíòó, ìåíüøå ðàíãà ïîñëåäíåãî. Àëãîðèòì îñóùåñòâëÿåò ïîñðåäñòâîì êî-
ïèðîâàíèÿ îòêëåéêó îò F åãî ïîäôðàãìåíòîâ, ðàññìàòðèâàÿ èõ â ïîðÿäêå âîçðàñòà-
íèÿ ðàíãîâ. Êàæäàÿ îïåðàöèÿ îòêëåéêè — ýêâèâàëåíòíîå ïðåîáðàçîâàíèå ñõåìû,
÷èñëî îïåðàöèé êîíå÷íî.  ðåçóëüòàòå ðàáîòû ñ êóñòîì F îí òðàíñôîðìèðóåòñÿ
â êóñò ñ åäèíñòâåííûì âíóòðåííèì âõîäîì. Êîíå÷íîñòü ÷èñëà îáðàáàòûâàåìûõ
êóñòîâ è êîíå÷íîñòü ïðèíàäëåæàùèõ êóñòàì ïîäôðàãìåíòîâ ãàðàíòèðóþò, ÷òî àë-
ãîðèòì ïðåîáðàçóåò ñõåìó G â ÷èñòóþ è ýêâèâàëåíòíóþ åé ñõåìó çà êîíå÷íîå ÷èñëî
îïåðàöèé îòêëåéêè.
Ëåììà 5 äîêàçàíà.
Îáîçíà÷èì M ìíîæåñòâî ñõåì èç M u , â êîòîðîå ïî ëåììå 5 ñâîäèòñÿ ïðîáëå-
ìà ýêâèâàëåíòíîñòè.
Ëåììà 6. Â ìíîæåñòâå M óñëîâèÿ 1) è 2) èç ëåììû 3 ÿâëÿþòñÿ êðèòåðèåì îò-
íîøåíèÿ ýêâèâàëåíòíîñòè ñõåì.
Äîêàçàòåëüñòâî. Ïóñòü G1, G2 — ñõåìû èç M ðàçìåðîâ n n1 2, ñîîòâåòñòâåííî.
Òðåáóåòñÿ óñòàíîâèòü, ÷òî èç îòíîøåíèÿ G G1 2~ ñëåäóþò óñëîâèÿ 1) è 2) èç ëåì-
ìû 3. Âûïîëíèìîñòü óñëîâèÿ 1) âûòåêàåò èç óòâåðæäåíèÿ 1.
Ïîêàæåì, ÷òî âûïîëíèìî óñëîâèå 2).
Âîçüìåì ïðîèçâîëüíóþ ôóíêöèþ ðàçìåòêè � èç L è ðàññìîòðèì ðàâíîâåëèêèå
ìàðøðóòû w w1 2, , ïðîêëàäûâàåìûå ôóíêöèåé � â G1, G2 ñîîòâåòñòâåííî è èìåþ-
ùèå íîðìó, íå ïðåâûøàþùóþ ÷èñëà n n1 2 1� .
Íà îñíîâàíèè ëåììû 4 è ÷èñòîòû ñõåì G1, G2 ìàðøðóòû w w1 2, ïðåäñòàâèìû
â âèäå
w u w u w ui i i ik ik ik� �0 1 1... , i � 1 2, ,
ãäå äëÿ ëþáîãî j, j k� �0 1, ... , , ïóòè u j1 è u j2 íåñóò ðàâíûå öåïî÷êè, âîçìîæíî
ïóñòûå, à äëÿ ëþáîãî j, j k� 0, ... , , ïóòè w j1 , w j2 íà÷èíàþòñÿ â ñîïðÿæåííûõ
ïðåîáðàçîâàòåëÿõ, êîòîðûì ïðèïèñàíû ðàçëè÷íûå îïåðàòîðíûå ñèìâîëû, ÿâëÿ-
þòñÿ ïóòÿìè â êóñòàõ ñ êîðíåì â ýòèõ ïðåîáðàçîâàòåëÿõ è òàêîâû, ÷òî
h w h wj j( ) ~ ( ).1 2
�
36 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5
Î÷åâèäíî, ÷òî äëÿ ìàðøðóòîâ w w1 2, ïåðâàÿ ïîâòîðÿþùàÿñÿ ïàðà ðàâíîóäà-
ëåííûõ îò èõ íà÷àëà ïðåîáðàçîâàòåëåé ïðèíàäëåæèò ëèáî îòðåçêàì òèïà u, ëèáî îò-
ðåçêàì òèïà w, ïîñêîëüêó â ÷èñòîé ñõåìå îòðåçêè îäíîãî è äðóãîãî òèïà íå èìåþò
îáùèõ ïðåîáðàçîâàòåëåé.
Îòñþäà âûòåêàåò êàê ñîïðÿæåííîñòü ïðåîáðàçîâàòåëåé, ïðèíàäëåæàùèõ ïåð-
âîé ïîâòîðÿþùåéñÿ ïàðå, òàê è ýêâèâàëåíòíîñòü öåïî÷åê, êîòîðûå íåñóò èíòåðâàëû
ïîâòîðà.
Òàêèì îáðàçîì, ñâîéñòâî 2) èç ëåììû 3 èìååò ìåñòî.
Ëåììà 6 äîêàçàíà.
Ðåçóëüòàòîì ïðîâåäåííûõ èññëåäîâàíèé ÿâëÿåòñÿ ñëåäóþùàÿ òåîðåìà.
Òåîðåìà 3. Â óðàâíîâåøåííîé ïîëóãðóïïîâîé ìîäåëè ñ ëåâûì ñîêðàùåíèåì
òåõíèêîé ñëåäîâ óñòàíàâëèâàåòñÿ ðàçðåøèìîñòü ïðîáëåìû ýêâèâàëåíòíîñòè.
Äåéñòâèòåëüíî, êàê áûëî äîêàçàíî òåîðåìîé 2 è ëåììîé 5, ïðîáëåìà ýêâèâà-
ëåíòíîñòè â ðàññìàòðèâàåìîé ìîäåëè ñâîäèòñÿ ê ïðîáëåìå ýêâèâàëåíòíîñòè ÷èñ-
òûõ ñõåì, ïðèíàäëåæàùèõ ìîäåëè. Ðàçðåøèìîñòü ýòîé ïðîáëåìû ñëåäóåò èç
ëåììû 6 è óòâåðæäåíèÿ 3.
Âî ââåäåíèè îòìå÷àëîñü, ÷òî ñàì ôàêò ðàçðåøèìîñòè íå ÿâëÿåòñÿ íîâûì,
îäíàêî íîâèçíà â òîì, ÷òî ïðè ýòîì èñïîëüçîâàëàñü òåõíèêà ñëåäîâ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ï î ä ë î â ÷ å í ê î Ð . È . Èåðàðõèÿ ìîäåëåé ïðîãðàìì // Ïðîãðàììèðîâàíèå. — 1981. — ¹ 2. —
Ñ. 3–14.
2. Ë ÿ ï ó í î â À . À . Î ëîãè÷åñêèõ ñõåìàõ ïðîãðàìì // Ïðîáë. êèáåðíåòèêè. — 1958. — Âûï. 1. —
Ñ. 46–74.
3. ß í î â Þ . È . Î ëîãè÷åñêèõ ñõåìàõ àëãîðèòìîâ // Òàì æå. — 1958. — Âûï. 1. — Ñ. 75–127.
4. Ã ë ó ø ê î â Â . Ì . , Ë å ò è ÷ å â ñ ê è é À . À . Òåîðèÿ äèñêðåòíûõ ïðåîáðàçîâàòåëåé // Èçáð. âîïð.
àëãåáðû è ëîãèêè. — Íîâîñèáèðñê: Íàóêà, 1973. — Ñ. 5–39.
5. Ë å ò è ÷ å â ñ ê è é À . À . Ýêâèâàëåíòíîñòü àâòîìàòîâ îòíîñèòåëüíî ïîëóãðóïï ñ ñîêðàùåíèåì //
Ïðîáë. êèáåðíåòèêè. — 1973. — Âûï. 27. — Ñ. 195–212.
6. Ò ð à õ ò å í á ð î ò Á . À . Ñëîæíîñòü àëãîðèòìîâ è âû÷èñëåíèé (ñïåöêóðñ äëÿ ñòóäåíòîâ ÍÃÓ). —
Íîâîñèáèðñê: Íîâîñèá. ãîñ. óí-ò, 1967. — 258 ñ.
7. Ï î ä ë î â ÷ å í ê î Ð . È . Ïîëóãðóïïîâûå ìîäåëè ïðîãðàìì // Ïðîãðàììèðîâàíèå. — 1981. — ¹ 4. —
Ñ. 3–13.
8. Ï î ä ë î â ÷ å í ê î Ð . È . Îò ñõåì ßíîâà ê òåîðèè ìîäåëåé ïðîãðàìì // Ìàò. âîïð. êèáåðíåòèêè. —
1998. — Âûï 7. — Ñ. 281–302.
9. Ï î ä ë î â ÷ å í ê î Ð . È . Àëãîðèòì êàíîíèçàöèè ïàð ñõåì ïðîãðàìì ñ ïåðåñòàíîâî÷íûìè
îïåðàòîðàìè // Ïðîãðàììèðîâàíèå. — 1997. — ¹ 6. — Ñ. 3–16.
Ïîñòóïèëà 20.11.2008
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5 37
Êëþ÷åâûå ñëîâà íà àíãëèéñêîì
algebraic model of programs, equivalence checking problem, cross-section
technique.
38 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5
|