Анализ структуры класса линейных автоматов над кольцом Zpk
Встановлено базові скінченно-автоматні характеристики для класу усіх лінійних автоматів над кільцем Zpk і тих, що не втрачають інформації. Досліджено складність розв'язку задач параметричної ідентифікації й ідентифікації початкового стану. Охарактеризовано множину нерухомих точок відповідних с...
Saved in:
| Date: | 2008 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2008
|
| Series: | Кибернетика и системный анализ |
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/72068 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Анализ структуры класса линейных автоматов над кольцом Zpk /В.В. Скобелев // Кибернетика и системный анализ. — 2008. — № 3. — С. 60-74. — Бібліогр.: 15 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-72068 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-720682025-02-23T18:27:16Z Анализ структуры класса линейных автоматов над кольцом Zpk Скобелев, В.В. Кибернетика Встановлено базові скінченно-автоматні характеристики для класу усіх лінійних автоматів над кільцем Zpk і тих, що не втрачають інформації. Досліджено складність розв'язку задач параметричної ідентифікації й ідентифікації початкового стану. Охарактеризовано множину нерухомих точок відповідних словникових функцій, які реалізуються ініціальними автоматами. Побудовано канонічні форми лінійних автоматів над кільцем Zpk. 2008 Article Анализ структуры класса линейных автоматов над кольцом Zpk /В.В. Скобелев // Кибернетика и системный анализ. — 2008. — № 3. — С. 60-74. — Бібліогр.: 15 назв. — рос. https://nasplib.isofts.kiev.ua/handle/123456789/72068 510.5+681.3 ru Кибернетика и системный анализ application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Кибернетика Кибернетика |
| spellingShingle |
Кибернетика Кибернетика Скобелев, В.В. Анализ структуры класса линейных автоматов над кольцом Zpk Кибернетика и системный анализ |
| description |
Встановлено базові скінченно-автоматні характеристики для класу усіх лінійних автоматів над кільцем Zpk і тих, що не втрачають інформації. Досліджено складність розв'язку задач параметричної ідентифікації й ідентифікації початкового стану. Охарактеризовано множину нерухомих точок відповідних словникових функцій, які реалізуються ініціальними автоматами. Побудовано канонічні форми лінійних автоматів над кільцем Zpk. |
| format |
Article |
| author |
Скобелев, В.В. |
| author_facet |
Скобелев, В.В. |
| author_sort |
Скобелев, В.В. |
| title |
Анализ структуры класса линейных автоматов над кольцом Zpk |
| title_short |
Анализ структуры класса линейных автоматов над кольцом Zpk |
| title_full |
Анализ структуры класса линейных автоматов над кольцом Zpk |
| title_fullStr |
Анализ структуры класса линейных автоматов над кольцом Zpk |
| title_full_unstemmed |
Анализ структуры класса линейных автоматов над кольцом Zpk |
| title_sort |
анализ структуры класса линейных автоматов над кольцом zpk |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2008 |
| topic_facet |
Кибернетика |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/72068 |
| citation_txt |
Анализ структуры класса линейных автоматов над кольцом Zpk /В.В. Скобелев // Кибернетика и системный анализ. — 2008. — № 3. — С. 60-74. — Бібліогр.: 15 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT skobelevvv analizstrukturyklassalinejnyhavtomatovnadkolʹcomzpk |
| first_indexed |
2025-11-24T10:50:21Z |
| last_indexed |
2025-11-24T10:50:21Z |
| _version_ |
1849668582795902976 |
| fulltext |
ÓÄÊ 510.5+681.3
Â.Â. ÑÊÎÁÅËÅÂ
ÀÍÀËÈÇ ÑÒÐÓÊÒÓÐÛ ÊËÀÑÑÀ ËÈÍÅÉÍÛÕ ÀÂÒÎÌÀÒÎÂ
ÍÀÄ ÊÎËÜÖÎÌ Z
p
k
Êëþ÷åâûå ñëîâà: ëèíåéíûå àâòîìàòû, êîíå÷íûå êîëüöà, ýêâèâàëåíòíîñòü
ñîñòîÿíèé, ïàðàìåòðè÷åñêàÿ èäåíòèôèêàöèÿ, èäåíòèôèêàöèÿ íà÷àëüíîãî ñî-
ñòîÿíèÿ, íåïîäâèæíûå òî÷êè, êàíîíè÷åñêèå ïðåäñòàâëåíèÿ.
ÂÂÅÄÅÍÈÅ
 íàñòîÿùåå âðåìÿ ïðè ðåøåíèè çàäà÷ ïðåîáðàçîâàíèÿ èíôîðìàöèè îñóùå-
ñòâëÿåòñÿ ñèñòåìàòè÷åñêèé ïåðåõîä îò ÷èñòî êîìáèíàòîðíûõ êîíñòðóêöèé ê
êîíñòðóêöèÿì, ïîñòðîåííûì íà îñíîâå êîíå÷íûõ àëãåáðàè÷åñêèõ ñèñòåì.
 ÷àñòíîñòè, ôðàãìåíòû òåîðèè êîíå÷íûõ ïîëåé ïðèñóòñòâóþò ïðàêòè÷åñêè âî
