Проблема мортальности и аффинные автоматы
Проблему мортальності для матриць другого порядку розглянуто з точки зору теорії автоматів. Показано, що ця проблема тісно пов'язана з проблемою досягнення станів у лінійних та афінних автоматах малої розмірності. Доведено, що проблема досягнення є алгоритмічно розв'язуваною для деяких під...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2008 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2008
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/71995 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Проблема мортальности и аффинные автоматы / И.К. Рысцов // Кибернетика и системный анализ. — 2008. — № 2. — С. 24-29. — Бібліогр.: 11 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859818346124410880 |
|---|---|
| author | Рысцов, И.К. |
| author_facet | Рысцов, И.К. |
| citation_txt | Проблема мортальности и аффинные автоматы / И.К. Рысцов // Кибернетика и системный анализ. — 2008. — № 2. — С. 24-29. — Бібліогр.: 11 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Проблему мортальності для матриць другого порядку розглянуто з точки зору теорії автоматів. Показано, що ця проблема тісно пов'язана з проблемою досягнення станів у лінійних та афінних автоматах малої розмірності. Доведено, що проблема досягнення є алгоритмічно розв'язуваною для деяких підкласів одновимірних афінних автоматів.
|
| first_indexed | 2025-12-07T15:23:04Z |
| format | Article |
| fulltext |
ÓÄÊ 519.713.4
È.Ê. ÐÛÑÖÎÂ
ÏÐÎÁËÅÌÀ ÌÎÐÒÀËÜÍÎÑÒÈ È ÀÔÔÈÍÍÛÅ ÀÂÒÎÌÀÒÛ
Êëþ÷åâûå ñëîâà: ïðîáëåìà ìîðòàëüíîñòè, àëãîðèòìè÷åñêèå ïðîáëåìû, ëè-
íåéíûå àâòîìàòû, àôôèííûå àâòîìàòû.
ÂÂÅÄÅÍÈÅ
Ìíîæåñòâî êâàäðàòíûõ ìàòðèö íàçûâàåòñÿ ìîðòàëüíûì, åñëè ñóùåñòâóåò ïî-
ñëåäîâàòåëüíîñòü ìàòðèö èç ýòîãî ìíîæåñòâà, ïðîèçâåäåíèå êîòîðûõ ðàâíî íó-
ëåâîé ìàòðèöå. Ïðîáëåìà ìîðòàëüíîñòè — ýòî àëãîðèòìè÷åñêàÿ ïðîáëåìà,
â êîòîðîé ïî çàäàííîìó ìíîæåñòâó êâàäðàòíûõ ìàòðèö íóæíî îïðåäåëèòü,
ÿâëÿåòñÿ ëè ýòî ìíîæåñòâî ìîðòàëüíûì.
Ì. Ïàòåðñîí â [1] äîêàçàë, ÷òî óæå äëÿ êâàäðàòíûõ ìàòðèö òðåòüåãî ïîðÿäêà
ïðîáëåìà ìîðòàëüíîñòè àëãîðèòìè÷åñêè íåðàçðåøèìà íàä ïîëåì ðàöèîíàëüíûõ
÷èñåë. Íî äëÿ ìàòðèö âòîðîãî ïîðÿäêà ïðîáëåìà îñòàåòñÿ äî ñèõ ïîð îòêðûòîé.
 [2] ïîêàçàíî, ÷òî âîñüìè ìàòðèö òðåòüåãî ïîðÿäêà äîñòàòî÷íî äëÿ íåðàçðåøè-
ìîñòè ïðîáëåìû ìîðòàëüíîñòè. Ïîäðîáíûé îáçîð ïî ïðîáëåìå ìîðòàëüíîñòè è
ìîòèâèðîâêè äëÿ åå èññëåäîâàíèÿ ìîæíî íàéòè â [3]. Â [4] ïîêàçàíî, ÷òî îãðàíè-
÷åííàÿ ïðîáëåìà ìîðòàëüíîñòè äëÿ äâóõ áóëåâûõ ìàòðèö ÿâëÿåòñÿ NP-ïîëíîé.
 äàííîé ðàáîòå ïðîáëåìà ìîðòàëüíîñòè ðàññìàòðèâàåòñÿ ñ àâòîìàòíîé òî÷êè
