О некоторых множествах автоматов над конечным кольцом
Досліджено множини автоматів Мілі та Мура над довільним комутативно-асоціативним кільцем, у яких функції переходів та функції реакцій є лінійними комбінаціями функцій стану автомата та функцій вхідного символу. Охарактеризовано підмножини сильнозв’язаних автоматів, автоматів, у яких функція переході...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2011 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2011
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/84182 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | О некоторых множествах автоматов над конечным кольцом / В.Г. Скобелев // Кибернетика и системный анализ. — 2011. — Т. 47, № 2. — С. 27-30. — Бібліогр.: 7 назв. — рос.. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860264566874701824 |
|---|---|
| author | Скобелев, В.Г. |
| author_facet | Скобелев, В.Г. |
| citation_txt | О некоторых множествах автоматов над конечным кольцом / В.Г. Скобелев // Кибернетика и системный анализ. — 2011. — Т. 47, № 2. — С. 27-30. — Бібліогр.: 7 назв. — рос.. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Досліджено множини автоматів Мілі та Мура над довільним комутативно-асоціативним кільцем, у яких функції переходів та функції реакцій є лінійними комбінаціями функцій стану автомата та функцій вхідного символу. Охарактеризовано підмножини сильнозв’язаних автоматів, автоматів, у яких функція переходів є переставленням, приведених автоматів та оборотних автоматів.
Sets of Mealy and Moore automata over an arbitrary finite commutative-associative ring with transition and output functions being linear combinations of any function of state of an automaton with any function of its input are investigated. Subsets of strongly connected, with permutation transition function, permutation reduced, and reversible automata are characterized.
|
| first_indexed | 2025-12-07T18:59:12Z |
| format | Article |
| fulltext |
ÓÄÊ 512.552+519.713
Â.Ã. ÑÊÎÁÅËÅÂ
Î ÍÅÊÎÒÎÐÛÕ ÌÍÎÆÅÑÒÂÀÕ ÀÂÒÎÌÀÒÎÂ
ÍÀÄ ÊÎÍÅ×ÍÛÌ ÊÎËÜÖÎÌ
Êëþ÷åâûå ñëîâà: êîíå÷íûå àâòîìàòû, êîíå÷íûå êîëüöà, ñèììåòðè÷íûå ïîòî÷-
íûå øèôðû.
ÂÂÅÄÅÍÈÅ
Ïåðåõîä â êðèïòîãðàôèè îò ÷èñòî êîìáèíàòîðíûõ ìîäåëåé ê êîìáèíàòîðíî-àëãåá-
ðàè÷åñêèì ìîäåëÿì [1, 2] ñòèìóëèðîâàë èññëåäîâàíèå àâòîìàòîâ, ïðåäñòàâëåííûõ
óðàâíåíèÿìè íàä êîíå÷íûìè êîëüöàìè.  ðàáîòàõ [3, 4] îõàðàêòåðèçîâàíû àâòîíîì-
íûå àâòîìàòû, â [5] — àâòîìàòû Ìèëè è Ìóðà íàä êîëüöîì Z
pk (ãäå p — ïðîñòîå
÷èñëî, k � N), â [6] ðàññìîòðåíû ìîäåëè è ìåòîäû, ëåæàùèå â îñíîâå àíàëèçà àâòî-
ìàòîâ íàä êîíå÷íûì êîììóòàòèâíî-àññîöèàòèâíûì êîëüöîì ñ åäèíèöåé [7].
Îõàðàêòåðèçóåì ìíîæåñòâî A1 àâòîìàòîâ Ìèëè M1 è ìíîæåñòâî A2 àâòîìàòîâ
Ìóðà íàä ïðîèçâîëüíûì êîíå÷íûì êîììóòàòèâíî-àññîöèàòèâíûì êîëüöîì
K � � �( , , )K (â äàëüíåéøåì — êîëüöî K), èìåþùèõ ñîîòâåòñòâåííî âèä
M tt t t
t t t
1
1 1 3 1
1 2 4 1
:
( ) ( )
( ) ( )
(
q f q f x
y f q f x
Z� �
� �
� �
� �
�
�
�
� � ), (1)
M tt t t
t t
2
1 1 3 1
1 2 1
:
( ) ( )
( )
( )
q f q f x
y f q
Z� �
� �
�
� �
�
�
�
�
� , (2)
ãäå fi
n nK K: ( , , )i �1 4� , à q x yt t t
nK, , � — ñîîòâåòñòâåííî ñîñòîÿíèå àâ-
òîìàòà, âõîäíîé è âûõîäíîé ñèìâîëû â ìîìåíò t � �Z .
1. ÏÎÄÌÍÎÆÅÑÒÂÀ, ÎÏÐÅÄÅËßÅÌÛÅ ÑÒÐÓÊÒÓÐÎÉ ÀÂÒÎÌÀÒÍÎÃÎ ÃÐÀÔÀ
Ìíîæåñòâî A A1 2
ñîñòîèò èç àâòîìàòîâ, ôóíêöèè ïåðåõîäîâ è âûõîäîâ êîòîðûõ
— ëèíåéíûå êîìáèíàöèè ôóíêöèè ñîñòîÿíèÿ àâòîìàòà è ôóíêöèè âõîäíîãî ñèìâî-
ëà. Òàêîå ñòðîåíèå ýòèõ ôóíêöèé äàåò âîçìîæíîñòü âûÿâèòü ñëåäóþùèå ñâîéñòâà.
Óòâåðæäåíèå 1. Àâòîìàò M �
A A1 2 — ñèëüíîñâÿçíûé àâòîìàò, äèàìåòð àâòîìàò-
íîãî ãðàôà êîòîðîãî ðàâåí åäèíèöå òîãäà è òîëüêî òîãäà, êîãäà f3 :K Kn n — áèåêöèÿ.
Äîêàçàòåëüñòâî. Îòîáðàæåíèå f3 :K Kn n ÿâëÿåòñÿ áèåêöèåé òîãäà è òîëüêî
òîãäà, êîãäà |{ ( ) ( ) | } | | |f q f x x1 3� � �K Kn n äëÿ âñåõ q � K n , ò.å. êîãäà äëÿ ëþáûõ
ñîñòîÿíèé q q, ~ � K n àâòîìàòà M �
A A1 2 ñóùåñòâóåò òàêîé âõîäíîé ñèìâîë
x � K n , ÷òî ~ ( ) ( )q f q f x� �1 3 . Ïîñëåäíåå ðàâåíñòâî ýêâèâàëåíòíî òîìó, ÷òî
M �
A A1 2 — ñèëüíîñâÿçíûé àâòîìàò, äèàìåòð àâòîìàòíîãî ãðàôà êîòîðîãî ðàâåí
åäèíèöå.
Óòâåðæäåíèå äîêàçàíî.
Èç óòâåðæäåíèÿ 1 âûòåêàåò èñòèííîñòü ñëåäóþùèõ äâóõ ñëåäñòâèé.
Ñëåäñòâèå 1. Àâòîìàò M �
A A1 2 ÿâëÿåòñÿ ïåðåñòàíîâî÷íûì àâòîìàòîì
òîëüêî òîãäà, êîãäà f3 : K Kn n — áèåêöèÿ.
Ñëåäñòâèå 2. Åñëè îòîáðàæåíèå f3 : K Kn n íå ÿâëÿåòñÿ áèåêöèåé, òî äèà-
ìåòð àâòîìàòíîãî ãðàôà àâòîìàòà M �
A A1 2 áîëüøå åäèíèöû.
Óòâåðæäåíèå 2. Åñëè f2 : K Kn n — áèåêöèÿ, òî M �A1 ÿâëÿåòñÿ ïðèâåäåí-
íûì àâòîìàòîì, â êîòîðîì ëþáûå äâà ñîñòîÿíèÿ îòëè÷àþòñÿ ìåæäó ñîáîé âõîäíûì
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 2 27
© Â.Ã. Ñêîáåëåâ, 2011
ñèìâîëîì.
Äîêàçàòåëüñòâî. Åñëè f2 : K Kn n — áèåêöèÿ, òî f q f q2 2( ) (~)� äëÿ ëþáûõ
q q, ~ � K n ( ~)q q� . Ñëåäîâàòåëüíî, y f q f x f q f x y� � � � �2 4 2 4( ) ( ) (~) ( ) ~ äëÿ ëþáûõ ñî-
ñòîÿíèé q q, ~ � K n ( ~)q q� àâòîìàòà M �A1 è âõîäíîãî ñèìâîëà x � K n .
Óòâåðæäåíèå äîêàçàíî.
Óòâåðæäåíèå 3. Åñëè f1: K Kn n è f2 : K Kn n — áèåêöèè, òî M �A2 ÿâ-
ëÿåòñÿ ïðèâåäåííûì àâòîìàòîì, â êîòîðîì ëþáûå äâà ñîñòîÿíèÿ îòëè÷àþñÿ ìåæäó
ñîáîé âõîäíûì ñèìâîëîì.
Äîêàçàòåëüñòâî. Ïóñòü f1: K Kn n — áèåêöèÿ. Òîãäà f q f q1 1( ) (~)� äëÿ ëþ-
áûõ q q, ~ � K n ( ~)q q� . Ñëåäîâàòåëüíî, f q f x f q f x1 3 1 3( ) ( ) (~) ( )� � � äëÿ ëþáûõ
q q, ~ � K n ( ~)q q� è x � K n . Åñëè æå f2 : K Kn n — áèåêöèÿ, òî
y f f q f x f f q f x y� � � � �2 1 3 2 1 3( ( ) ( )) ( (~) ( )) ~ äëÿ ëþáûõ ñîñòîÿíèé q q, ~ � K n( ~)q q�
àâòîìàòà M �A2 è âõîäíîãî ñèìâîëà x � K n .
Óòâåðæäåíèå äîêàçàíî.
Äâà ðàçëè÷íûõ ñîñòîÿíèÿ àâòîìàòà íàçûâàþòñÿ áëèçíåöàìè, åñëè ïîä âîçäåé-
ñòâèåì ëþáîãî âõîäíîãî ñèìâîëà îíè ïåðåõîäÿò â îäíî è òî æå ñîñòîÿíèå, à âûäà-
âàåìûå àâòîìàòîì âûõîäíûå ñèìâîëû ñîâïàäàþò.
Óòâåðæäåíèå 4. Ñîñòîÿíèÿ q q, ~ � K n ( ~)q q� àâòîìàòà M �
A A1 2 ÿâëÿþòñÿ
áëèçíåöàìè òîãäà è òîëüêî òîãäà, êîãäà îíè ïðèíàäëåæàò îäíîìó è òîìó æå êëàññó
ðàçáèåíèÿ K n / �, ãäå � � �ker kerf f1 2, åñëè M �A1, è � � ker f1, åñëè M �A2.
Äîêàçàòåëüñòâî. Ñîñòîÿíèÿ q q, ~ � K n ( ~)q q� àâòîìàòà M �A1 ÿâëÿþòñÿ áëèç-
íåöàìè òîãäà è òîëüêî òîãäà, êîãäà f q f q1 1( ) (~)� è f q f q2 2( ) (~)� , ò.å. êîãäà
q q f f
�~( )ker ker1 2 . Ïîñëåäíåå îçíà÷àåò, ÷òî ñîñòîÿíèÿ q q, ~ � K n ( ~)q q� ïðèíàä-
ëåæàò îäíîìó è òîìó æå êëàññó ðàçáèåíèÿ K n / ( )ker kerf f1 2� .
Ñîñòîÿíèÿ q q, ~ � K n ( ~)q q� àâòîìàòà M �A2 ÿâëÿþòñÿ áëèçíåöàìè òîãäà è
òîëüêî òîãäà, êîãäà f q f q1 1( ) (~)� , ò.å. êîãäà q q f
~( )ker 1 . Ïîñëåäíåå îçíà÷àåò, ÷òî
ñîñòîÿíèÿ q q, ~ � K n ( ~)q q� ïðèíàäëåæàò îäíîìó è òîìó æå êëàññó ðàçáèåíèÿ
K n / ker f1.
Óòâåðæäåíèå äîêàçàíî.
2. ÏÎÄÌÍÎÆÅÑÒÂÀ ÎÁÐÀÒÈÌÛÕ ÀÂÒÎÌÀÒÎÂ
Äëÿ êðèïòîãðàôèè ïðåäñòàâëÿþò èíòåðåñ ïîäìíîæåñòâà Ai
inv ( , )i �1 2 òàêèõ àâòîìà-
òîâ M i i�A , êîãäà ïðè êàæäîì íà÷àëüíîì ñîñòîÿíèè q 0 � K n áèåêöèåé ÿâëÿåòñÿ àâ-
òîìàòíîå îòîáðàæåíèå F q( , ) : ( ) ( )M
n nK K
0
� � , ðåàëèçóåìîå èíèöèàëüíûì àâòî-
ìàòîì ( , )M i q 0 . Òàêèå àâòîìàòû îïðåäåëÿþò êëàññ ïîòî÷íûõ øèôðîâ, äëÿ êîòîðûõ
íà÷àëüíîå ñîñòîÿíèå q 0 � K n ÿâëÿåòñÿ ñåêðåòíûì ñåàíñîâûì êëþ÷oì.
Òåîðåìà 1. Äëÿ ëþáûõ îòîáðàæåíèé f i
n nK K: ( , , )i �1 2 3 èñòèííî ðàâåíñòâî
A A
1 1 1 4
inv n nM K K� � { | :f — áèåêöèÿ}. (3)
Äîêàçàòåëüñòâî. Ïóñòü M1 1�A — òàêîé àâòîìàò, ÷òî f4 : K Kn n ÿâëÿåòñÿ
áèåêöèåé. Èç âòîðîãî óðàâíåíèÿ ñèñòåìû (1) íàõîäèì
x f y f qt t t�
�
�� �1 4
1
1 2( ( )). (4)
Ïîäñòàâèâ (4) â ïåðâîå óðàâíåíèå ñèñòåìû (1), ïîëó÷èì
28 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 2
q f q f f y f qt t t t�
�
�� � �1 1 3 4
1
1 2( ) ( ( ( ))). (5)
Çàìåíèâ â (4) è (5) x íà y , a y íà x , ïîëó÷èì òàêîé àâòîìàò
M
t t t t
t t
1
1 1 1 3 4
1
1 2
1 4
1
� �
�
�
�
�
� � �
�
:
( ) ( ( ( )))
(
q f q f f x f q
y f x �
�
�
�
�
�
��
�
1 2f q
Z
( ))
( )
t
t , (6)
êîãäà ïðè êàæäîì íà÷àëüíîì ñîñòîÿíèè q 0 � K n èíèöèàëüíûé àâòîìàò ( , )M1
1
0
� q
ðåàëèçóåò îòîáðàæåíèå F
q( , )M1 0
1� , ò.å. ïðè êàæäîì íà÷àëüíîì ñîñòîÿíèè q 0 � K n îòî-
áðàæåíèå F q( , )M1 0
ÿâëÿåòñÿ áèåêöèåé. Ñëåäîâàòåëüíî, M
inv
1 1�A .
Ïóñòü M �A1 — òàêîé àâòîìàò, ïðè êîòîðîì îòîáðàæåíèå f4 : K Kn n íå ÿâ-
ëÿåòñÿ áèåêöèåé. Òîãäà ñóùåñòâóþò òàêèå âõîäíûå ñèìâîëû x x f1 1 4, ~ � ker , ÷òî
x x1 1� ~ . Ïîñêîëüêó f x f x4 1 4 1( ) (~ )� , òî y f q f x f q f x y1 2 0 4 1 2 0 4 1 1� � � � �( ) ( ) ( ) (~ ) ~
äëÿ âñåõ q 0 � K n , ò.å. ïðè êàæäîì íà÷àëüíîì ñîñòîÿíèè q 0 � K n îòîáðàæåíèå
F q( , )M1 0
íå ÿâëÿåòñÿ áèåêöèåé. Ñëåäîâàòåëüíî, M
inv
1 1�A .
Òåîðåìà äîêàçàíà.
Òåîðåìà 2. Äëÿ ëþáîãî îòîáðàæåíèÿ f1: K Kn n èñòèííî ðàâåíñòâî
A A
2 2 2 2
inv n nM K K� � { | :f è f3 : K Kn n — áèåêöèè}. (7)
Äîêàçàòåëüñòâî. Ïóñòü M 2 2�A — òàêîé àâòîìàò, ÷òî îòîáðàæåíèÿ fi
n nK K:
( , )i � 2 3 ÿâëÿþòñÿ áèåêöèÿìè. Èç (2) íàõîäèì
x f q f qt t t�
�
�� �1 3
1
1 1( ( )), (8)
q f yt t�
�
��1 2
1
1( ) . (9)
Ïîäñòàâèì (9) â (8) è ïîëó÷èì
x f f y f qt t t�
� �
�� �1 3
1
2
1
1 1( ( ) ( )). (10)
Çàìåíèâ â (9) è (10) x íà y , à y íà x , ïîëó÷èì òàêîé àâòîìàò
M
t t
t t t
2
1 1 2
1
1
1 3
1
2
1
1 1
� �
�
�
�
� �
�
�
� �
�
�:
( )
( ( ) ( ))
q f x
y f f x f q
�
��
� �( )t Z , (11)
êîãäà ïðè êàæäîì íà÷àëüíîì ñîñòîÿíèè q 0 � K n èíèöèàëüíûé àâòîìàò ( , )M 2
1
0
� q
ðåàëèçóåò îòîáðàæåíèå F
q( , )M2 0
1� , ò.å. ïðè êàæäîì íà÷àëüíîì ñîñòîÿíèè q 0 �K n îòî-
áðàæåíèå F q( , )M2 0
ÿâëÿåòñÿ áèåêöèåé. Ñëåäîâàòåëüíî, M
inv
2 2�A .
Ïóñòü M 2 2�A — òàêîé àâòîìàò, êîãäà õîòÿ áû îäíî èç îòîáðàæåíèé
f i
n nK K: ( , )i � 2 3 íå ÿâëÿåòñÿ áèåêöèåé.
Åñëè îòîáðàæåíèå f3: K Kn n íå ÿâëÿåòñÿ áèåêöèåé, òî ñóùåñòâóþò òàêèå
âõîäíûå ñèìâîëû x x f1 1 3, ~ � ker , ÷òî x x1 1� ~ . Ïîñêîëüêó f x f x3 1 3 1( ) (~ )� , òî
y f f q f x f f q f x y1 2 1 0 3 1 2 1 0 3 1 1� � � � �( ( ) ( )) ( ( ) (~ )) ~
äëÿ âñåõ q 0 � K n , ò.å. ïðè êàæäîì íà÷àëüíîì ñîñòîÿíèè q 0 � K n îòîáðàæåíèå
F q( , )M2 0
íå ÿâëÿåòñÿ áèåêöèåé. Îòñþäà èìååì M
inv
2 2�A .
Ïóñòü f3: K Kn n — áèåêöèÿ, à îòîáðàæåíèå f2: K Kn n íå ÿâëÿåòñÿ áè-
åêöèåé. Òîãäà ñóùåñòâóþò òàêèå q q f1 1 2, ~ � ker , ÷òî q q1 1� ~ . À òàê êàê
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 2 29
f3: K Kn n — áèåêöèÿ, òî äëÿ ëþáîãî q 0 � K n èìåþòñÿ òàêèå x x1 1, ~ � K n
( ~ )x x1 1� , ÷òî q f q f x1 1 0 3 1� �( ) ( ) è ~ ( ) (~ )q f q f x1 1 0 3 1� � . Ñëåäîâàòåëüíî, äëÿ êàæäî-
ãî íà÷àëüíîãî ñîñòîÿíèÿ q 0 � K n àâòîìàòà M 2 2�A ñóùåñòâóþò òàêèå âõîäíûå
ñèìâîëû x x1 1, ~ � K n ( ~ )x x1 1� , ÷òî y f q f q y1 2 1 2 1 1� � �( ) (~ ) ~ . Ýòî îçíà÷àåò, ÷òî ïðè
êàæäîì íà÷àëüíîì ñîñòîÿíèè q 0 � K n îòîáðàæåíèå F q( , )M2 0
íå ÿâëÿåòñÿ áèåêöèåé.
Îòñþäà âûòåêàåò, ÷òî M
inv
2 2�A .
Òåîðåìà äîêàçàíà.
Èç (6) è (11) âûòåêàåò, ÷òî äëÿ àâòîìàòà M inv inv�
A A1 2 îáðàòíûì àâòîìàòîì
M �1 ÿâëÿåòñÿ àâòîìàò Ìèëè. Êðîìå òîãî, èç òåîðåì 1 è 2 âûòåêàþò ñëåäóþùèå òðè
ñëåäñòâèÿ.
Ñëåäñòâèå 3. Äëÿ ëþáîãî ïîòî÷íîãî øèôðà
(( , ), ( , ))M Mi iq q0
1
0
� ( , ( , ))q0 1 2� � �K M in
i i
inv
A
â ïðîöåññå øèôðîâàíèÿ – ðàñøèôðîâàíèÿ àâòîìàòû M i è M i
�1 äâèæóòñÿ â ïðîñò-
ðàíñòâå ñîñòîÿíèé ïî îäíîé è òîé æå òðàåêòîðèè â îäíîì è òîì æå íàïðàâëåíèè.
Ñëåäñòâèå 4. Äëÿ ëþáîãî àâòîìàòà M
inv
1 1�A ôóíêöèè ïåðåõîäîâ è âûõîäîâ àâòî-
ìàòà M1
1� ðàçäåëèìû ïî ïåðåìåííûì q è x òîãäà è òîëüêî òîãäà, êîãäà ïî ýòèì ïåðåìåí-
íûì ðàçäåëèìû îòîáðàæåíèÿ g q x f f x f q1 3 4
1
2( , ) ( ( ( )))� �� è g q x f x f q2 4
1
2( , ) ( ( ))� �� .
Ñëåäñòâèå 5. Äëÿ ëþáîãî àâòîìàòà M
inv
2 2�A ôóíêöèÿ âûõîäîâ àâòîìàòà M 2
1�
ðàçäåëèìà ïî ïåðåìåííûì q è x òîãäà è òîëüêî òîãäà, êîãäà ïî ýòèì ïåðåìåííûì
ðàçäåëèìî îòîáðàæåíèå g q x f f x f q3 3
1
2
1
1( , ) ( ( ) ( ))� �� � .
ÇÀÊËÞ×ÅÍÈÅ
 ðàññìîòðåííûõ ìíîæåñòâàõ àâòîìàòîâ Ìèëè è Ìóðà íàä êîëüöîì K ôóíêöèè