âñåõ ñîâðåìåííûõ ñòàíäàðòàõ øèôðîâàíèÿ [1–4]. Áîëåå òîãî, ïðàêòè÷åñêè âñå
ñõåìû ïîòî÷íîãî øèôðîâàíèÿ, ïðåäñòàâëåííûå â ðåàëèçóåìûõ â íàñòîÿùåå
âðåìÿ åâðîïåéñêîì (NESSIE) è ÿïîíñêîì (CRYPTREC) ïðîåêòàõ, îñíîâàíû íà
èñïîëüçîâàíèè àâòîìàòîâ íàä ïîëåì GF( )2k ( , )k �16 32 .
Èçâåñòíî, ÷òî ïîëå — ñïåöèàëüíûé ñëó÷àé êîëüöà, ïðè÷åì ïîñëåäíåå ñîäåð-
æèò äåëèòåëè íóëÿ, ïîýòîìó îñîáûé èíòåðåñ ïðåäñòàâëÿåò èññëåäîâàíèå êëàññîâ
àâòîìàòîâ íàä êîíå÷íûì êîëüöîì [5]. Ïðîñòåéøèì òàêèì êëàññîì ÿâëÿþòñÿ ëè-
íåéíûå àâòîìàòû, ïðåäñòàâëÿþùèå ñîáîé åñòåñòâåííîå îáîáùåíèå ëèíåéíûõ àâ-
òîìàòîâ íàä êîíå÷íûì ïîëåì [6]. Áîëåå òîãî, èç-çà íàëè÷èÿ â êîëüöå äåëèòåëåé
íóëÿ ïðîèñõîäèò ïåðåõîä îò ñòðóêòóðû âåêòîðíîãî ïðîñòðàíñòâà ê ìîäóëþ ëè-
íåéíûõ ôîðì íàä êîíå÷íûì êîëüöîì [7]. Ïî-âèäèìîìó, ïî ýòîé ïðè÷èíå ñâî-
éñòâà ëèíåéíûõ àâòîìàòîâ íàä êîíå÷íûì êîëüöîì äî ñèõ ïîð ñèñòåìàòè÷åñêè íå
èññëåäîâàíû. Ñ òî÷êè çðåíèÿ çàäà÷ ïðåîáðàçîâàíèÿ èíôîðìàöèè âàæíûì ïîä-
êëàññîì ëþáîãî êëàññà àâòîìàòîâ ÿâëÿþòñÿ ÁÏÈ-àâòîìàòû [8–10], ò.å. àâòîìàòû,
îñóùåñòâëÿþùèå ïðè êàæäîì ôèêñèðîâàííîì íà÷àëüíîì ñîñòîÿíèè âçàèìíî îä-
íîçíà÷íîå ïðåîáðàçîâàíèå âõîäíîé ïîëóãðóïïû â âûõîäíóþ. Ïîýòîìó àêòóàëüíà
çàäà÷à èññëåäîâàíèÿ ñòðóêòóðû êëàññà ëèíåéíûõ àâòîìàòîâ íàä êîíå÷íûì
êîëüöîì è õàðàêòåðèñòèêà ñâîéñòâ ëèíåéíûõ ÁÏÈ-àâòîìàòîâ.
Îñíîâíàÿ öåëü äàííîé ðàáîòû — èññëåäîâàíèå ñâîéñòâ êëàññà ëèíåéíûõ àâ-
òîìàòîâ íàä êîëüöîì Z
pk . Â ðàçä. 1 ââåäåíû îñíîâíûå ïîíÿòèÿ è îïðåäåëåíèÿ. Â
ðàçä. 2 èññëåäîâàíû îñíîâíûå êîíå÷íî-àâòîìàòíûå õàðàêòåðèñòèêè, â ðàçä. 3 ðå-
øåíà çàäà÷à ïàðàìåòðè÷åñêîé èäåíòèôèêàöèè è èäåíòèôèêàöèè íà÷àëüíîãî ñî-
ñòîÿíèÿ, â ðàçä. 4 îõàðàêòåðèçîâàíû íåïîäâèæíûå òî÷êè, â ðàçä. 5 ïîñòðîåíû êà-
íîíè÷åñêèå ôîðìû àâòîìàòîâ Ìèëè è Ìóðà íàä êîëüöîì Z
pk . Çàêëþ÷åíèå
ñîäåðæèò ðÿä âûâîäîâ.
1. ÎÑÍÎÂÍÛÅ ÏÎÍßÒÈß È ÎÏÐÅÄÅËÅÍÈß
Çàôèêñèðóåì êîëüöî Z Z
p pk k� � �( , , ) ( p — ïðîñòîå ÷èñëî, à îïåðàöèè � è �
îïðåäåëåíû ðàâåíñòâàìè a b a b pk� � � ( )mod è a b a b pk� � � ( )mod ). Ýëåìåíò
a
pk�Z ÿâëÿåòñÿ îáðàòèìûì â êîëüöå Z
pk òîãäà è òîëüêî òîãäà, êîãäà
a p� / ( )0 mod (ñì., íàïðèìåð, [11]). Ïóñòü Mn è Mn
inv — ìíîæåñòâî ñîîòâå-
òñòâåííî âñåõ è âñåõ îáðàòèìûõ ( )n n -ìàòðèö íàä êîëüöîì Z
pk . ßñíî, ÷òî
60 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3
© Â.Â. Ñêîáåëåâ, 2008
| |Mn
k np� � 2
. Â [11] ïîêàçàíî, ÷òî
n p p pn n
n n
inv n n
n! ( ) | | | | ( ) | |
� �
1 1
2
M M M ( )1
è èñòèííû ñëåäóþùèå ñâîéñòâà ñèñòåìû ëèíåéíûõ óðàâíåíèé
A x b A x bn
p
n
k
� � � �( ; , )M Z (2)
íàä êîëüöîì Z
pk :
1) åñëè A n
inv�M , òî ñèñòåìà (2) èìååò åäèíñòâåííîå ðåøåíèå;
2) åñëè A n
inv�M M\ è det ( )A � 0, òî ñèñòåìà (2) ñîâìåñòíàÿ òîãäà è òîëüêî
òîãäà, êîãäà det det( ) . . . ( )A An1 0� � � , ãäå A i ni ( , . . . , )�1 — ìàòðèöà, ïîëó÷åí-
íàÿ èç ìàòðèöû A çàìåíîé i-ãî ñòîëáöà âåêòîðîì b;
3) åñëè A n
inv�M M\ è det ( )A � 0, òî ñèñòåìà (2) ñîâìåñòíàÿ òîãäà è òîëüêî
òîãäà, êîãäà âûïîëíåíû óñëîâèÿ det mod det( ) ( ) & ( )A p Ai
r
i�
�0
�
�0 1( )mod pr ( , . . . , )i n�1 , ãäå r îïðåäåëÿåòñÿ óñëîâèåì det ( )A �
� � �0 0 1( ) & ( ) / ( )mod det modp A pr r , ïðè÷åì ÷èñëî ðåøåíèé ñèñòåìû (2) íå
ìåíüøå, ÷åì pn r� .
Îáúåêòàìè èññëåäîâàíèÿ íàñòîÿùåé ðàáîòû ÿâëÿþòñÿ èíèöèàëüíûå àâòîìà-
òû Ìèëè è Ìóðà [12, 13] ñîîòâåòñòâåííî:
( , ) : ( )M
A B x
y C D x
t
t t t
t t t
1 0
1 1
1 1
q
q q
q
Z
� �
� �
�
� � � �
� � � �
�
�
�
�
��
,
( )3
( , ) : ( )M
A B x
y C
t
t t t
t t
2 0
1 1
1 1
q
q q
q
Z
� �
� �
�
� � � �
� �
�
�
�
�
��
,
( )4
ãäå A B C D, , , — ( )n n -ìàòðèöû íàä êîëüöîì Z
pk , à q Zt t t
p
nx y
k
, , � — âåê-
òîð-ñòîëáöû, ïðåäñòàâëÿþùèå ñîñòîÿíèå àâòîìàòà, âõîäíîé è âûõîäíîé ñèìâîë â
ìîìåíò t. Ïóñòü An, 1 — ìíîæåñòâî âñåõ àâòîìàòîâ M1, îïðåäåëÿåìûõ ôîðìóëîé
(3), à An, 2 — ìíîæåñòâî âñåõ àâòîìàòîâ M 2 , îïðåäåëÿåìûõ (4).
Àâòîìàòû M1 è M 2 — ÁÏÈ-àâòîìàòû òîãäà è òîëüêî òîãäà, êîãäà îáðàòèìû
ìàòðèöû D è B C, ñîîòâåòñòâåííî. Ïðè ýòîì îáðàòíûå àâòîìàòû èìåþò âèä
( , ) : (M
A B x
y C D x
t
t t t
t t t
1
1
0
1 1 1 1
1 1 1 1
� �
� �
� � � �
� � � �
�q
q q
q
Z�
�
�
�
��
),
ãäå A A B D C1
1� � �
O , B B D1
1� �
, C D C1
1� �
O , D D1
1�
è
( , ) : ( )M
B x
y C D x
t
t t
t t t
2
1
0
1 1 1
1 1 1
� �
� �
�
� �
� � � �
�
�
�
�
��
q
q
q
Z ,
ãäå B C1
1�
, C A1 � O , D B C1
1 1� �
. Ïóñòü A n i
inv i, ( , )�1 2 — ìíîæåñòâî
âñåõ îáðàòèìûõ àâòîìàòîâ M i n i�A , .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3 61
2. ÊÎÍÅ×ÍÎ-ÀÂÒÎÌÀÒÍÛÅ ÕÀÐÀÊÒÅÐÈÑÒÈÊÈ
Îöåíêè ÷èñëà îáðàòèìûõ àâòîìàòîâ M ii n i
inv� �A , ( , )1 2 óñòàíàâëèâàåò ñëåäóþ-
ùàÿ ôîðìóëèðîâêà
Òåîðåìà 1. Äëÿ âñåõ n�N
( ! ( ) ) | | | | ( ) | | (, , ,n p p p in n i
n i n i
inv n n i
n i
� �
�1 1
2
A A A �1 2, ) . ( )5
Äîêàçàòåëüñòâî. Òàê êàê äëÿ àâòîìàòà M ii n i� �A , ( , )1 2 âûáîð ìàòðèö èç
ìíîæåñòâà Mn îñóùåñòâëÿåòñÿ íåçàâèñèìî, òî
| | | |,A Mn n1
4� , (6)
| | | |,A Mn n2
3� . (7)
Äëÿ àâòîìàòà M
n
inv
1 1
�A
,
îñóùåñòâëÿåòñÿ íåçàâèñèìûé âûáîð ìàòðèö
A B C n, , �M è D n
inv�M , à äëÿ àâòîìàòà M
n
inv
2 2
�A
,
— íåçàâèñèìûé âûáîð ìàò-
ðèö A n�M è B C n
inv, �M . Ñëåäîâàòåëüíî,
| | | | | |
,
A M M
n
inv
n n
inv
1
3� , (8)
| | | | | |
,
A M M
n
inv
n n
inv
2
2� . (9)
Ïîäñòàâèâ (1) â (8) è (9) è âîñïîëüçîâàâøèñü ðàâåíñòâàìè (6) è (7), ïîëó÷èì (5).
Òåîðåìà äîêàçàíà.
Ïîëîæèì v in i
inv
n i
inv
n i, , ,| | | | ( , )� � �
A A 1 1 2 . Èç òåîðåìû 1 âûòåêàåò ñëåäóþ-
ùèé ðåçóëüòàò.
Ñëåäñòâèå. Äëÿ âñåõ n�N
( ! ( ) ) ( ) ( , ),n p p v p in n i
n i
inv n n i
� �
�
�1 1 1 2
2
.
Ïóñòü Dn
( )1 — ìíîæåñòâî âñåõ äèàãîíàëüíûõ ( )n n -ìàòðèö íàä êîëüöîì
Z
pk , íà ãëàâíîé äèàãîíàëè êîòîðûõ ðàñïîëîæåíû îáðàòèìûå ýëåìåíòû êîëüöà Z
pk .
Ïîëîæèì B A D
n
inv
n
inv
nM D
, ,
( )|
1 1 1
1� � �{ } è B A
n
inv
n
invM B C
, ,
| ,
2 2 2
� � �{ Dn
( )1 }.
Òåîðåìà 2. Äëÿ âñåõ n�N
| | (( ) ) | | ( , ),
( )
,B An i
inv n k k n n i
n i
invp p i�
�
� �1 1 21 . (10)
Äîêàçàòåëüñòâî. Äëÿ àâòîìàòà M
n
inv
1 1
�B
,
îñóùåñòâëÿåòñÿ íåçàâèñèìûé âû-
áîð ìàòðèö A B C n, , �M è D n�D( )1 , à äëÿ àâòîìàòà M
n
inv
2 2
�B
,
— íåçàâèñèìûé
âûáîð ìàòðèö A n�M è B C n, ( )�D 1 . Ñëåäîâàòåëüíî,
| | | | | | |
,
( )B M D
n
inv
n n1
3 1� , (11)
| | | | | |
,
( )B M D
n
inv
n n2
1 2� . (12)
×èñëî îáðàòèìûõ ýëåìåíòîâ êîëüöà Z
pk ðàâíî ( )p pk
1 1. Äëÿ ìàòðèöû
X n�D( )1 âûáîð äèàãîíàëüíûõ ýëåìåíòîâ îñóùåñòâëÿåòñÿ íåçàâèñèìî. Ñëåäîâà-
òåëüíî,
| | ( ) ( ) | |( ) ( ) ( )D Mn
n k n n k n k n
np p p p1 1 11 1
2
�
�
� . ( )13
62 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3
Ïîäñòàâèâ (13) â (11) è (12) è âîñïîëüçîâàâøèñü ðàâåíñòâàìè (6) è (7), ïîëó-
÷èì (10).
Òåîðåìà äîêàçàíà.
Îõàðàêòåðèçóåì àâòîìàò M ii n i� �A , ( , )1 2 â òåðìèíàõ òåîðèè àâòîìàòîâ [13].
Ïóñòü G in i, ( , )�1 2 — ìíîæåñòâî âñåõ àâòîìàòîâ M i n i�A , , ó êîòîðûõ
ãðàô ïåðåõîäîâ — ïîëíûé ãðàô ñ ïåòëÿìè è G G in i
inv
n i n i
inv
, , , ( , )� � �A 1 2 .
Òåîðåìà 3. Äëÿ âñåõ n�N
G
n
inv
n
inv
, ,2 2
� A , (14)
(( !) ( ) ) | | | | ( ) | |, , ,n p p G pn n
n n
inv n n
n
� �
1 1
2 2
1 1
2
1A A . ( )15
Äîêàçàòåëüñòâî. Äëÿ äîêàçàòåëüñòâà òåîðåìû íàì ïîíàäîáèòñÿ ñëåäóþùåå
óòâåðæäåíèå.
Óòâåðæäåíèå 1. Ïóñòü n�N. Ãðàô ïåðåõîäîâ àâòîìàòà M ii n i� �A , ( , )1 2
— ïîëíûé ãðàô ñ ïåòëÿìè òîãäà è òîëüêî òîãäà, êîãäà ìàòðèöà B îáðàòèìàÿ.
Äîêàçàòåëüñòâî. Ïóñòü B — îáðàòèìàÿ ìàòðèöà. Òîãäà äëÿ ëþáûõ ôèêñèðî-
âàííûõ ñîñòîÿíèé q q Z, � �
p
n
k
àâòîìàòà M i n i�A , ( , )i �1 2 è äëÿ ëþáîãî âõîäíîãî
ñèìâîëà x
p
n
k
�Z
q q q q q q� � � � � � � � � � � � � � �
A B x B x A x B A� �1 ( ).
Ñëåäîâàòåëüíî, â àâòîìàòå M ii n i� �A , ( , )1 2 ïåðåõîä èç ëþáîãî ñîñòîÿíèÿ
q Z�
p
n
k
â ëþáîå ñîñòîÿíèå q Z� �
p
n
k
îñóùåñòâëÿåòñÿ çà îäèí òàêò. Îòñþäà ñëåäó-
åò, ÷òî ãðàô ïåðåõîäîâ àâòîìàòà M i (i �1 2, ) — ïîëíûé ãðàô ñ ïåòëÿìè.
Ïóñòü B — íåîáðàòèìàÿ ìàòðèöà. Ïðåäïîëîæèì, ÷òî ãðàô ïåðåõîäîâ àâòî-
ìàòà M ii n i� �A , ( , )1 2 — ïîëíûé ãðàô ñ ïåòëÿìè. Òîãäà äëÿ ëþáîãî ñîñòîÿíèÿ
q Z�
p
n
k
è ëþáûõ âõîäíûõ ñèìâîëîâ x x x x
p
n
k1 2 1 2, ( )� �Z
B x A B x A B x x� � � � � � � � � �1 1 1 2 0q q ( )� .
Òàê êàê B — íåîáðàòèìàÿ ìàòðèöà, òî ñèñòåìà óðàâíåíèé B u� � 0 ñîâìåñòíàÿ è
èìååò ðåøåíèå u0 0� . Ïîëîæèì x x u2 1 0� � . Òîãäà x x1 2� , íî
B x x� �( )1 2 0� . Ïîëó÷åíî ïðîòèâîðå÷èå. Ñëåäîâàòåëüíî, ïðåäïîëîæåíèå ëîæ-
íîå. Îòñþäà âûòåêàåò, ÷òî åñëè B — íåîáðàòèìàÿ ìàòðèöà, òî ãðàô ïåðåõîäîâ
àâòîìàòà M ii n i� �A , ( , )1 2 íå ÿâëÿåòñÿ ïîëíûì ãðàôîì ñ ïåòëÿìè.
Óòâåðæäåíèå äîêàçàíî.
Ïî îïðåäåëåíèþ äëÿ ëþáîãî àâòîìàòà M
n
inv
2 2
� A
,
ìàòðèöà B îáðàòèìàÿ.
Ñëåäîâàòåëüíî, G
n
inv
n
inv
, ,2 2
� A , ÷òî è òðåáîâàëîñü ïîêàçàòü.
Äëÿ àâòîìàòà M G
n
inv
1 1
�
,
îñóùåñòâëÿåòñÿ íåçàâèñèìûé âûáîð ìàòðèö
A C n, �M è B D n
inv, �M . Ñëåäîâàòåëüíî,
| | | | | |
,
G
n
inv
n n
inv
1
2 2� M M . (16)
Ïîäñòàâèâ (1) â (16) è âîñïîëüçîâàâøèñü ðàâåíñòâîì (6), ïîëó÷èì (15).
Òåîðåìà äîêàçàíà.
Ïóñòü Ñn i i, ( , )�1 2 — ìíîæåñòâî âñåõ ïåðåñòàíîâî÷íûõ àâòîìàòîâ
M i n i� A , è C C An i
inv
n i n i
inv i, , , ( , )� � �1 2 .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3 63
Òåîðåìà 4. Äëÿ âñåõ n � 2
| | ( ! ( ) ) | | ( , ), ,C An i
inv n n i
n in p p i�
�
�1 1 2
2 1 . ( )17
Äîêàçàòåëüñòâî.Äëÿ äîêàçàòåëüñòâà òåîðåìû íàì ïîíàäîáèòñÿ ñëåäóþùåå
óòâåðæäåíèå.
Óòâåðæäåíèå 2.Åñëè äëÿ àâòîìàòà M ii n i� �A , ( , )1 2 ìàòðèöà A îáðàòè-
ìàÿ, òî M — ïåðåñòàíîâî÷íûé àâòîìàò.
Äîêàçàòåëüñòâî. Ïóñòü A — îáðàòèìàÿ ìàòðèöà. Ïðåäïîëîæèì ïðîòèâíîå,
ò.å. ÷òî àâòîìàò M ii n i� �A , ( , )1 2 íå ÿâëÿåòñÿ ïåðåñòàíîâî÷íûì. Òîãäà ñóùå-
ñòâóþò òàêèå ñîñòîÿíèÿ q q Z q q, ( )� � � �
p
n
k
è âõîäíîé ñèìâîë x
p
n
k
�Z , ÷òî
A B x A B x A A A� � � � � � � � � � � � � � � � �q q q q q q( )� 0.
Òàê êàê A — îáðàòèìàÿ ìàòðèöà, òî A � � � � � � �( )q q q q� �0 0 q q� � . Ïî-
ëó÷åíî ïðîòèâîðå÷èå. Ñëåäîâàòåëüíî, ïðåäïîëîæåíèå ëîæíîå. Îòñþäà âûòåêà-
åò, ÷òî åñëè A — îáðàòèìàÿ ìàòðèöà, òî M ii ( , )�1 2 — ïåðåñòàíîâî÷íûé
àâòîìàò.
Óòâåðæäåíèå äîêàçàíî.
Äëÿ àâòîìàòà M
n
inv
1 1
� C
,
îñóùåñòâëÿåòñÿ íåçàâèñèìûé âûáîð ìàòðèö
B C n, , �M è A D n
inv, �M , à äëÿ àâòîìàòà M
n
inv
2 2
� C
,
— íåçàâèñèìûé âûáîð ìàò-
ðèö A B C n
inv, , �M . Ñëåäîâàòåëüíî,
| | | | | |
,
C M M
n
inv
n n
inv
1
2 2� , (18)
| | | |
,
C M
n
inv
n
inv
2
3� . (19)
Ïîäñòàâèâ (1) â (18) è (19) è âîñïîëüçîâàâøèñü ðàâåíñòâàìè (6) è (7), ïîëó-
÷èì (17).
Òåîðåìà äîêàçàíà.
Ïóñòü Dn i i, ( , )�1 2 — ìíîæåñòâî âñåõ ïðèâåäåííûõ àâòîìàòîâ M Ai n i� , è
D D An i
inv
n i n i
inv i, , , ( , )� � �1 2 .
Òåîðåìà 5. Äëÿ âñåõ n � 2
| | ( ! ( ) ) | | ( , ), ,D An i
inv n n i
n in p p i�
�
�1 1 2
2 1 . ( )20
Äîêàçàòåëüñòâî. Äëÿ äîêàçàòåëüñòâà òåîðåìû íàì ïîíàäîáÿòñÿ ñëåäóþùèå
äâà óòâåðæäåíèÿ.
Óòâåðæäåíèå 3. Åñëè äëÿ àâòîìàòà M n1 1� A , ìàòðèöà C îáðàòèìàÿ, òî M1
— ïðèâåäåííûé àâòîìàò, ñòåïåíü ðàçëè÷èìîñòè êîòîðîãî ðàâíà 1.
Äîêàçàòåëüñòâî. Ïóñòü C — îáðàòèìàÿ ìàòðèöà. Ïðåäïîëîæèì ïðîòèâíîå,
ò.å. ÷òî àâòîìàò M n1 1� A , íå ÿâëÿåòñÿ ïðèâåäåííûì èëè åãî ñòåïåíü ðàçëè÷è-
ìîñòè íå ðàâíà 1. Òîãäà ñóùåñòâóþò òàêèå ñîñòîÿíèÿ q q Z q q, ( )� � � �
p
n
k
, ÷òî äëÿ
âñåõ x
p
n
k
�Z
C D x C D x C C C� � � � � � � � � � � � � � � � �q q q q q q( )� 0.
Òàê êàê C — îáðàòèìàÿ ìàòðèöà, òî C � � � � � �( )q q q q� �0 0 � � �q q.
Ïîëó÷åíî ïðîòèâîðå÷èå. Ñëåäîâàòåëüíî, ïðåäïîëîæåíèå ëîæíîå. Îòñþäà âûòå-
64 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3
êàåò, ÷òî åñëè C — îáðàòèìàÿ ìàòðèöà, òî M1 — ïðèâåäåííûé àâòîìàò, ñòåïåíü
ðàçëè÷èìîñòè êîòîðîãî ðàâíà 1.
Óòâåðæäåíèå äîêàçàíî.
Óòâåðæäåíèå 4. Åñëè äëÿ àâòîìàòà M n2 2� A , ìàòðèöû A è C îáðàòèìûå,
òî M 2 — ïðèâåäåííûé àâòîìàò, ñòåïåíü ðàçëè÷èìîñòè êîòîðîãî ðàâíà 1.
Äîêàçàòåëüñòâî. Ïóñòü A è C — îáðàòèìûå ìàòðèöû. Ïðåäïîëîæèì ïðî-
òèâíîå, ò.å. ÷òî àâòîìàò M n2 2� A , íå ÿâëÿåòñÿ ïðèâåäåííûì èëè åãî ñòåïåíü
ðàçëè÷èìîñòè íå ðàâíà 1. Òîãäà ñóùåñòâóþò òàêèå ñîñòîÿíèÿ q q Z q q, ( )� � � �
p
n
k
,
÷òî äëÿ âñåõ x
p
n
k
�Z
C A B x C A B x C A� � � � � � � � � � � � � � �( ) ( ) ( )q q q qO 0.
Òàê êàê A è C — îáðàòèìûå ìàòðèöû, òî C A� — îáðàòèìàÿ ìàòðèöà. Ñëåäî-
âàòåëüíî, C A� � � � � � � � � �( )q q q q q qO O0 0 . Ïîëó÷åíî ïðîòèâîðå÷èå.
Çíà÷èò, ïðåäïîëîæåíèå ëîæíîå. Îòñþäà âûòåêàåò, ÷òî M 2 — ïðèâåäåííûé
àâòîìàò, ñòåïåíü ðàçëè÷èìîñòè êîòîðîãî ðàâíà 1.
Óòâåðæäåíèå äîêàçàíî.
Äëÿ àâòîìàòà M
n
inv
1 1
� D
,
îñóùåñòâèì íåçàâèñèìûé âûáîð ìàòðèö A B n, �M
è C D n
inv, �M , à äëÿ àâòîìàòà M
n
inv
2 2
� D
,
— íåçàâèñèìûé âûáîð ìàòðèö
A B C n
inv, , �M . Ñëåäîâàòåëüíî,
| | | | | |
,
D M M
n
inv
n n
inv
1
2 2� , (21)
| | | |
,
D M
n
inv
n
inv
2
3� . (22)
Ïîäñòàâèâ (1) â (21) è (22) è âîñïîëüçîâàâøèñü ðàâåíñòâàìè (6) è (7), ïîëó-
÷èì (20).
Òåîðåìà äîêàçàíà.
Ïóñòü E in i, ( , )�1 2 — ìíîæåñòâî âñåõ àâòîìàòîâ M i n i� A , , èìåþùèõ ñî-
ñòîÿíèÿ-áëèçíåöû [14] è E E in i
inv
n i n i
inv
, , , ( , )� � �A 1 2 .
Òåîðåìà 6. Äëÿ âñåõ n � 2
| | ! ( ) ( ( ) ) | |
, ,E n p p p
n
inv n n n n
n1
2
11 1 1
2
�
A , ( )23
| | ( ( ) ( ! ( ) | |
, ,E p n p p
n
inv n n n n
n2 21 1 1
2
�
A . ( )24
Äîêàçàòåëüñòâî. Äëÿ äîêàçàòåëüñòâà òåîðåìû íàì ïîíàäîáÿòñÿ ñëåäóþùèå
óòâåðæäåíèÿ.
Óòâåðæäåíèå 5.Åñëè äëÿ àâòîìàòà M n1 1� A , ìàòðèöû A è C íåîáðàòèìûå
è ñèñòåìà óðàâíåíèé
A u
C u
� �
� �
�
�
�
0
0
,
(25)
èìååò íåíóëåâîå ðåøåíèå, òî â M1 ñóùåñòâóþò ñîñòîÿíèÿ-áëèçíåöû.
Äîêàçàòåëüñòâî. Ïóñòü A è C — íåîáðàòèìûå ìàòðèöû. Ñîñòîÿíèÿ
q q Z, � �
p
n
k
( )q q� � àâòîìàòà M n1 1�A , ÿâëÿþòñÿ áëèçíåöàìè òîãäà è òîëüêî òîã-
äà, êîãäà äëÿ ëþáîãî âõîäíîãî ñèìâîëà x
p
n
k
�Z
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3 65
A B x A B x
C D x C D x
A
C
� � � � � � � �
� � � � � � � �
�
� � �
� �
q q
q q
q q
q
( ) ,
(
O
O
0
q) .�
�
�
�
�
�
�
�� 0
( )26
Ïóñòü u0 — íåíóëåâîå ðåøåíèå ñèñòåìû (25). Ïîëîæèì q q� � � u0 . Òîãäà
q q� � è ñîñòîÿíèÿ q q Z, � �
p
n
k
óäîâëåòâîðÿþò óñëîâèþ (26). Ñëåäîâàòåëüíî,
q q Z, � �
p
n
k
— ñîñòîÿíèÿ-áëèçíåöû.
Óòâåðæäåíèå äîêàçàíî.
Óòâåðæäåíèå 6. Åñëè äëÿ àâòîìàòà M n2 2�A , ìàòðèöà A íåîáðàòèìàÿ, òî â
àâòîìàòå M 2 ñóùåñòâóþò ñîñòîÿíèÿ-áëèçíåöû.
Äîêàçàòåëüñòâî. Ïóñòü A — íåîáðàòèìàÿ ìàòðèöà. Ñîñòîÿíèÿ
q q Z q q, ( )� � � �
p
n
k
àâòîìàòà M n2 2�A , ÿâëÿþòñÿ áëèçíåöàìè òîãäà è òîëüêî
òîãäà, êîãäà äëÿ ëþáîãî âõîäíîãî ñèìâîëà x
p
n
k
�Z
A B x A B x
C A B x C A B x
A� � � � � � � �
� � � � � � � � � �
�
� � �q q
q q
q q
( ) ( )
( )O 0
0
0
C A
A
� � � �
� � � �
�
�
�
�
�
� ( )
( )
q q
q q
O
O .
( )27
Òàê êàê A — íåîáðàòèìàÿ ìàòðèöà, òî óðàâíåíèå A u� � 0 âñåãäà èìååò íåíó-
ëåâîå ðåøåíèå u0 . Ïîëîæèì q q� � � u0 . Òîãäà q q Z� � �
p
n
k
è ñîñòîÿíèÿ
q q Z, � �
p
n
k
óäîâëåòâîðÿþò óñëîâèþ (27). Ñëåäîâàòåëüíî, q q Z, � �
p
n
k
—
ñîñòîÿíèÿ-áëèçíåöû.
Óòâåðæäåíèå äîêàçàíî.
Èç (1) âûòåêàåò, ÷òî
( ( ) ) | | | \ | ( ! ( ) )| |1 1 1 1
2
� �
p n p pn n
n n n
inv n n
nM M M M . ( )28
Äëÿ àâòîìàòà M E
n
inv
1 1
�
,
îñóùåñòâèì íåçàâèñèìûé âûáîð ìàòðèö
A C n n
inv, \�M M , B n�M è D n
inv�M , à äëÿ àâòîìàòà M E
n
inv
2 2
�
,
— íåçàâèñèìûé
âûáîð ìàòðèö A n n
inv�M M\ è B C n
inv, �M . Ñëåäîâàòåëüíî,
| | | \ | | | | |
,
E
n
inv
n n
inv
n n
inv
1
2� M M M M , ( )29
| | | \ | | |
,
E
n
inv
n n
inv
n
inv
2
2� M M M . ( )30
Ïîäñòàâèâ (1) è (28) â (29) è (30) è âîñïîëüçîâàâøèñü ðàâåíñòâàìè (6) è (7),
ïîëó÷èì (23) è (24).
Òåîðåìà äîêàçàíà.
Ïóñòü Dn
( )2 — ìíîæåñòâî âñåõ äèàãîíàëüíûõ ( )n n -ìàòðèö íàä êîëüöîì
Z
pk , íà ãëàâíîé äèàãîíàëè êîòîðûõ ðàñïîëîæåíû íåîáðàòèìûå ýëåìåíòû êîëüöà
Z
pk . Ïîëîæèì
F M E A C
n
inv
n
inv
n, ,
( )| ,
1 1 1
2� � �{ }D è F M E A
n
inv
n
inv
n, ,
( )|
2 2 2
2� � �{ }D .
66 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3
Òåîðåìà 7. Äëÿ âñåõ n�N
| | ! ( ) | |
,
( )
,F n p p p
n
inv n n n k k n
n1
2 1
11
2
�
� A , ( )31
| | ( ! ( ) ) | |
,
( )
,F p n p p
n
inv n k k n n n
n2
1 2
21
2
�
�
A . ( )32
Äîêàçàòåëüñòâî. Äëÿ àâòîìàòà M F
n
inv
1 1
�
,
îñóùåñòâèì íåçàâèñèìûé âûáîð
ìàòðèö A C n, ( )�D 2 , B n�M è D n
inv�M , à äëÿ àâòîìàòà M F
n
inv
2 2
�
,
— íåçàâèñè-
ìûé âûáîð ìàòðèö A n�D( )2 è B C n
inv, �M . Ñëåäîâàòåëüíî,
| | | | | | | |
,
( )F
n
inv
n n n
inv
1
2 2� D M M , (33)
| | | | | |
,
( )F
n
inv
n n
inv
2
2 2� D M . (34)
×èñëî íåîáðàòèìûõ ýëåìåíòîâ êîëüöà Z
pk ðàâíî p p pk k
�
( )1 1
�
pk 1. Äëÿ ìàòðèöû X n�D( )2 âûáîð äèàãîíàëüíûõ ýëåìåíòîâ îñóùåñòâëÿåòñÿ
íåçàâèñèìî. Ñëåäîâàòåëüíî,
| | | |( ) ( ) ( )D Mn
k n k n kn
np p2 1 1 2
� �
. ( )35
Ïîäñòàâèâ (1) è (35) â (33) è (34) è âîñïîëüçîâàâøèñü ðàâåíñòâàìè (6) è (7),
ïîëó÷èì (31) è (32).
Òåîðåìà äîêàçàíà.
Èññëåäóåì ýêâèâàëåíòíîñòü àâòîìàòîâ M M ii i n i, ( , ),� � �A 1 2 , ãäå
( , ) : (M
A B x
y C D x
t t t
t t t
1 0
1 1
1 1
�
� � � � � � � �
� � � � � � � �
� �
� �
q
q q
q
t �
�
�
�
�Z ),
(36)
( , ) : ( )M
A B x
y C
t
t t t
t t
2 0
1 1
1 1
�
� � � � � � � �
� � � � �
�
� � �
� �
�q
q q
q
Z�
�
. (37)
Îòìåòèì, ÷òî èíäóêöèåé ïî t íåñëîæíî ïîêàçàòü, ÷òî äëÿ àâòîìàòà
M ii n i� �A , ( , )1 2 èñòèííû ðàâåíñòâà
q q Nt
t
i
t
t i
i tA A B x B x t�
�
�
�
�� � � � � � � � �1
1
0
1
1
1 ( ).
( )38
Òåîðåìà 8. Èíèöèàëüíûå àâòîìàòû ( , )M1 0q è ( , )� �M1 0q ( ,M M1 1� �A n, )1
ýêâèâàëåíòíû òîãäà è òîëüêî òîãäà, êîãäà âûïîëíåíû ñëåäóþùèå óñëîâèÿ: à)
D D� � ; á) C C� � � � �q q0 0 0O ; â) äëÿ ëþáîãî ñîñòîÿíèÿ q Z0 �
p
n
k
ñóùåñòâóåò
òàêîå ñîñòîÿíèå q Z0 � �
p
n
k
è, íàîáîðîò, äëÿ ëþáîãî ñîñòîÿíèÿ q Z0 � �
p
n
k
ñóùåñ-
òâóåò òàêîå ñîñòîÿíèå q Z0 �
p
n
k
,÷òî C A C At t� � � � � � � �( ) q q0 0 0O
( , . . . , )t pkn� �
1 2 2 ; ã) C A Bj� � � � �( ) O O O
� � �C A Bj ( , . . . , )j pkn� �
1 2 3 ;
ä) C B C B� � � � �O O.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3 67
Äîêàçàòåëüñòâî. Îïåðàòîðû, ðåàëèçóåìûå èíèöèàëüíûìè àâòîìàòàìè ( , )M1 0q è
( , )M1 0� �q ðàâíû òîãäà è òîëüêî òîãäà, êîãäà äëÿ ëþáîé âõîäíîé ïîñëåäîâàòåëüíîñòè
x xt1 . . . ( , . . . , )t pkn� �
1 2 1 èñòèííû ðàâåíñòâà y yt t� �.
Ïóñòü t �1. Èç âòîðîãî óðàâíåíèÿ ñèñòåì (3) è (36) âûòåêàåò, ÷òî äëÿ ëþáîãî
âõîäíîãî ñèìâîëà x
p
n
k1 �Z
y y C D x C D x1 1 0 1 0 1� � � � � � � � � � � � � �q q
� � � � � � �
�( )D D x C CO O1 0 0q q . (39)
Òàê êàê äëÿ ôèêñèðîâàííûõ çíà÷åíèé D D C C� � �, , , , ,q q0 0 ðàâåíñòâî (39)
èñòèííî äëÿ âñåõ x
p
n
k1 �Z , òî D D O� �O , ò.å. D D� � . Ñëåäîâàòåëüíî, óñëîâèå à)
âûïîëíåíî. Îòñþäà âûòåêàåò, ÷òî ðàâåíñòâî (39) èìååò âèä C C� � � � �q q0 0 0O ,
ò.å. óñëîâèå á) âûïîëíåíî.
Ïóñòü t pkn� �
2 2 1, . . . , . Èç âòîðîãî óðàâíåíèÿ ñèñòåì (3) è (36) è ðàâåíñòâà
D D� � âûòåêàåò, ÷òî äëÿ ëþáîãî âõîäíîãî ñëîâà x xt
p
nt
k1 . . . �Z
y y C D x C D x C Ct t t t t t t t� � � � � � � � � � � � � � � � � �
q q q q1 1 1 1. (40)
Âîñïîëüçîâàâøèñü â (40) ðàâåíñòâîì (38), ïîëó÷èì
y y C A A B x B xt t
t
i
t
t i
i� � � � � � � � � � � � � � � � �
�
(( ) ( )1
0
1
2
1q t
�1 )
� � � � � � � � � �
�
C A A B x B xt
i
t
t i
i t( )1
0
1
2
1
1q
� � � � � � � � � � � � � �
�
( ( ) ) ( ( )C A C A C At t
i
t
t i1
0
1
0
1
2
1q qO
� � � � � � � � � � � �
B C A B x C B C B xt i
i tO O1
1 0) ( ) . (41)
Ïîëîæèâ x xt
t
1 1
1
0 0. . . . . .
�
���
â (41), ïîëó÷èì C A Ct� � � � � �( ) q0 O
� � �A t q0 0 ( , . . . , )t pkn�
1 2 2 , ò.å. óñëîâèå â) âûïîëíåíî. Ñëåäîâàòåëüíî, ðàâå-
íñòâî (41) ïðèíèìàåò âèä
� � � � � � � � �
�
i
t
t i t iC A B C A B
1
2
1 1( ( ) )O
� � � � � � � �
x C B C B xi t( )O 1 0. (42)
Äëÿ i t�
1 2, . . . , ïîñëåäîâàòåëüíî ïîëîæèì x xt1 1. . .
� 0 0 0 0 0
1 2
. . . . . .
t
i
t i
x
��� ���
â (42). Ïîëó÷èì, ÷òî äëÿ âñåõ i t�
1 2, . . . , ðàâåíñòâî ( ( )C A t i� � � �
1
� � � � � �
B C A B xt i
iO 1 0) èñòèííî ïðè âñåõ xi
p
n
k
�Z . Ñëåäîâàòåëüíî,
C A B C A B j pj j kn� � � � � � � � �
( ) ( , . . . , )O O 1 2 3 , (43)
ò.å. óñëîâèå ã) âûïîëíåíî.
Ïîäñòàâèâ (43) â (42), ïîëó÷èì ÷òî ðàâåíñòâî ( )C B C B� � � � �O � �
xt 1 0 èñòèííî
ïðè âñåõ xt
p
n
k
�1 Z . Ñëåäîâàòåëüíî,C B C B� � �
� �O O, ò.å. óñëîâèå ä) âûïîëíåíî.
68 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3
Òåîðåìà äîêàçàíà.
Òåîðåìà 9. Èíèöèàëüíûå àâòîìàòû ( , )M 2 0q è ( , )M 2 0� �q
( , ),M M n2 2 2� �A ýêâèâàëåíòíû òîãäà è òîëüêî òîãäà, êîãäà âûïîëíåíû ñëåäóþ-
ùèå óñëîâèÿ: à) C B C B� � � � �O O; á) äëÿ ëþáîãî ñîñòîÿíèÿ q Z0 �
p
n
k
ñóùåñ-
òâóåò òàêîå ñîñòîÿíèå q Z0 � �
p
n
k
è, íàîáîðîò, äëÿ ëþáîãî ñîñòîÿíèÿ q Z0 � �
p
n
k
ñó-
ùåñòâóåò òàêîå ñîñòîÿíèå q Z0 �
p
n
k
, ÷òî
C A C A t pt t kn� � � � � � � � �
( ) ( , . . . , )q q0 0 0 1 2 1O ;
â) C A B C A B j pj j kn� � � � � � � � �
( ) ( , . . . , )O O 1 2 2 .
Äîêàçàòåëüñòâî. Îïåðàòîðû, ðåàëèçóåìûå èíèöèàëüíûìè àâòîìàòàìè
( , )M 2 0q è ( , )M 2 0� �q ðàâíû òîãäà è òîëüêî òîãäà, êîãäà äëÿ ëþáîé âõîäíîé ïî-
ñëåäîâàòåëüíîñòè x x t pt
kn
1 1 2 1. . . ( , . . . , )�
èñòèííû ðàâåíñòâà y yt t� �.
Ïóñòü t �1. Èç âòîðîãî óðàâíåíèÿ ñèñòåì (4) è (37) âûòåêàåò, ÷òî äëÿ ëþáîãî
âõîäíîãî ñèìâîëà x
p
n
k1 �Z
y y C C C A B x C A B x1 1 1 1 0 1 0 1� � � � � � � � � � � � � � � � � � � � � �q q q q( ) ( )�
� � � �
� � � � �
� � � � �( )C B C B x C A C AO O1 0 0q q . (44)
Òàê êàê äëÿ ôèêñèðîâàííûõ çíà÷åíèé A A B B C C, , , , , , ,� � � �q q0 0 ðàâåíñòâî
(44) èñòèííî äëÿ âñåõ x
p
n
k1 �Z , òî
C B C B
C A C A
� � �
� �
� �
� � � � � �
�
�
�
O O
O
,
,q q0 0 0
ò.å. âûïîëíåíû óñëîâèÿ à) è á) ïðè t �1.
Ïóñòü t pkn�
2 2 1, . . . , . Èç 2-ãî óðàâíåíèÿ ñèñòåì (4) è (37) âûòåêàåò, ÷òî
äëÿ ëþáîãî âõîäíîãî ñëîâà x xt
p
nt
k1 . . . �Z
y y C Ct t t t� � � � � � � � �q q . (45)
Âîñïîëüçîâàâøèñü â (45) ðàâåíñòâîì (38), ïîëó÷èì
y y C A A B x B xt t
t
i
t
t i
i t� � � � � � � � � � � � � � � � � �
�
(( ) ( ) )q0
1
1
� � � � � � � � � � � � � � � �
�
C A A B x B x C A C At
i
t
t i
i t
t( ) ( ( )q q0
1
1
0 O t � �q0 )
� � � � � � � � � � �
�
i
t
t i t i
iC A B C A B x
1
1
0( ( ) )O . (46)
Ïîëîæèâ x xt
t
1 1
1
0 0. . . . . .
�
���
â (46), ïîëó÷èì C A C At t� � � � � � �( ) q0 O
� �q0 0, ò.å. óñëîâèå â) âûïîëíåíî ïðè t pkn�
2 2 1, . . . , .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3 69
Äëÿ i t�
1 1, . . . , ïîñëåäîâàòåëüíî ïîëîæèì x xt1 1. . .
� �
0 0 0 0 0
1 1
. . . . . .
i
i
t i
x
��� ���
â (46). Ïîëó÷èì, ÷òî äëÿ âñåõ i t�
1 1, . . . , ðàâåíñòâî ( ( )C A t i� � � �
� � � � � �
B C A B xt i
iO ) 0 èñòèííî ïðè âñåõ xi
p
n
k
�Z . Ñëåäîâàòåëüíî,
C A B C A Bj j� � � � � � � �( ) O O ( j pk n� �
�1 2 2, . . . , ), ò.å. óñëîâèå â) âûïîëíåíî.
Òåîðåìà äîêàçàíà.
3. ÇÀÄÀ×È ÈÄÅÍÒÈÔÈÊÀÖÈÈ ÀÂÒÎÌÀÒÀM ii n i� �A , ( , )1 2
Ðàññìîòðèì ðåøåíèå çàäà÷ èäåíòèôèêàöèè àâòîìàòà M ii n i� �A , ( , )1 2 â ïðåä-
ïîëîæåíèè, ÷òî ýêñïåðèìåíòàòîð ïîëíîñòüþ óïðàâëÿåò âõîäîì, à òàêæå ïî-
ëíîñòüþ íàáëþäàåò âûõîä àâòîìàòà M i . Âûáîð òàêèõ ïðåäïîëîæåíèé îáîñíî-
âàí òåì, ÷òî îíè õàðàêòåðèçóþò âíóòðåííþþ ñëîæíîñòü çàäà÷è èäåíòèôèêà-
öèè, òàê êàê ïðè èõ îñëàáëåíèè ñëîæíîñòü ðåøåíèÿ çàäà÷è èäåíòèôèêàöèè
ñóùåñòâåííî âîçðàñòàåò.
Ðàññìîòðèì âíà÷àëå çàäà÷ó ïàðàìåòðè÷åñêîé èäåíòèôèêàöèè àâòîìàòà
M ii n i� �A , ( , )1 2 , ïðåäïîëîæèâ, ÷òî ýêñïåðèìåíòàòîð èìååò âîçìîæíîñòü òàê-
æå óïðàâëÿòü èíèöèàëèçàöèåé àâòîìàòà M i (ò.å. ïðîâîäèòü ñ íèì M i êðàòíûé
ýêñïåðèìåíò òðåáóåìîé êðàòíîñòè).
Òåîðåìà 10. Ïóñòü M n1 1�A , è ýêñïåðèìåíòàòîð ïîëíîñòüþ óïðàâëÿåò âõî-
äîì è èíèöèàëèçàöèåé àâòîìàòà M1, à òàêæå ïîëíîñòüþ íàáëþäàåò âûõîä àâòî-
ìàòà M1. Òîãäà:
1) êàæäàÿ èç ìàòðèö C è D èäåíòèôèöèðóåòñÿ åäèíñòâåííûì îáðàçîì ïîñðå-
äñòâîì n-êðàòíîãî ýêñïåðèìåíòà âûñîòû 1;
2) åñëè C — îáðàòèìàÿ ìàòðèöà, òî èäåíòèôèêàöèÿ êàæäîé èç ìàòðèö A è B
ñâîäèòñÿ ê ðåøåíèþ n ñèñòåì ëèíåéíûõ óðàâíåíèé n-ãî ïîðÿäêà íàä êîëüöîì
Z
pk , ïîñòðîåííûõ â ðåçóëüòàòå n-êðàòíîãî ýêñïåðèìåíòà âûñîòû 2.
Äîêàçàòåëüñòâî. Ïóñòü M n1 1�A , è ýêñïåðèìåíòàòîð ïîëíîñòüþ óïðàâëÿåò
âõîäîì è èíèöèàëèçàöèåé àâòîìàòà M1, à òàêæå ïîëíîñòüþ íàáëþäàåò åãî âûõîä.
Ïîëîæèì q 0 0� è x ei1 � ( , , )i n�1 � , ãäå ei
i n i
T�
( , ..., , , , )0 01 0 0
1
���
�
���
. Èç âòîðîãî
óðàâíåíèÿ ñèñòåìû (3) íàõîäèì, ÷òî y D ei1 � � . Òàê êàê D ei� ( , . . . , )i n�1 — i-é
ñòîëáåö ìàòðèöû D, òî ìàòðèöà D èäåíòèôèöèðóåòñÿ â ðåçóëüòàòå ñëåäóþùåãî
n-êðàòíîãî ýêñïåðèìåíòà âûñîòû 1: { }( , ) | , . . . ,q x e i ni0 10 1� � � , ÷òî è
òðåáîâàëîñü ïîêàçàòü.
Ïîëîæèì q ei0 � ( , . . . , )i n�1 x1 0� . Èç âòîðîãî óðàâíåíèÿ ñèñòåìû (3) íàõî-
äèì, ÷òî y C ei1 � � . Òàê êàê C ei� ( , . . . , )i n�1 — i-é ñòîëáåö ìàòðèöû C, òî ìàò-
ðèöà C èäåíòèôèöèðóåòñÿ â ðåçóëüòàòå ñëåäóþùåãî n-êðàòíîãî ýêñïåðèìåíòà âû-
ñîòû 1: { }( , ) | , . . . ,q0 1 0 1� � �e x i ni , ÷òî è òðåáîâàëîñü ïîêàçàòü.
Ïóñòü C — îáðàòèìàÿ ìàòðèöà íàä êîëüöîì Z
pk .
Ïîëîæèì q0 � ei ( , . . . , )i n�1 è x1 0� . Èç ïåðâîãî óðàâíåíèÿ ñèñòåìû (3) íàõî-
äèì, ÷òî q1 � �A ei . Ïîëîæèâ òåïåðü x2 0� , ïîëó÷èì y C2 � �. Òàê êàê A ei�
� ( )A e C y A ei i� � � � �
1
2 (i n�1, . . . , ) — i-é ñòîëáåö ìàòðèöû A, òî èäåíòèôè-
êàöèÿ ìàòðèöû A ñâîäèòñÿ ê ðåøåíèþ n ñèñòåì ëèíåéíûõ óðàâíåíèé n-ãî ïîðÿäêà íàä
êîëüöîì Z
pk , ïîñòðîåííûõ â ðåçóëüòàòå n-êðàòíîãî ýêñïåðèìåíòà âûñîòû 2:
{( , ) |q e x xi0 1 2 00� � i n�1, . . . , }, ÷òî è òðåáîâàëîñü ïîêàçàòü.
Ïîëîæèì q0 0� è x ei1 � ( , . . . , )i n�1 . Èç ïåðâîãî óðàâíåíèÿ ñèñòåìû (3) íà-
õîäèì, ÷òî q1 � �B ei . Ïîëîæèâ òåïåðü x2 0� , ïîëó÷èì
y C B e C y B ei i2
1
2� � � � � � �
( ) .
70 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3
Ïîñêîëüêó B ei� (i n�1, . . . , ) — i-é ñòîëáåö ìàòðèöû B, òî èäåíòèôèêàöèÿ ìàò-
ðèöû B ñâîäèòñÿ ê ðåøåíèþ n ñèñòåì ëèíåéíûõ óðàâíåíèé n-ãî ïîðÿäêà íàä êîëü-
öîì Z
pk , ïîñòðîåííûõ â ðåçóëüòàòå n-êðàòíîãî ýêñïåðèìåíòà âûñîòû 2:
{ }( , ) | , . . . ,q0 1 20 0 1� � �x x e i ni , ÷òî è òðåáîâàëîñü ïîêàçàòü.
Òåîðåìà äîêàçàíà.
Ñ ïîìîùüþ ðàâåíñòâà (38) ïðåäñòàâèì ñèñòåìó (3) â âèäå
y C A q A B x B x D x ii
i
j
i
i j
j i i�
�
� �� � � � � � � � � � � �1 0
1
1
1( ) ( )Z , ( )47
à ñèñòåìó (4) — â âèäå
y C A A B x B x ii
i
j
i
i j
j i�
�
�
� � �� � � � � � � � � �1
1
0
0
1
1 1( ) ( )q Z . ( )48
Ïóñòü â àâòîìàòå M n1 1�A , ìàòðèöà C íåîáðàòèìàÿ. Èç (47) âûòåêàåò, ÷òî
èäåíòèôèêàöèÿ ìàòðèö A è B ñâîäèòñÿ ê ðåøåíèþ ïðè èçâåñòíûõ ìàòðèöàõ C è
D ñèñòåì íåëèíåéíûõ óðàâíåíèé
C A q A B x B x y D xi
j
i
i j
j i i i� � � � � � � � � �
�
� �( )0
1
1
1 1O (49)
äëÿ âñåõ q
p
n
k0 �Z è x xi
p
n i
k1 1. . . �
��Z (i pn k�
�1 1, . . . , ).
Ðåøåíèå çàäà÷è ïàðàìåòðè÷åñêîé èäåíòèôèêàöèè àâòîìàòà M n2 2�A , çíà-
÷èòåëüíî ñëîæíåå, òàê êàê â ñèëó (48) ýòà çàäà÷à ñâîäèòñÿ ê ðåøåíèþ îòíîñè-
òåëüíî ìàòðèö A B C, , ñèñòåìû íåëèíåéíûõ óðàâíåíèé
C A A B x B x y i pi
j
i
i j
j i i� � � � � � � � � ��
�
� � �( ) ( , ,1
0
0
1
1 1 1 1q �
n k�
1)
( )50
äëÿ âñåõ q Z0 �
p
n
k
è x xi
p
n k
k1 1. . . �
��Z (i pn k�
�1 1, . . . , ).
Ðàññìîòðèì òåïåðü ðåøåíèå çàäà÷è èäåíòèôèêàöèè íà÷àëüíîãî ñîñòîÿíèÿ
àâòîìàòà M i n i�A , (i �1 2, ).
Ïóñòü M n1 1�A , . Ïîëîæèâ t � 0 â (3), ïîëó÷èì C y D x� � �q0 1 1O . Ñëåäî-
âàòåëüíî, åñëè C — îáðàòèìàÿ ìàòðèöà, òî èäåíòèôèêàöèÿ íà÷àëüíîãî ñîñòîÿíèÿ
q0 àâòîìàòà M n1 1�A , îñóùåñòâëÿåòñÿ ïðîñòûì ýêñïåðèìåíòîì äëèíû 1. Åñëè
æå C — íåîáðàòèìàÿ ìàòðèöà, òî èäåíòèôèêàöèÿ íà÷àëüíîãî ñîñòîÿíèÿ q0 àâòî-
ìàòà M n1 1�A , ñâîäèòñÿ ê ðåøåíèþ ïðè èçâåñòíûõ ìàòðèöàõ A B C D, , , ñèñòåì
ëèíåéíûõ óðàâíåíèé (49) äëÿ âñåõ x xi1 1. . . � � Z
p
n i
k
� �( )1
(i pn k�
�1 1, . . . , ).
Ïóñòü M n2 2�A , . Ïîëîæèâ t � 0 â (4) , ïîëó÷èì C A q� � �0
� � �y C B x1 1O . Ñëåäîâàòåëüíî, åñëè A C, — îáðàòèìûå ìàòðèöû, òî èäåíòè-
ôèêàöèÿ íà÷àëüíîãî ñîñòîÿíèÿ q0 àâòîìàòà M n2 2�A , îñóùåñòâëÿåòñÿ ïðîñòûì
ýêñïåðèìåíòîì äëèíû 1. Åñëè æå õîòÿ áû îäíà èç ìàòðèö A C, íåîáðàòèìàÿ, òî
èäåíòèôèêàöèÿ íà÷àëüíîãî ñîñòîÿíèÿ q0 àâòîìàòà M n2 2�A , ñâîäèòñÿ ê ðåøå-
íèþ ïðè èçâåñòíûõ ìàòðèöàõ A B C, , ñèñòåì ëèíåéíûõ óðàâíåíèé (50) äëÿ âñåõ
x xi
p
n i
k1 1
1
� �
� ��Z ( ) (i pn k�
�1 1, ,� ).
4. ÍÅÏÎÄÂÈÆÍÛÅ ÒÎ×ÊÈ ÀÂÒÎÌÀÒÀM i n i�A , (i � 1 2, )
Íåïîäâèæíîé òî÷êîé ñëîâàðíîé ôóíêöèè f X X: � �� íàçûâàåòñÿ òàêàÿ ïî-
ñëåäîâàòåëüíîñòü u X� � , ÷òî f u u( ) � . Îõàðàêòåðèçóåì íåïîäâèæíûå òî÷êè
èíèöèàëüíîãî àâòîìàòà ( , )M i q0 , ãäå M i n i�A , (i �1 2, ).
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3 71
Ïóñòü M n1 1�A , . Íåïîäâèæíîé òî÷êîé èíèöèàëüíîãî àâòîìàòà ( , )M1 0q ÿâ-
ëÿåòñÿ ëþáîå âõîäíîå ñëîâî x xi
p
n i
k1 . . . � �Z (i�N), óäîâëåòâîðÿþùåå ñëåäóþùåé
ñèñòåìå ðåêóððåíòíûõ ñîîòíîøåíèé:
( ) ,
( ) (
I D x C q
I D x C A A B xt
t
j
t
t j
j
O
O
� � �
� � � � � � � ��
�
1 0
1 0
1
1
q � � �
�
�
�
�
� B x t it ) ( , , ).1 1�
Îòñþäà âûòåêàåò, ÷òî èíèöèàëüíûé àâòîìàò ( , )M1 0q èìååò íåïîäâèæíóþ
òî÷êó òîãäà è òîëüêî òîãäà, êîãäà ñóùåñòâóåò òàêîé âõîäíîé ñèìâîë x
p
n
k1 �Z ,
÷òî èñòèííî ðàâåíñòâî
( )I D x CO � � �1 0q . (51)
Èç (51) ñëåäóåò, ÷òî íåïîäâèæíîé òî÷êîé àâòîìàòà ( , )M1 0 âñåãäà ÿâëÿåòñÿ
âõîäíîé ñèìâîë x1 0� .
Ïóñòü q0 0� . Ïîëîæèâ â (51) x a1 0� � q (a � 0), ïîëó÷èì
(( ) )I D a CO O� � �q0 0. (52)
Èç (52) âûòåêàåò, ÷òî åñëè ñóùåñòâóåò òàêîé ýëåìåíò a
pk�Z (a � 0), ÷òî
ìàòðèöà ( )I D a CO O� íåîáðàòèìàÿ, òî èíèöèàëüíûé àâòîìàò ( , )M1 0q ( )q0 0�
èìååò íåïîäâèæíûå òî÷êè x1 0� .
Ïóñòü M n2 2�A , . Íåïîäâèæíîé òî÷êîé èíèöèàëüíîãî àâòîìàòà ( , )M 2 0q
ÿâëÿåòñÿ ëþáîå âõîäíîå ñëîâî x xi
p
n i
k1 . . . � �Z ( )i�N , óäîâëåòâîðÿþùåå ñëåäóþ-
ùåé ñèñòåìå ðåêóððåíòíûõ ñîîòíîøåíèé:
( ) ,
( ) (
I C B x C A q
I C B x C A A At
t
j
t
O
O
� � � � �
� � � � � � � ��
�
1 0
1 0
1
1
q t j
j tB x B x t i
� � � � �
�
�
�
�
� ) ( , , ).1 1�
Îòñþäà ïîëó÷àåì, ÷òî èíèöèàëüíûé àâòîìàò ( , )M 2 0q èìååò íåïîäâèæíóþ
òî÷êó òîãäà è òîëüêî òîãäà, êîãäà ñóùåñòâóåò òàêîé âõîäíîé ñèìâîë x
p
n
k1 �Z ,
÷òî èñòèííî ðàâåíñòâî
( )I C B x C AO � � � � �1 0q . (53)
Èç (53) âûòåêàåò, ÷òî íåïîäâèæíîé òî÷êîé àâòîìàòà ( , )M 2 0 âñåãäà ÿâëÿåòñÿ
âõîäíîé ñèìâîë x1 0� .
Ïóñòü q0 0� (a � 0). Ïîëîæèâ â (53) x a1 0� � q (a � 0), ïîëó÷èì
(( ) )I C B a C AO O� � � � �q0 0. (54)
Èç (54) âûòåêàåò, ÷òî åñëè ñóùåñòâóåò òàêîé ýëåìåíò a
pk�Z (a � 0), ÷òî
ìàòðèöà ( )I C B a C AO O� � � íåîáðàòèìàÿ, òî èíèöèàëüíûé àâòîìàò ( , )M 2 0q
( )q0 0� èìååò íåïîäâèæíûå òî÷êè x1 0� .
5. ÊÀÍÎÍÈ×ÅÑÊÀß ÔÎÐÌÀ ÀÂÒÎÌÀÒÀ M i n i�A , (i � 1 2, )
Èçâåñòíî, ÷òî ìíîæåñòâî Z
p
n
k
ïðåäñòàâëÿåò ñîáîé Z
p
n
k
-ìîäóëü ëèíåéíûõ ôîðì
[7]. Ñëåäîâàòåëüíî, êàæäîå ëèíåéíîå ïðåîáðàçîâàíèå Z
p
n
k
â Z
p
n
k
, èíûìè ñëî-
âàìè, êàæäóþ ìàòðèöó H n�M ñ ïîìîùüþ ýëåìåíòàðíûõ îïåðàöèé (ò.å. óìíî-
æåíèÿ ñëåâà è ñïðàâà íà ñîîòâåòñòâóþùèå ìàòðèöû G F n
inv, �M ) ìîæíî ïðåä-
ñòàâèòü â âèäå
72 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3
G H F
U O
O V
r h
h r
� � �
�
�
�
�
�
�
�
�
,
,
, (55)
ãäå U r�D( )1 , V
h
�D( )2 , à Or h, — íóëåâàÿ ( )r h -ìàòðèöà. Ïóñòü Dn
( ), ( )1 2 —
ìíîæåñòâî âñåõ ìàòðèö âèäà (55). Îòìåòèì, ÷òî ëþáàÿ ìàòðèöà X n�D( ), ( )1 2
îñóùåñòâëÿåò óìíîæåíèå êîìïîíåíò âåêòîðà z
p
n
k
�Z íà ñîîòâåòñòâóþùèå ýëå-
ìåíòû êîëüöà Z
p
n
k
, à ìíîæåñòâî Mn
inv — ãðóïïà, èçîìîðôíàÿ ïîäãðóïïå ñèì-
ìåòðè÷åñêîé ãðóïïû S
pk n� .
Áóäåì ãîâîðèòü, ÷òî àâòîìàò ( , )M q0 (M n n� A A, ,1 2 ) ïðåäñòàâëåí â êà-
íîíè÷åñêîé ôîðìå, åñëè âñå âûïîëíÿåìûå â åãî ïðåäñòàâëåíèè ëèíåéíûå ïðåîá-
ðàçîâàíèÿ — ýëåìåíòû ìíîæåñòâ Dn
( ), ( )1 2 è Mn
inv . Êàíîíè÷åñêèå ôîðìû àâòîìà-
òîâ ( , )M1 0q ( ),M n1 1�A è ( , )M 2 0q ( ),M n�A 2 èìåþò ñîîòâåòñòâåííî
ñëåäóþùèé âèä:
( , ):
( ) (
M
F R X F R X F xt t t
1 0
1
1
1 1 1 1
1
2 2 2
1
1
q
q q
�
�� � � � � � � � � )
( ) ( )
( )
G y X R F R X F x
t
t t t3 1 3 3 1
1
4 4 4
1
1� � � � � � � � �
�
�
�
�
�
�
q
Z�
��
,
( , ):
( ) (
M
F R X F R X F xt t t
2 0
1
1
1 1 1 1
1
2 2 2
1
1
q
q q
�
�� � � � � � � � � )
( )
( )
G y X R F
t
t t3 1 3 3 1
1
1� � � � �
�
�
�
�
�� �
�
�
q
Z ,
ãäå X i n�D( ), ( )1 2 ( , . . . , )i �1 4 , G Ri i n
inv, �M ( , . . . , )i �1 4 , ïðè÷åì X 1 �
� � �G A F1 1, X G B F2 2 2� � � , X G C F3 3 3� � � , X G D F4 2 2� � � ,
R F1 1
1� �
G
1
1
, R F G2 1
1
2
1� �
, R F F3 3
1
1� �
, R G G4 3 4
1� �
.
Åñëè M i n i
inv�A , ( , )i �1 2 , òî êàíîíè÷åñêèå ôîðìû èìåþò áîëåå ïðîñòîé âèä,
à èìåííî:
( , ):
( ) (
M
F R X F R X F xt t t
1 0
1
1
1 1 1 1
1
2 2 2
1
1
q
q q
�
�� � � � � � � � � )
( )
( )
G y X R F Y x
t
t t t3 1 3 3 1
1
1 1� � � � � � �
�
�
�
�
�� �
�
�
q
Z ,
( , ) :
( )
(
M
F R X F Y x
y Y
t t t
t
2 0
1
1
1 1 1 1
1
2 1
1 3
q
q q
�
�
�
� � � � � � �
� � F
t
t1
1
1
�
�
�
�
�
�
�
�� q
Z
)
( ),
ãäå Y G D n
inv
1 3� � �M , Y F B n
inv
2 1
1� � �
M è Y C n
inv
1 � �M .
ÇÀÊËÞ×ÅÍÈÅ
 íàñòîÿùåé ðàáîòå óñòàíîâëåíû îñíîâíûå êîíå÷íî-àâòîìàòíûå õàðàêòåðèñòè-