çðåíèÿ. Ïîêàçàíî, ÷òî îíà òåñíî ñâÿçàíà ñ ïðîáëåìîé äîñòèæèìîñòè ñîñòîÿíèé â ëè-
íåéíûõ è àôôèííûõ àâòîìàòàõ ìàëîé ðàçìåðíîñòè. Êðîìå òîãî, ïîêàçàíî, ÷òî ïðî-
áëåìà äîñòèæèìîñòè ñîñòîÿíèé àëãîðèòìè÷åñêè ðàçðåøèìà äëÿ îäíîìåðíûõ ëèíåé-
íûõ àâòîìàòîâ è äëÿ íåêîòîðûõ ïîäêëàññîâ îäíîìåðíûõ àôôèííûõ àâòîìàòîâ.
1. ÏÐÅÄÂÀÐÈÒÅËÜÍÛÅ ÑÂÅÄÅÍÈß
Íàïîìíèì, ÷òî ëèíåéíûì n-ìåðíûì àâòîìàòîì íàä ïîëåì ðàöèîíàëüíûõ ÷è-
ñåë Q íàçûâàåòñÿ òðîéêà A Q X fn� ( , , ), ãäå Q n — ëèíåéíîå ïðîñòðàíñòâî
ñîñòîÿíèé (âåêòîðîâ äëèíû n), X — êîíå÷íîå ìíîæåñòâî âõîäíûõ ñèìâîëîâ,
à f — îòîáðàæåíèå âèäà f X n Q: ( , )� Mat , êîòîðîå îòîáðàæàåò ìíîæåñòâî X
âî ìíîæåñòâî êâàäðàòíûõ ìàòðèö n-ãî ïîðÿäêà ñ ðàöèîíàëüíûìè ýëåìåíòàìè.
Îòîáðàæåíèå f îïðåäåëÿåò ôóíêöèþ ïåðåõîäîâ F s x s f x( , ) ( )� � , ãäå ñïðàâà
ñòîèò ïðîèçâåäåíèå âåêòîðà ñòðîêè s íà ìàòðèöó f x( ). Äðóãèìè ñëîâàìè, ôóíê-
öèÿ ïåðåõîäîâ áóäåò ëèíåéíîé ïî ïåðâîìó àðãóìåíòó, íî, âîîáùå ãîâîðÿ, íåëè-
íåéíîé ïî âòîðîìó. ×èñëî n íàçûâàåòñÿ ðàçìåðíîñòüþ ëèíåéíîãî àâòîìàòà [5].
Ïîñêîëüêó ìíîæåñòâî ìàòðèö Mat ( , )n Q ÿâëÿåòñÿ ìóëüòèïëèêàòèâíûì ìî-
íîèäîì, òî îòîáðàæåíèå f ìîæíî ïðîäîëæèòü äî ãîìîìîðôèçìà, îïðåäåëåííîãî
íà ñâîáîäíîì ìîíîèäå f X n Q: ( , )* � Mat , êîòîðûé êàæäîìó âõîäíîìó ñëîâó
w x x xm� 1 2 � ñîïîñòàâëÿåò ïðîèçâåäåíèå áàçîâûõ ìàòðèö
f w f x f x f xm( ) ( ) ( ) ( )� � �1 2 � . Òîãäà ôóíêöèÿ ïåðåõîäîâ îïðåäåëÿåòñÿ äëÿ
ëþáûõ âõîäíûõ ñëîâ ïî ôîðìóëå F s w s f w( , ) ( )� � , ãäå ïðàâàÿ ÷àñòü ïî-ïðåæíå-
ìó ïîíèìàåòñÿ êàê ïðîèçâåäåíèå âåêòîðà íà ìàòðèöó. Ìíîæåñòâîì äîñòèæèìûõ
ñîñòîÿíèé (ìíîæåñòâîì äîñòèæèìîñòè) äëÿ ñîñòîÿíèÿ s Q n� â àâòîìàòå A íàçû-
âàåòñÿ ìíîæåñòâî �R s F s w w XA ( ) ( , ) *� �{ }.
24 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2
© È.Ê. Ðûñöîâ, 2008
Ïóñòü A Q X f� ( , , )2 — äâóìåðíûé ëèíåéíûé àâòîìàò, òîãäà âõîäíîå ñëî-
âî w íàçîâåì íóëåâûì äëÿ A, åñëè f w( ) � 0. Ìíîæåñòâî âñåõ íóëåâûõ ñëîâ äëÿ A
îáîçíà÷èì Z A w f w( ) | ( )� �{ }0 . Òîãäà ïðîáëåìó ìîðòàëüíîñòè ìîæíî ñôîðìó-
ëèðîâàòü ñëåäóþùèì îáðàçîì.
Ïðîáëåìà 1 (ìîðòàëüíîñòü). Çàäàí äâóìåðíûé ëèíåéíûé àâòîìàò A, òðåáó-
åòñÿ îïðåäåëèòü, ÿâëÿåòñÿ ëè ìíîæåñòâî Z A( ) íåïóñòûì.
Ëèíåéíûé àâòîìàò A Q X f� ( , , )2 íàçûâàåòñÿ ãðóïïîâûì, åñëè ìàòðèöû
f x( ) îáðàòèìûå (íåîñîáåííûå) äëÿ âñåõ x X� . Êîíå÷íî, åñëè àâòîìàò A èìååò
íóëåâîå ñëîâî, òî ó íåãî äîëæåí áûòü, ïî êðàéíåé ìåðå, îäèí ñèíãóëÿðíûé âõîä-
íîé ñèìâîë x 1, äëÿ êîòîðîãî ìàòðèöà f x( )1 ñèíãóëÿðíàÿ (îñîáåííàÿ). Óäèâè-
òåëüíî, íî îäíîãî ñèíãóëÿðíîãî ñèìâîëà îêàçûâàåòñÿ äîñòàòî÷íî äëÿ ñóùåñòâî-
âàíèÿ íóëåâîãî ñëîâà. Ñëåäóþùåå ïðåäëîæåíèå äîêàçàíî â ðàáîòàõ [3, 6] äëÿ
ìàòðèö âòîðîãî ïîðÿäêà.
Ïðåäëîæåíèå 1. Äëÿ ëþáîãî äâóìåðíîãî ëèíåéíîãî àâòîìàòà A ñóùåñòâóåò
äâóìåðíûé ëèíåéíûé àâòîìàò B, èìåþùèé òîëüêî îäèí ñèíãóëÿðíûé âõîäíîé
ñèìâîë, òàêîé, ÷òî Z A( ) � � òîãäà è òîëüêî òîãäà, êîãäà Z B( ) � �.
Ýòî ïðåäëîæåíèå ïîêàçûâàåò, ÷òî îñíîâíàÿ òðóäíîñòü â ïðîáëåìå ìîðòàëü-
íîñòè çàêëþ÷àåòñÿ â äîñòèæèìîñòè ñîñòîÿíèé ñîîòâåòñòâóþùåãî ãðóïïîâîãî ëè-
íåéíîãî àâòîìàòà. Äåéñòâèòåëüíî, íåíóëåâàÿ ñèíãóëÿðíàÿ ìàòðèöà âòîðîãî ïî-
ðÿäêà M f x� ( )1 õàðàêòåðèçóåòñÿ ñâîèì îäíîìåðíûì îáðàçîì Im ( )M è îäíî-
ìåðíûì ÿäðîì Ker ( )M , êîòîðûå ÿâëÿþòñÿ ïðÿìûìè ëèíèÿìè, ïðîõîäÿùèìè
÷åðåç íà÷àëî êîîðäèíàò. Çíà÷èò, íóëåâîå ñëîâî â àâòîìàòå B áóäåò ñóùåñòâîâàòü
òîãäà è òîëüêî òîãäà, êîãäà ñ ïîìîùüþ ãðóïïîâûõ ñèìâîëîâ ïðÿìóþ Im ( )M
ìîæíî ïðåîáðàçîâàòü â ïðÿìóþ Ker ( )M . Ýòî ïîçâîëÿåò ñôîðìóëèðîâàòü
ïðîáëåìó äîñòèæèìîñòè ñîñòîÿíèé àâòîìàòà.
Î÷åâèäíî, ÷òî â ïðîáëåìå ìîðòàëüíîñòè ìàòðèöû ìîæíî ðàññìàòðèâàòü ñ òî÷-
íîñòüþ äî íåíóëåâîãî ñêàëÿðíîãî ìíîæèòåëÿ, ïîýòîìó áóäåì ãîâîðèòü, ÷òî ñîñòî-
ÿíèÿ s è t àâòîìàòà A ýêâèâàëåíòíû, åñëè s t� � , ãäå � — íåíóëåâîå ðàöèîíàëüíîå
÷èñëî (ñêàëÿð). Ýòî îòíîøåíèå áóäåò êîíãðóýíöèåé â ëèíåéíîì àâòîìàòå, ïîýòîìó
ìîæíî ïîñòðîèòü ôàêòîð-àâòîìàò ïî ýòîé êîíãðóýíöèè, êîòîðûé áóäåò äåéñòâî-
âàòü â ïðîåêòèâíîì ïðîñòðàíñòâå. Íî âìåñòî ýòîãî ââåäåííîå îòíîøåíèå ïîçâîëÿ-
åò ñôîðìóëèðîâàòü ïðîáëåìó äîñòèæèìîñòè ñîñòîÿíèé êàê «ïîòî÷å÷íóþ».
Ïðîáëåìà 2 (äîñòèæèìîñòü). Çàäàí äâóìåðíûé ëèíåéíûé ãðóïïîâîé àâòî-
ìàò B è äâà åãî ñîñòîÿíèÿ — s è t. Òðåáóåòñÿ îïðåäåëèòü, ñóùåñòâóåò ëè ðàöèî-
íàëüíîå ÷èñëî � òàêîå, ÷òî � t R sB� ( ).
Èíòåðåñíî îòìåòèòü, ÷òî âïåðâûå ïðîáëåìà ìîðòàëüíîñòè áûëà ñôîðìóëè-
ðîâàíà èìåííî êàê ïðîáëåìà äîñòèæèìîñòè ïðÿìûõ íà ïëîñêîñòè [7]. Ýòî ïîêà-
çûâàåò, ÷òî àâòîð ïðîáëåìû, ïî-âèäèìîìó, çíàë î ïðåäëîæåíèè 1, íî íå ñôîðìó-
ëèðîâàë åãî ÿâíî. Èç ïðåäëîæåíèÿ 1 ïîëó÷àåì ñëåäóþùåå óòâåðæäåíèå.
Ïðåäëîæåíèå 2. Ïðîáëåìà ìîðòàëüíîñòè ðàçðåøèìà òîãäà è òîëüêî òîãäà,
êîãäà ðàçðåøèìà ïðîáëåìà äîñòèæèìîñòè.
 îáùåì ñëó÷àå ïðîáëåìû 1 è 2 ÿâëÿþòñÿ òðóäíûìè àëãîðèòìè÷åñêèìè ïðî-