ïåðåõîäîâ è âûõîäîâ ÿâëÿþòñÿ ëèíåéíûìè êîìáèíàöèÿìè ôóíêöèé îò ñîñòîÿíèÿ
è ôóíêöèé îò âõîäíîãî ñèìâîëà. Äàíà õàðàêòåðèñòèêà ïîäìíîæåñòâà ñèëüíîñâÿç-
íûõ, ïåðåñòàíîâî÷íûõ, ïðèâåäåííûõ è îáðàòèìûõ àâòîìàòîâ.
Àíàëèç ïîäìíîæåñòâ ìíîæåñòâ Ai ( , )i �1 2 , îïðåäåëÿåìûõ êîíêðåòíûìè òèïà-
ìè îòîáðàæåíèé f j ( , , )j �1 4� (ïîëèíîìû, ýêñïîíåíòû è ò.ä.) ïðåäñòàâëÿåò âîç-
ìîæíîå íàïðàâëåíèå èññëåäîâàíèé. Äðóãîå íàïðàâëåíèå — èññëåäîâàíèå àâòîìà-
òîâ ñ ëàãîì l ( )l � 1 íàä êîëüöîì K .
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. À ë ô å ð î â À . Ï . , Ç ó á î â À . Þ . , Ê ó ç ü ì è í À . Ñ . è ä ð. Îñíîâû êðèïòîãðàôèè. — Ì.: Ãåëèîñ
ÀÐÂ, 2002. — 480 ñ.
2. Õ à ð è í Þ . Ñ . , Á å ð í è ê  . È . , Ì à ò â å å â à .  . è ä ð . Ìàòåìàòè÷åñêèå è êîìïüþòåðíûå
îñíîâû êðèïòîëîãèè. — Ìèíñê: Íîâîå çíàíèå, 2003. — 382 ñ.
3. Ê ó ç ü ì è í À . Ñ . , Ê ó ð à ê è í  . Ë . , Í å ÷ à å â À . À . Ïñåâäîñëó÷àéíûå è ïîëèëèíåéíûå ïîñëå-
äîâàòåëüíîñòè / Òðóäû ïî äèñêðåòíîé ìàòåìàòèêå. Ò. 1. — Ì.: Íàó÷íîå èçä-âî «ÒÂÏ», 1997. —
Ñ. 139–202.
4. Ê ó ç ü ì è í À . Ñ . , Ê ó ð à ê è í Â . Ë . , Í å ÷ à å â À . À . Ñâîéñòâà ëèíåéíûõ è ïîëèëèíåéíûõ
ðåêóððåíò íàä êîëüöàìè Ãàëóà. I / Òðóäû ïî äèñêðåòíîé ìàòåìàòèêå. Ò. 2. — Ì.: Íàó÷íîå èçä-âî
«ÒÂÏ», 1998. — Ñ. 191–222.
5. Ñ ê î á å ë å â Â . Â . , Ñ ê î á å ë å â Â . Ã . Àíàëèç øèôðñèñòåì. — Äîíåöê: ÈÏÌÌ ÍÀÍ Óêðàèíû,
2009. — 479 ñ.
6. Ñ ê î á å ë å â  .  . , Ñ ê î á å ë å â  . à . Î ñëîæíîñòè àíàëèçà àâòîìàòîâ íàä êîíå÷íûì êîëüöîì //
Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2010. — ¹ 4. — Ñ. 17–30.
7. Ê ó ð î ø À . Ã . Ëåêöèè ïî îáùåé àëãåáðå. — Ì.: Íàóêà, 1973. — 400 ñ.
Ïîñòóïèëà 02.07.2010
30 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 2
|
| id | nasplib_isofts_kiev_ua-123456789-84182 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T18:59:12Z |
| publishDate | 2011 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Скобелев, В.Г. 2015-07-03T15:50:18Z 2015-07-03T15:50:18Z 2011 О некоторых множествах автоматов над конечным кольцом / В.Г. Скобелев // Кибернетика и системный анализ. — 2011. — Т. 47, № 2. — С. 27-30. — Бібліогр.: 7 назв. — рос.. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/84182 512.552+519.713 Досліджено множини автоматів Мілі та Мура над довільним комутативно-асоціативним кільцем, у яких функції переходів та функції реакцій є лінійними комбінаціями функцій стану автомата та функцій вхідного символу. Охарактеризовано підмножини сильнозв’язаних автоматів, автоматів, у яких функція переходів є переставленням, приведених автоматів та оборотних автоматів. Sets of Mealy and Moore automata over an arbitrary finite commutative-associative ring with transition and output functions being linear combinations of any function of state of an automaton with any function of its input are investigated. Subsets of strongly connected, with permutation transition function, permutation reduced, and reversible automata are characterized. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика О некоторых множествах автоматов над конечным кольцом Про деякі множини автоматів над скінченним кільцем Some subsets of automata over a finite ring Article published earlier |
| spellingShingle | О некоторых множествах автоматов над конечным кольцом Скобелев, В.Г. Кибернетика |
| title | О некоторых множествах автоматов над конечным кольцом |
| title_alt | Про деякі множини автоматів над скінченним кільцем Some subsets of automata over a finite ring |
| title_full | О некоторых множествах автоматов над конечным кольцом |
| title_fullStr | О некоторых множествах автоматов над конечным кольцом |
| title_full_unstemmed | О некоторых множествах автоматов над конечным кольцом |
| title_short | О некоторых множествах автоматов над конечным кольцом |
| title_sort | о некоторых множествах автоматов над конечным кольцом |
| topic | Кибернетика |
| topic_facet | Кибернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84182 |
| work_keys_str_mv | AT skobelevvg onekotoryhmnožestvahavtomatovnadkonečnymkolʹcom AT skobelevvg prodeâkímnožiniavtomatívnadskínčennimkílʹcem AT skobelevvg somesubsetsofautomataoverafinitering |