êè ëèíåéíûõ àâòîìàòîâ Ìèëè è Ìóðà íàä êîëüöîì Z
pk . Âûäåëåíû è îõà-
ðàêòåðèçîâàíû êëàññû ëèíåéíûõ ÁÏÈ-àâòîìàòîâ íàä êîëüöîì Z
pk . Íàéäåíû
óñëîâèÿ, ïðè êîòîðûõ ñóùåñòâóþò ýôôåêòèâíûå àëãîðèòìû ðåøåíèÿ çàäà÷ ïà-
ðàìåòðè÷åñêîé èäåíòèôèêàöèè, à òàêæå èäåíòèôèêàöèè íà÷àëüíîãî ñîñòîÿíèÿ
èññëåäóåìûõ àâòîìàòîâ. Ïîêàçàíî, ÷òî â êëàññå âñåõ ëèíåéíûõ àâòîìàòîâ íàä
êîëüöîì Z
pk ýòè çàäà÷è ñâîäÿòñÿ ê ðåøåíèþ ñèñòåì íåëèíåéíûõ óðàâíåíèé.
Ñëîæíîñòü ðåøåíèÿ ýòèõ ñèñòåì óðàâíåíèé è îïðåäåëÿåò âíóòðåííþþ ñëîæíîñòü
ðåøåíèÿ çàäà÷ èäåíòèôèêàöèè â êëàññå ëèíåéíûõ àâòîìàòîâ íàä êîëüöîì Z
pk .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3 73
Îõàðàêòåðèçîâàíû íåïîäâèæíûå òî÷êè ñëîâàðíûõ ôóíêöèé, ðåàëèçóåìûõ èíè-
öèàëüíûìè ëèíåéíûìè àâòîìàòàìè íàä êîëüöîì Z
pk . Äåòàëüíàÿ õàðàêòåðèñòèêà
ìíîæåñòâ íåïîäâèæíûõ òî÷åê äëÿ ñëîâàðíûõ ôóíêöèé, ðåàëèçóåìûõ èíèöèàëüíû-
ìè ëèíåéíûìè ÁÏÈ-àâòîìàòàìè íàä êîëüöîì Z
pk , ïðåäñòàâëÿåò ñîáîé îäíî èç âîç-
ìîæíûõ íàïðàâëåíèé áóäóùèõ èññëåäîâàíèé. Ýòî íàïðàâëåíèå àêòóàëüíî ïðè èñ-
ñëåäîâàíèè âîçìîæíîñòåé ïðèìåíåíèÿ ëèíåéíûõ ÁÏÈ-àâòîìàòîâ íàä êîëüöîì Z
pk
äëÿ ðåøåíèÿ çàäà÷ çàùèòû èíôîðìàöèè.
Ïîñòðîåíû êàíîíè÷åñêèå ôîðìû ëèíåéíûõ àâòîìàòîâ íàä êîëüöîì Z
pk . Îíè
õàðàêòåðèçóþòñÿ òåì, ÷òî âñå âûïîëíÿåìûå â åãî ïðåäñòàâëåíèè ëèíåéíûå ïðå-
îáðàçîâàíèÿ — ýëåìåíòû ìíîæåñòâ Dn
( ), ( )1 2 è Mn
inv . Çíà÷åíèå òàêèõ ôîðì ñîñòîèò
â ñëåäóþùåì. Ïðè ëîãàðèôìè÷åñêîì âåñå [15] åìêîñòíàÿ ñëîæíîñòü ýëåìåíòà
z
p
n
k
�Z ðàâíà ! "nk plog , à åìêîñòíàÿ ñëîæíîñòü ïåðåñòàíîâêè ìíîæåñòâà Z
p
n
k
,
ïðåäñòàâëåííîé ìàòðèöåé X n
inv�M , ðàâíà ! "n k p2 log . Íàçîâåì ïåðåñòàíîâêó
ìíîæåñòâà Z
p
n
k
ëåãêî âû÷èñëèìîé, åñëè ïðè ëîãàðèôìè÷åñêîì âåñå åå ðåàëèçóåò
àëãîðèòì, åìêîñòíàÿ è âðåìåííàÿ ñëîæíîñòü êîòîðîãî ðàâíà ! "O nk p( )log .
Èçó÷åíèå ñòðóêòóðû ìíîæåñòâà ëåãêî âû÷èñëèìûõ ïåðåñòàíîâîê ìíîæåñòâà Z
p
n
k
— âòîðîå âîçìîæíîå íàïðàâëåíèå áóäóùèõ èññëåäîâàíèé. Ýòî íàïðàâëåíèå òàê-
æå àêòóàëüíî ïðè èññëåäîâàíèè âîçìîæíîñòåé ïðèìåíåíèÿ ëèíåéíûõ
ÁÏÈ-àâòîìàòîâ íàä êîëüöîì Z
pk äëÿ ðåøåíèÿ çàäà÷ çàùèòû èíôîðìàöèè.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. À ë ô å ð î â À . Ï . Îñíîâû êðèïòîãðàôèè. — Ì.: Ãåëèîñ ÀÐÂ, 2002. — 480 ñ.
2. Á à á è ÷ å â Ñ . à . Îñíîâû ñîâðåìåííîé êðèïòîãðàôèè. — Ì.: Ãîðÿ÷àÿ ëèíèÿ — Òåëåêîì,
2002. — 175 ñ.
3. Ø í à é å ð Á . Ïðèêëàäíàÿ êðèïòîãðàôèÿ. Ïðîòîêîëû, àëãîðèòìû, èñõîäíûå òåêñòû íà ÿçûêå
ÑÈ. — Ì.: ÒÐÈÓÌÔ, 2003. — 816 ñ.
4. Õ à ð è í Þ . Ñ . Ìàòåìàòè÷åñêèå è êîìïüþòåðíûå îñíîâû êðèïòîëîãèè. — Ìèíñê: Íîâîå
çíàíèå, 2003. — 382 ñ.
5. Ñ ê î á å ë å â  . à . Íåëèíåéíûå àâòîìàòû íàä êîíå÷íûì êîëüöîì // Êèáåðíåòèêà è
ñèñòåìíûé àíàëèç. — 2006. — ¹ 6. — Ñ. 29–42.
6. Ã è ë ë À . Ëèíåéíûå ïîñëåäîâàòåëüíîñòíûå ìàøèíû. — Ì.: Íàóêà, 1974. — 298 ñ.
7. Á . À . â à í ä å ð Â à ð ä å í . Àëãåáðà. — Ì.: Íàóêà, 1979. — 634 ñ.
8. E v e n S . On information-lossless automata of finite order // IEEE Trans. on Elect. Comput. —
1965. — C-14. — N 4. — P. 561–569.
9. H u f f m a n D . A . Canonical forms for information-lossless finite state logical machines // IRE
Trans. Circuit Theory. Special Supplement. — 1959. — CT-6. — P. 41–59.
10. Ê ó ð ì è ò À . À . Àâòîìàòû áåç ïîòåðè èíôîðìàöèè êîíå÷íîãî ïîðÿäêà. — Ðèãà: Çèíàòíå,
1972. — 266 ñ.
11. Ñ ê î á å ë å â Â . Â . Îá îáðàòèìûõ ìàòðèöàõ íàä êîëüöîì Z
p
n
k // Òð. ÈÏÌÌ ÍÀÍ Óêðàèíû.
— 13. — 2006. — Ñ. 185–192.
12. Ã ë ó ø ê î â Â . Ì . Ñèíòåç öèôðîâûõ àâòîìàòîâ. — Ì.: Ôèçìàòëèò, 1962. — 476 ñ.
13. Ò ð à õ ò å í á ð î ò À . À . , Á à ð ç ä è í ü ß . Ì . Êîíå÷íûå àâòîìàòû (ïîâåäåíèå è ñèíòåç).
— Ì.: Íàóêà, 1970. — 400 ñ.
14. Ê î ð ø ó í î â À . Ä . Î ïåðå÷èñëåíèè êîíå÷íûõ àâòîìàòîâ // Ïðîáëåìû êèáåðíåòèêè. —
1978. — Âûï. 34. — Ñ. 5–82.
15. À õ î À . , Õ î ï ê ð î ô ò Ä æ . , Ó ë ü ì à í Ä æ . Ïîñòðîåíèå è àíàëèç âû÷èñëèòåëüíûõ
àëãîðèòìîâ. — Ì.: Ìèð, 1979. — 536 ñ.
Ïîñòóïèëà 04.04.2007
74 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3
|