áëåìàìè, ïîýòîìó â [3] áûëî ïðåäëîæåíî ðàññìîòðåòü ýòè ïðîáëåìû äëÿ òðåó-
ãîëüíûõ àâòîìàòîâ, ò.å. äâóìåðíûõ ëèíåéíûõ àâòîìàòîâ, ó êîòîðûõ âñå îáðàòè-
ìûå ìàòðèöû f x( ) òðåóãîëüíûå. Äëÿ îïðåäåëåííîñòè ìîæíî ñ÷èòàòü ýòè
ìàòðèöû íèæíå-òðåóãîëüíûìè, ò.å. èìåþùèìè âèä
f x
a x
b x
( )
( )
( )
�
�
�
�
0
1
, (1)
ãäå a x( ), b x( ) — ðàöèîíàëüíûå ÷èñëà, ïðè÷åì a x( ) � 0 äëÿ âñåõ x X� .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2 25
Çàìåòèì, ÷òî âñå ïðÿìûå ïàðàëëåëüíûå îñè àáñöèññ èíâàðèàíòíû ïîä äå-
éñòâèåì òðåóãîëüíîãî àâòîìàòà, ïîýòîìó â ïðîáëåìå äîñòèæèìîñòè 2 äëÿ òðåó-
ãîëüíûõ àâòîìàòîâ ìîæíî îïóñòèòü ìíîæèòåëü � è ñôîðìóëèðîâàòü åå êàê îáû÷-
íóþ äîñòèæèìîñòü äëÿ ñîñòîÿíèé, íàõîäÿùèõñÿ, íàïðèìåð, íà ïðÿìîé y �1.
Ïðîáëåìà 3. Çàäàí äâóìåðíûé ëèíåéíûé òðåóãîëüíûé àâòîìàò
A Q X f� ( , , )2 è äâà åãî ñîñòîÿíèÿ: ( , )s 1 , ( , )t 1 , ãäå s t Q, � . Òðåáóåòñÿ îïðåäåëèòü,
äîñòèãàåòñÿ ëè èç ñîñòîÿíèÿ ( , )s 1 ñîñòîÿíèå ( , )t 1 .
Êàê âèäíî èç ôîðìóëèðîâêè ýòîé ïðîáëåìû, ïðîöåññ äîñòèæèìîñòè ñîñòîÿ-
íèé â òðåóãîëüíîì àâòîìàòå ìîæíî ñ÷èòàòü â íåêîòîðîì ñìûñëå îäíîìåðíûì,
ïîýòîìó åñòåñòâåííî ïåðåéòè ê ðàññìîòðåíèþ îäíîìåðíûõ àâòîìàòîâ, íî äëÿ
ýòîãî íóæíû àâòîìàòû áîëåå îáùåãî âèäà.
Îäíîìåðíûì àôôèííûì àâòîìàòîì íàçîâåì òðîéêó îáúåêòîâ A Q X f� ( , , ),
ãäå Q — ïîëå ðàöèîíàëüíûõ ÷èñåë (ìíîæåñòâî ñîñòîÿíèé), X — êîíå÷íîå ìíî-
æåñòâî âõîäíûõ ñèìâîëîâ, à f — ôóíêöèÿ ïåðåõîäîâ f s x s a x b x( , ) ( ) ( )� � � ,
ãäå a x( ), b x( ) — ðàöèîíàëüíûå ÷èñëà, çàâèñÿùèå îò âõîäíîãî ñèìâîëà x. Òàêèå
àâòîìàòû áóäåì íàçûâàòü ïðîñòî àôôèííûìè àâòîìàòàìè, ïîñêîëüêó èõ ìíîãî-
ìåðíûå àíàëîãè â äàííîé ðàáîòå íå ðàññìàòðèâàþòñÿ. Îòìåòèì, ÷òî ëèíåéíûå
àâòîìàòû ÿâëÿþòñÿ ÷àñòíûì ñëó÷àåì àôôèííûõ, êîãäà b x( ) � 0 äëÿ âñåõ x X� .
Àôôèííûé àâòîìàò A íàçûâàåòñÿ ãðóïïîâûì, åñëè a x( ) � 0 äëÿ âñåõ x X� .
Ôóíêöèÿ ïåðåõîäîâ àôôèííîãî àâòîìàòà îáû÷íûì îáðàçîì ïðîäîëæàåòñÿ íà
âñå âõîäíûå ñëîâà è äëÿ âõîäíîãî ñëîâà w x x xm� 1 2 � ïðåîáðàçîâàíèå ñîñòîÿíèé
îñóùåñòâëÿåòñÿ ïî ôîðìóëå f s w s a w b w( , ) ( ) ( )� � � , ãäå a w( ) �
� � �a x a x a xm( ) ( ) ( )1 2 � , à b w( ) çàâèñèò îò a x b xi i( ), ( ), 1 � �i m. Êîíêðåòíûé
âèä ýòîé çàâèñèìîñòè óêàæåì äàëåå. Ìíîæåñòâî äîñòèæèìûõ ñîñòîÿíèé èç ñî-
ñòîÿíèÿ s îïðåäåëÿåòñÿ îáû÷íûì îáðàçîì: �R s f s wA ( ) ( , )� { w X� * }. Ñëåäóþ-
ùåå ïðåäëîæåíèå â äðóãèõ òåðìèíàõ äîêàçàíî â ðàáîòå [3].
Ïðåäëîæåíèå 3. Ïðîáëåìà äîñòèæèìîñòè â äâóìåðíûõ ëèíåéíûõ òðåóãîëü-
íûõ àâòîìàòàõ ðàçðåøèìà òîãäà è òîëüêî òîãäà, êîãäà ðàçðåøèìà ïðîáëåìà äîñ-
òèæèìîñòè â îäíîìåðíûõ àôôèííûõ ãðóïïîâûõ àâòîìàòàõ.
Äîêàçàòåëüñòâî. Ñîïîñòàâèì êàæäîé òðåóãîëüíîé ìàòðèöå âèäà (1) òðåó-
ãîëüíîãî àâòîìàòà A ïåðåõîä f s x s a x b x( , ) ( ) ( )� � � â àôôèííîì àâòîìàòå B è,
íàîáîðîò, êàæäîìó ïåðåõîäó â ãðóïïîâîì àôôèííîì àâòîìàòå ìîæíî ñîïîñòà-
âèòü òðåóãîëüíóþ ìàòðèöó âèäà (1). Íåòðóäíî âèäåòü, ÷òî äëÿ çàäàííûõ ðàöèî-
íàëüíûõ ÷èñåë s è t áóäåò âûïîëíÿòüñÿ óñëîâèå ( , ) (( , ))t R sA1 1� òîãäà è òîëüêî
òîãäà, êîãäà t R sB� ( ) Òàêèì îáðàçîì, ïðåäëîæåíèå äîêàçàíî.
Öåëåñîîáðàçíî ïîäðîáíåå èññëåäîâàòü ïðîáëåìó äîñòèæèìîñòè ñîñòîÿíèé â
àôôèííûõ àâòîìàòàõ. Îñíîâíûå ðåçóëüòàòû äàííîé ðàáîòû ñôîðìóëèðóåì
ñëåäóþùèì îáðàçîì:
• äîêàçàíà ðàçðåøèìîñòü ïðîáëåìû äîñòèæèìîñòè ñîñòîÿíèé â îäíîìåðíûõ
ëèíåéíûõ àâòîìàòàõ;
• äîêàçàíà ðàçðåøèìîñòü ïðîáëåìû äîñòèæèìîñòè ñîñòîÿíèé â àôôèííûõ
àâòîìàòàõ, êîãäà a x( ) �1 äëÿ âñåõ x X� , ëèáî êîãäà 0 1� �a x( ) äëÿ âñåõ x X� ,
ëèáî êîãäà a x( ) �1 äëÿ âñåõ x X� .
2. ËÈÍÅÉÍÛÅ ÀÂÒÎÌÀÒÛ
Ñíà÷àëà ðàññìîòðèì ñàìûé ïðîñòîé ñëó÷àé ïðîáëåìû äîñòèæèìîñòè, à èìåí-
íî ïðîáëåìó äîñòèæèìîñòè ñîñòîÿíèé â îäíîìåðíûõ ëèíåéíûõ àâòîìàòàõ.
Ïóñòü A Q X f� ( , , ) — îäíîìåðíûé ëèíåéíûé àâòîìàò, è ïóñòü
w x x xm� 1 2 � — âõîäíîå ñëîâî, òîãäà ïî îïðåäåëåíèþ èìååì ðàâåíñòâî
f s wm s a x a x a xm( , ) ( ) ( ( ) ( )� � �1 2 � . Îòñþäà ñëåäóåò, ÷òî t R sA� ( ) òîãäà è
26 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2
òîëüêî òîãäà, êîãäà ñóùåñòâóþò íåîòðèöàòåëüíûå öåëûå ÷èñëà n x( ), äëÿ
êîòîðûõ âûïîëíÿåòñÿ ðàâåíñòâî
s a x t
x X
n x
�
� �( ) ( ) . (2)
Òàêèì îáðàçîì, ïîëó÷àåì ñëåäóþùåå óòâåðæäåíèå.
Òåîðåìà 1. Ïðîáëåìà äîñòèæèìîñòè ñîñòîÿíèé â îäíîìåðíûõ ëèíåéíûõ àâ-
òîìàòàõ ÿâëÿåòñÿ àëãîðèòìè÷åñêè ðàçðåøèìîé.
Äîêàçàòåëüñòâî. Ïðåäñòàâèì â ðàâåíñòâå (2) ðàöèîíàëüíûå ÷èñëà s t, è a x( )
èõ íåñîêðàòèìûìè öåëî÷èñëåííûìè äðîáÿìè è ðàçëîæèì âñå öåëûå ÷èñëà íà
ïðîñòûå. Òîãäà â (2) ìîæåò âñòðåòèòüñÿ òîëüêî êîíå÷íîå ÷èñëî r ïðîñòûõ ÷èñåë
p p p r1 2, , ,� . Ïðèðàâíèâàÿ ïîêàçàòåëè ñòåïåíè ïðè êàæäîì ïðîñòîì ÷èñëå â
ëåâîé è ïðàâîé ÷àñòÿõ ðàâåíñòâà, ïîëó÷èì ñèñòåìó ëèíåéíûõ äèîôàíòîâûõ óðàâ-
íåíèé. Òî÷íåå, ïîëó÷èì çàäà÷ó ëèíåéíîãî öåëî÷èñëåííîãî ïðîãðàììèðîâàíèÿ
âèäà M Y C� � , Y � 0, ãäå M — öåëî÷èñëåííàÿ ìàòðèöà ðàçìåðíîñòè r k� ,
� �k X� , Y n x n x k� ( ( ), , ( ))1 � — âåêòîð íåèçâåñòíûõ, C — âåêòîð êîíñòàíò.
Èçâåñòíî, ÷òî ïðîáëåìà ñóùåñòâîâàíèÿ äîïóñòèìîãî ðåøåíèÿ ó çàäà÷è ëèíåéíî-
ãî öåëî÷èñëåííîãî ïðîãðàììèðîâàíèÿ àëãîðèòìè÷åñêè ðàçðåøèìà [8]. Îòñþäà
âûòåêàåò ñïðàâåäëèâîñòü óòâåðæäåíèÿ òåîðåìû.
Íåòðóäíî âèäåòü, ÷òî ïðîáëåìà äîñòèæèìîñòè â îäíîìåðíûõ ëèíåéíûõ àâ-
òîìàòàõ ñîîòâåòñòâóåò ïðîáëåìå ìîðòàëüíîñòè äëÿ ìàòðèö âòîðîãî ïîðÿäêà, êîã-
äà âñå íåîñîáåííûå ìàòðèöû äèàãîíàëüíûå. Çíà÷èò, â êà÷åñòâå ñëåäñòâèÿ èç òåî-
ðåìû 1 è ïðåäëîæåíèÿ 1 ïîëó÷àåì óòâåðæäåíèå.
Ñëåäñòâèå 1. Ïðîáëåìà ìîðòàëüíîñòè ðàçðåøèìà äëÿ äâóìåðíûõ ëèíåéíûõ àâ-
òîìàòîâ, ó êîòîðûõ âñåì ãðóïïîâûì ñèìâîëàì ñîîòâåòñòâóþò äèàãîíàëüíûå ìàòðèöû.
3. ÀÔÔÈÍÍÛÅ ÀÂÒÎÌÀÒÛ
Íà÷íåì ñíîâà ñ ïðîñòîãî ñëó÷àÿ. Àôôèííûé àâòîìàò A Q X f� ( , , ) íàçîâåì
óíèòàðíûì, åñëè a x( ) �1 äëÿ âñåõ x X� .  ýòîì ñëó÷àå äëÿ âõîäíîãî ñëîâà
w x x xm� 1 2 � èìååì f s w s b x b xm( , ) ( ) ( )� � � �1 � . Îòñþäà ñëåäóåò, ÷òî
t R sA� ( ) òîãäà è òîëüêî òîãäà, êîãäà ñóùåñòâóþò íåîòðèöàòåëüíûå öåëûå ÷èñ-
ëà n x( ), x X� , äëÿ êîòîðûõ âûïîëíÿåòñÿ ñëåäóþùåå ðàâåíñòâî:
s b x n x t
x X
� �
�
� ( ) ( ) . (3)
Ýòî ëèíåéíîå äèîôàíòîâî óðàâíåíèå ÿâëÿåòñÿ àääèòèâíûì àíàëîãîì ðàâå-
íñòâà (2). Òîãäà ðàçðåøèìîñòü ïðîáëåìû ñóùåñòâîâàíèÿ ðåøåíèÿ óðàâíåíèÿ (3)
ñëåäóåò èç ðàçðåøèìîñòè ïðîáëåìû ñóùåñòâîâàíèÿ ðåøåíèÿ ó ëèíåéíûõ äèî-
ôàíòîâûõ óðàâíåíèé [9]. Îòñþäà ïîëó÷àåì ñëåäóþùåå óòâåðæäåíèå.
Òåîðåìà 2. Ïðîáëåìà äîñòèæèìîñòè ñîñòîÿíèé â óíèòàðíûõ àôôèííûõ àâ-
òîìàòàõ ÿâëÿåòñÿ àëãîðèòìè÷åñêè ðàçðåøèìîé.
Èç äîêàçàòåëüñòâà ïðåäëîæåíèÿ 3 âèäíî, ÷òî ïðîáëåìå äîñòèæèìîñòè â óíè-
òàðíûõ àôôèííûõ àâòîìàòàõ ñîîòâåòñòâóåò ïðîáëåìà äîñòèæèìîñòè äëÿ äâóìåð-
íûõ òðåóãîëüíûõ àâòîìàòîâ, ó êîòîðûõ âñå ìàòðèöû óíèòðåóãîëüíûå:
f x
b x
( )
( )
�
�
�
�
1 0
1
.
(4)
Çíà÷èò, â êà÷åñòâå ñëåäñòâèÿ èç òåîðåìû 2 è ïðåäëîæåíèé 2 è 3 ïîëó÷àåì
ñëåäóþùåå óòâåðæäåíèå.
Ñëåäñòâèå 2. Ïðîáëåìà ìîðòàëüíîñòè ðàçðåøèìà äëÿ äâóìåðíûõ ëèíåéíûõ
àâòîìàòîâ, ó êîòîðûõ âñåì ãðóïïîâûì ñèìâîëàì ñîîòâåòñòâóþò óíèòðåóãîëüíûå
ìàòðèöû âèäà (4).
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2 27
Òåïåðü äåòàëüíåå ðàññìîòðèì ïåðåõîäû â àôôèííîì àâòîìàòå A �
� ( , , )Q X f . Ïóñòü l w m( ) � — äëèíà âõîäíîãî ñëîâà w x x xm� 1 2 � , è ïóñòü
� i i mw x x( ) � � 1 � — i-é ñóôôèêñ ñëîâà w, 1 � �i m. Ïðåäïîëàãàåòñÿ, ÷òî
� m w e( ) � , ãäå e — ïóñòîå ñëîâî. Äàëåå, ïóñòü a w a x a x( ) ( ) ( )� � �1 2 � � a xm( ) —
ãîìîìîðôèçì ñâîáîäíîãî ìîíîèäà a X Q: * � â ìóëüòèïëèêàòèâíóþ ãðóïïó ðà-
öèîíàëüíûõ ÷èñåë. Ñëåäóþùàÿ ôîðìóëà, êîòîðàÿ ëåãêî äîêàçûâàåòñÿ èíäóêöèåé
ïî äëèíå âõîäíîãî ñëîâà, ìîæåò ðàññìàòðèâàòüñÿ êàê îáîáùåíèå ôîðìóëû
ïåðåõîäà äëÿ êëàññè÷åñêèõ ëèíåéíûõ àâòîìàòîâ [10]:
f s w s a w a w b x
i
m
i i( , ) ( ) ( ( )) ( )� �
�
�
1
� . (5)
Îïðåäåëåíèå 1. Àôôèííûé àâòîìàò A Q X f� ( , , ) íàçîâåì ñæèìàþùèì,
åñëè 0 1� �a x( ) äëÿ âñåõ x X� .
Ëåììà. Åñëè àôôèííûé àâòîìàò A Q X f� ( , , ) ÿâëÿåòñÿ ñæèìàþùèì, òî
ìíîæåñòâî R sA ( ) áóäåò îãðàíè÷åííûì äëÿ ëþáîãî s Q� .
Äîêàçàòåëüñòâî. Ïîëîæèì c a x x X� �max ( ) |{ }, d b x� max | ( )| |{ x X� } è çà-
ìåòèì, ÷òî 0 1� �c . Òîãäà èç ñâîéñòâà (5) ïîëó÷àåì ñëåäóþùèå íåðàâåíñòâà:
f s w s c c d s
d
c
m
i
m
m i( , )| | | | |� � � �
��
��
1 1
. (6)
Òàêèì îáðàçîì, ëåììà äîêàçàíà.
Ââåäåì òåïåðü ïîíÿòèå îáðàòíîãî àâòîìàòà äëÿ ãðóïïîâîãî àôôèííîãî àâòî-
ìàòà, êîòîðîå îêàçûâàåòñÿ ïîëåçíûì âî ìíîãèõ ñèòóàöèÿõ. Íàïîìíèì, ÷òî àô-
ôèííûé àâòîìàò A Q X f� ( , , ) íàçûâàåòñÿ ãðóïïîâûì, åñëè a x( ) � 0 äëÿ âñåõ
x X� .  ýòîì ñëó÷àå âñå âõîäíûå ñèìâîëû äåéñòâóþò íà ìíîæåñòâå ñîñòîÿíèé Q
ëèíåéíî è âçàèìíî îäíîçíà÷íî, ïîýòîìó ìîæíî îáû÷íûì îáðàçîì îïðåäåëèòü
îáðàòíûé àôôèííûé àâòîìàò inv ( ) ( , , )A Q X g� , â êîòîðîì
g t x t b x a x( , ) ( ( )) / ( )� � äëÿ âñåõ x X� . Èíäóêöèåé ïî äëèíå âõîäíîãî ñëîâà
w x x xm� 1 2 � ëåãêî ïîêàçàòü, ÷òî â àâòîìàòå A âûïîëíÿåòñÿ óñëîâèå f s w t( , ) �
òîãäà è òîëüêî òîãäà, êîãäà â àâòîìàòå inv ( )A âûïîëíÿåòñÿ óñëîâèå
g t w s( , )� �1 , ãäå w x x xm m
�
��1
1 1� — îáðàòíîå äëÿ w ñëîâî. Òàêèì îáðà-
çîì, ïîëó÷àåì ñëåäóþùåå ñâîéñòâî:
t R s s R tA A� � �( ) ( )( )inv . (7)
Îïðåäåëåíèå 2. Àôôèííûé àâòîìàò A Q X f� ( , , ) íàçîâåì óâåëè÷èâàþùèì,
åñëè a x( ) �1 äëÿ âñåõ x X� .
Òåîðåìà 3. Ïðîáëåìà äîñòèæèìîñòè ñîñòîÿíèé â ñæèìàþùèõ è óâåëè÷èâà-
þùèõ àôôèííûõ àâòîìàòàõ ÿâëÿåòñÿ àëãîðèòìè÷åñêè ðàçðåøèìîé.
Äîêàçàòåëüñòâî. Ïóñòü A Q X f� ( , , ) — ñæèìàþùèé àôôèííûé àâòîìàò, è
ïóñòü çàäàíû ðàöèîíàëüíûå ÷èñëà s è t, ïðè÷åì t p q� / , ãäå p è q — âçàèìíî
ïðîñòûå öåëûå ÷èñëà. Òîãäà ñîãëàñíî ëåììå ìíîæåñòâî R sA ( ) è ìíîæåñòâî
R s q u q y R sA A( ) | ( )� �{ } îãðàíè÷åííûå. Çíà÷èò, ìíîæåñòâî R s qA ( ) � ñîäåðæèò
òîëüêî êîíå÷íîå ÷èñëî öåëûõ ÷èñåë è èõ ìîæíî íàéòè, íàïðèìåð, ïåðåáèðàÿ âñå
âõîäíûå ñëîâà äî çàðàíåå èçâåñòíîé äëèíû. Ñîîòâåòñòâóþùóþ ãðàíèöó íà äëèíó
ñëîâ ìîæíî ïîëó÷èòü èç ñâîéñòâà (6). Îñòàåòñÿ çàìåòèòü, ÷òî óñëîâèå t R sA� ( ) ðàâ-
íîñèëüíî óñëîâèþ p R s qA� ( ) , è òåîðåìà â ýòîì ñëó÷àå äîêàçàíà.
Åñëè A Q X f� ( , , ) — óâåëè÷èâàþùèé àôôèííûé àâòîìàò, òî åãî îáðàòíûé
inv ( ) ( , , )A Q X g� áóäåò â ýòîì ñëó÷àå ñæèìàþùèì, ïîñêîëüêó 0 11� ��a x( )
äëÿ âñåõ x X� . Òîãäà óòâåðæäåíèå òåîðåìû ñëåäóåò èç ñâîéñòâà (7) è ðàçðåøè-
ìîñòè ïðîáëåìû äîñòèæèìîñòè äëÿ ñæèìàþùèõ àâòîìàòîâ. Òàêèì îáðàçîì, òåî-
ðåìà ïîëíîñòüþ äîêàçàíà.
 ðåçóëüòàòå èç ýòîé òåîðåìû è ïðåäëîæåíèé 2 è 3 ïîëó÷àåì ñëåäóþùåå óòâåðæäåíèå.
28 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2
Ñëåäñòâèå 3. Ïðîáëåìà ìîðòàëüíîñòè ðàçðåøèìà äëÿ äâóìåðíûõ ëèíåéíûõ
àâòîìàòîâ, ó êîòîðûõ âñåì ãðóïïîâûì ñèìâîëàì ñîîòâåòñòâóþò òðåóãîëüíûå
ìàòðèöû (1), ïðè÷åì 0 1� �a x( ) äëÿ âñåõ x X� èëè a x( ) �1äëÿ âñåõ x X� .
 çàêëþ÷åíèå ðàññìîòðèì ñàìûé ñëîæíûé ñëó÷àé, êîãäà â àôôèííîì àâòî-
ìàòå åñòü äâà âõîäíûõ ñèìâîëà x è y, êîòîðûå óäîâëåòâîðÿþò óñëîâèþ
| ( )| | ( ) |a x a y� �1 . Äëÿ èëëþñòðàöèè âîçíèêàþùèõ çäåñü òðóäíîñòåé äîñòàòî÷íî
íàïîìíèòü èçâåñòíóþ ÷èñëîâóþ çàäà÷ó, êîòîðóþ íàçûâàþò «óìíîæèòü íà òðè è
ïðèáàâèòü åäèíèöó» [11]. Ïóñòü A N x y f1 � ( , , , ){ } — «÷àñòè÷íûé» àôôèííûé
àâòîìàò, îïðåäåëåííûé íà ìíîæåñòâå íàòóðàëüíûõ ÷èñåë N ñëåäóþùèì îáðà-
çîì: f s x s( , ) /� 2, åñëè s — ÷åòíîå ÷èñëî, è f s y s( , ) � � �3 1, åñëè s — íå÷åòíîå
÷èñëî, áîëüøåå åäèíèöû. Òðåáóåòñÿ äîêàçàòü, ÷òî èç ëþáîãî ñîñòîÿíèÿ äîñòèãà-
åòñÿ ïåðâîå ñîñòîÿíèå, ò.å. àâòîìàò, â êîíöå êîíöîâ, îñòàíàâëèâàåòñÿ íåçàâèñèìî
îò íà÷àëüíîãî ñîñòîÿíèÿ.
Õîòÿ A1 è íå ñîâñåì «÷èñòûé» àôôèííûé àâòîìàò, òåì íå ìåíåå ðîäñòâî
ýòîé ïðîáëåìû ñ ïðîáëåìîé äîñòèæèìîñòè íå âûçûâàåò ñîìíåíèé. Â äàííîì
ñëó÷àå òàêæå îêàçûâàåòñÿ ïîëåçíûì «îáðàòíûé» àâòîìàò, êîòîðûé ïîìîãàåò ïî-
íÿòü àðèôìåòè÷åñêóþ ñòðóêòóðó ìíîæåñòâ ñîñòîÿíèé, íàõîäÿùèõñÿ íà îäíîì
óðîâíå äîñòèæèìîñòè [11]. Êàê ïîêàçûâàþò êîìïüþòåðíûå ýêñïåðèìåíòû, åñëè
s� 1040 , òî àâòîìàò âñåãäà îñòàíàâëèâàåòñÿ, íî ïîëíîãî äîêàçàòåëüñòâà, íàñêîëü-
êî èçâåñòíî àâòîðó, äî ñèõ ïîð íåò.
ÇÀÊËÞ×ÅÍÈÅ
Ïîëó÷åííûå ðåçóëüòàòû âñåëÿþò íåêîòîðóþ íàäåæäó íà òî, ÷òî ïðîáëåìà äîñ-
òèæèìîñòè äëÿ îäíîìåðíûõ àôôèííûõ àâòîìàòîâ ìîæåò îêàçàòüñÿ àëãîðèòìè-
÷åñêè ðàçðåøèìîé. Çäåñü ìîæíî äâèãàòüñÿ è äàëüøå, íàïðèìåð, îáúåäèíèòü
óíèòàðíûé è ñæèìàþùèé àâòîìàòû â îäèí àâòîìàò è ðàññìîòðåòü äëÿ íåãî
ïðîáëåìó äîñòèæèìîñòè. Îäíàêî ìíîæåñòâî äîñòèæèìîñòè äëÿ àôôèííîãî àâ-
òîìàòà ìîæåò èìåòü î÷åíü ñëîæíóþ ñòðóêòóðó. Íàïðèìåð, íåòðóäíî ïîêàçàòü,
÷òî ðàöèîíàëüíûå òî÷êè èç ìíîæåñòâà Êàíòîðà îáðàçóþò ìíîæåñòâî äîñòèæè-
ìîñòè äëÿ íåêîòîðîãî àôôèííîãî àâòîìàòà. Ýòî ñâèäåòåëüñòâóåò â ïîëüçó íå-
ðàçðåøèìîñòè ýòîé ïðîáëåìû.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. P a t e r s o n Ì . Unsolvability in 3 3� matrices // Studies in Appl. Mathemat. — 1970. — 49. — P.
105–107.
2. H a l a v a V . , H a r j i T . Mortality in matrix semigroups. — Turku: Turku Centre of Comput. Sci.,
2000. — Techn. Rep. N 361. — P. 1–8.
3. B o u r n e z Î . , B r a n i c k y Ì . The mortality problem for matrices of low dimensions // Theory
Comput. Systems. — 2002. — 35. — P. 433–448.
4. B l o n d e l V . , T s i t s i k l i s J . When is a pair of matrices mortal? // Inform. Process. Letters. —
1997. — 63. — P. 283–286.
5. Ð û ñ ö î â È . Ê . Ïðåäñòàâëåíèå ðåãóëÿðíûõ èäåàëîâ â êîíå÷íûõ àâòîìàòàõ // Êèáåðíåòèêà è
ñèñòåìíûé àíàëèç. — 2003. — ¹ 5. — Ñ. 48–58.
6. Ð û ñ ö î â È . Ê . Ìèíèìàëüíûå íóëåâûå ñëîâà äëÿ ìàòðèö âòîðîãî ïîðÿäêà // Òàì æå. — 2007.
— ¹ 4. — Ñ. 10–18.
7. S c h u l t z P . Mortality of 2 2� matrices // American Mathemat. Monthly. — 1977. — 84, N 2. —
P. 463–464.
8. Ï à ï à ä è ì è ò ð è ó Õ . Ñ ò à é ã ë è ö Ê . Êîìáèíàòîðíàÿ îïòèìèçàöèÿ. — Ì.: Ìèð, 1985. —
510 ñ.
9. Ñ õ ð å é â å ð À . Òåîðèÿ ëèíåéíîãî è öåëî÷èñëåííîãî ïðîãðàììèðîâàíèÿ. Ò.1. — Ì.: Ìèð,
1991. — 360 ñ.
10. Ã è ë ë À . Ëèíåéíûå ïîñëåäîâàòåëüíîñòíûå ìàøèíû. — Ì.: Íàóêà, 1974. — 287 ñ.
11. Í è â å ð ã å ë ü ò Þ . , Ô à ð ð à ð Ä æ . , Ð å é í ã î ë ü ä Ý . Ìàøèííûé ïîäõîä ê ðåøåíèþ ìà-
òåìàòè÷åñêèõ çàäà÷. — Ì.: Ìèð, 1977. — 351 ñ.
Ïîñòóïèëà 02.08.2007
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2 29
|
| id | nasplib_isofts_kiev_ua-123456789-71995 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| language | Russian |
| last_indexed | 2025-12-07T15:23:04Z |
| publishDate | 2008 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Рысцов, И.К. 2014-12-15T22:06:33Z 2014-12-15T22:06:33Z 2008 Проблема мортальности и аффинные автоматы / И.К. Рысцов // Кибернетика и системный анализ. — 2008. — № 2. — С. 24-29. — Бібліогр.: 11 назв. — рос. https://nasplib.isofts.kiev.ua/handle/123456789/71995 519.713.4 Проблему мортальності для матриць другого порядку розглянуто з точки зору теорії автоматів. Показано, що ця проблема тісно пов'язана з проблемою досягнення станів у лінійних та афінних автоматах малої розмірності. Доведено, що проблема досягнення є алгоритмічно розв'язуваною для деяких підкласів одновимірних афінних автоматів. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Проблема мортальности и аффинные автоматы Article published earlier |
| spellingShingle | Проблема мортальности и аффинные автоматы Рысцов, И.К. Кибернетика |
| title | Проблема мортальности и аффинные автоматы |
| title_full | Проблема мортальности и аффинные автоматы |
| title_fullStr | Проблема мортальности и аффинные автоматы |
| title_full_unstemmed | Проблема мортальности и аффинные автоматы |
| title_short | Проблема мортальности и аффинные автоматы |
| title_sort | проблема мортальности и аффинные автоматы |
| topic | Кибернетика |
| topic_facet | Кибернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/71995 |
| work_keys_str_mv | AT ryscovik problemamortalʹnostiiaffinnyeavtomaty |