Анализ автоматных моделей, определенных на многообразиях над конечным кольцом
Досліджено автоматні моделі, визначені над скінченним кільцем на багатовиді з алгеброю та на параметризованому багатовиді із заданою множиною траєкторій. Визначено гомоморфізми вказаних структур. Встановлено, яким чином гомоморфізм однієї структури на іншу дає змогу за автоматною моделлю, яку задано...
Saved in:
| Published in: | Проблемы управления и информатики |
|---|---|
| Date: | 2013 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/207638 |
| 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: | Анализ автоматных моделей, определенных на многообразиях над конечным кольцом / В.В. Скобелев // Проблемы управления и информатики. — 2013. — № 4. — С. 147–156. — Бібліогр.: 11 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860158959425421312 |
|---|---|
| author | Скобелев, В.В. |
| author_facet | Скобелев, В.В. |
| citation_txt | Анализ автоматных моделей, определенных на многообразиях над конечным кольцом / В.В. Скобелев // Проблемы управления и информатики. — 2013. — № 4. — С. 147–156. — Бібліогр.: 11 назв. — рос. |
| collection | DSpace DC |
| container_title | Проблемы управления и информатики |
| description | Досліджено автоматні моделі, визначені над скінченним кільцем на багатовиді з алгеброю та на параметризованому багатовиді із заданою множиною траєкторій. Визначено гомоморфізми вказаних структур. Встановлено, яким чином гомоморфізм однієї структури на іншу дає змогу за автоматною моделлю, яку задано на початковій структурі, побудувати її гомоморфний образ, визначений на результуючій моделі. Охарактеризовано множини групових автоматів, автоматів зі станами-джерелами, автоматів зі станами-стоками, автоматів, які мають стани-близнюки, та 1-діагностовних автоматів.
There are analyzed automata models determined over finite ring on variety with algebra and on parametrized variety with prescribed set of trajectories. Homomorphisms of pointed structures are determined. It is proposed some method of exploring this homomorphism for design for any automata model determined in initial structure its image determined in resulting structure. The sets of group automata, automata with source-states, automata with flow-states, automata with twins-states and automata with 1-distinguishable states are characterized.
|
| first_indexed | 2025-12-07T17:54:08Z |
| format | Article |
| fulltext |
© В.В. СКОБЕЛЕВ, 2013
Международный научно-технический журнал
«Проблемы управления и информатики», 2013, № 4 147
ПРОБЛЕМЫ ЗАЩИТЫ ИНФОРМАЦИИ
УДК 519.712 + 681.3
В.В. Скобелев
АНАЛИЗ АВТОМАТНЫХ МОДЕЛЕЙ,
ОПРЕДЕЛЕННЫХ НА МНОГООБРАЗИЯХ
НАД КОНЕЧНЫМ КОЛЬЦОМ
Введение
Многообразие над полем (т.е. множество решений системы алгебраических
уравнений над полем) является одним из основных понятий алгебраической геомет-
рии [1, 2]. Это понятие естественным образом переносится на конечное кольцо [3].
Актуальность исследования автоматных моделей, определенных на многообра-
зии над конечным кольцом, объясняется следующими обстоятельствами. Во-пер-
вых, такие модели определяют новый класс дискретных конечных динамических
систем. Во-вторых, в современных шифрах используются вычисления в кольцах
вычетов [4, 5]. В-третьих, эллиптическая криптография [6, 7] считается одним из
наиболее перспективных направлений современной криптографии (эллиптическая
кривая, как и любая алгебраическая кривая, представляет собой многообразие).
Известно, что параметризованные многообразия часто применяются как в ма-
тематике, так и в ее многочисленных приложениях. При этом (в явном или неяв-
ном виде) используется то обстоятельство, что параметризация дает возможность
естественно выделить то или иное множество траекторий на многообразии. Кроме
того, эллиптическая кривая — это пример многообразия, которое является абеле-
вой группой, т.е. специальным случаем алгебры. Поэтому естественно выделить
множество многообразий с определенными на них алгебрами.
Целью настоящей работы и является исследование свойств автоматов Мили
и Мура, определенных над конечным кольцом на параметризованных многообрази-
ях (c заданным множеством траекторий) и на многообразиях с алгеброй. В разд. 1
введены необходимые понятия и определены исследуемые модели. В разд. 2 опре-
делены гомоморфизмы рассматриваемых многообразий. Построены отображения,
которые каждому автомату, определенному на исходном многообразии, ставят в
соответствие гомоморфный образ автомата, определенный на гомоморфном образе
многообразия. В разд. 3 и 4 охарактеризованы некоторые основные нетривиальные
подмножества исследуемых автоматов. Заключение содержит ряд выводов.
1. Исследуемые модели
Автомат над конечным кольцом ),,( KK представляет собой конечную
дискретную динамическую систему, определенную системой уравнений
),(
),,(
121
111
ttt
ttt
x
x
qfy
qfq
),( Zt (1)
где
nn KXK :1f и
ln KXK :2f — функция переходов и выходов,
а ,n
t Kq tx и
l
t Ky — соответственно вектор состояния, входной символ
148 ISSN 0572-2691
и вектор, представляющий выходной символ автомата в момент t. Если при лю-
бом начальном векторе состояния ,0q принадлежащем многообразию ,nKV
для любого входного слова ixx 1 )( Ni все состояния jq ),,1( ij также
принадлежат этому многообразию, то естественно говорить, что автомат опреде-
лен на многообразии V.
Во множестве всех многообразий в nK выделяются следующие два подмно-
жества многообразий, имеющие многочисленные приложения:
1) множество )(,1 KV n всех таких многообразий ,nKV что определена ал-
гебра ),,( 21 FFS VV где },,{
101 k F и },,{
212 k F — множество
соответственно унарных и бинарных операций, определенных на множестве V;
2) множество )(,2 KV n всех многообразий ,nKV для которых существует
параметризация ),(τhv где mKτ ),( nm а T
1 ),,( nhh h — набор поли-
номов от m переменных mtt ,,1 над кольцом K .
Пример 1. 1. Пусть — эллиптическая кривая над конечным полем .K Из-
вестно, что множество точек G этой кривой (включая бесконечно удаленную
точку O) является абелевой группой ).,( GG Зафиксируем на множестве
G множество унарных операций },,,,{
1101 k F где OP )(0 и
i
i PPP )( )(
1ki N для всех .GP Таким образом, определена ал-
гебра ),,( 21 FFS
GG где },{2 F т.е. ).(2,1 KVG
2. Пусть многообразие
nKV задано системой уравнений 0 im
nii vav
).1,,1( ni Параметризация многообразия V имеет вид
),1,,1(
ta
nitav
n
m
ii
i
).( Kt
Итак, ).(,2 KV nV
Из определения множеств )(,1 KV n и )(,2 KV n вытекает, что автоматы на мно-
гообразиях, принадлежащих этим множествам, можно определить следующим
образом.
На многообразии )(,1 KV nV алгебра VS дает возможность определить
множества автоматов Мили )()1(
VnA и Мура )()2(
VnA соответственно системами
уравнений
))(),((
)),(),((
21
11
122
111
vqy
vqq
t
t
xtijt
xtijt
);( Zt (2)
)),((
)),(),((
211
11
22
111
vqy
vqq
tijt
xtijt t ),( Zt (3)
где Vvv 21, — фиксированные точки, 121 1
, kii Z и
221, kjj N — фиксиро-
ванные числа, а Vq 0 и .11 1 ktx Z Из (2) и (3) вытекает, что для автомата
)()( )2()1(
VV nnM AA множество чисел 11kZ является входным алфавитом,
а многообразие V — множеством состояний и выходным алфавитом.
Пример 2. Из примера 1 и формул (2), (3) вытекает, что на многообразии G
(где — эллиптическая кривая над конечным полем K ) множества автоматов Мили
)(
)1(
2 GA и Мура )(
)2(
2 yGA определяются соответственно системами уравнений
Международный научно-технический журнал
«Проблемы управления и информатики», 2013, № 4 149
211
111 ,
Pxmqy
Pxnqq
ttt
ttt
);( Zt (4)
,
211
111
Pmqy
Pxnqq
tt
ttt
),( Zt (5)
где GPP 21, — фиксированные точки, 11
, kmn Z — фиксированные числа,
11 1 ktx Z и .0 Gq Для автомата )()(
)2(
2
)1(
2 GGM AA множество чисел
11kZ является входным алфавитом, а многообразие G — множеством состоя-
ний и выходным алфавитом.
Отметим, что множество автоматов )()(
)2(
2
)1(
2 GG AA исследовано в [8, 9].
В частности, охарактеризованы множества групповых и приведенных автоматов,
решены задача восстановления
начального состояния автомата и
задача построения асимптотически
точной имитационной модели для
семейства автоматов (в общем виде
эта задача решена в [10, 11]).
Для определения автоматов на
многообразии )(,2 KV nV восполь-
зуемся тем обстоятельством, что
параметризация дает возможность
выделить на многообразии множе-
ство траекторий, т.е. последова-
тельностей точек. Действительно
(см. рис. 1), любое отображение
mm KKf : определяет во множестве mK множество траекторий ,τ ),(τf
),(2
τf ).( mKτ Следовательно, на многообразии )(,2 KV nV отображение
mm KKf : и параметризация )(τhv )( mKτ определяют множество траек-
торий )),(()),((),( 2
τhτhτh ff ),( mKτ где
i
i fff )( Ni , а — опе-
рация суперпозиции.
Отсюда вытекает, что для фиксированного семейства отображений
kii N }{
(где
mm
i KK : для всех ki N ) естественно определить на многообразии V
множества автоматов Мили ),(
)1(
,, VlknA и Мура ),(
)2(
,, VlknA соответственно си-
стемами уравнений
)(
)),((
1
1
1
1
txt
txt
t
t
qry
τhq
);( Zt (6)
)(
)),((
11
1 1
tt
txt t
qry
τhq
),( Zt (7)
где ,0
mKτ ),( 00 τhq )(
11 txt t
ττ
),( Zt
ln
i KK :r ),( ki N
ln KK :r и ktx N1 ).( Zt Из (6) и (7) вытекает, что для автомата
),(),( ,,
)1(
,, VV
(2)AA lknlknM множество чисел kN — входной алфавит, много-
образие V — множество состояний, а множество lK — выходной алфавит. По-
ложим
1
)(
,,
)(
, ),(),(
l
i
lkn
i
kn VV AA ).2,1( i
h
h
h
h
h h K
m
V
f ()
f
2
()
1 f (1)
f
2
(1)
Рис. 1
150 ISSN 0572-2691
2. Гомоморфизмы исследуемых моделей
Известно, что гомоморфизм — одно из наиболее важных качественных по-
нятий теории динамических систем. Неформально говоря, это понятие дает воз-
можность выделить те свойства, которые сохраняются при проекциях множеств,
определяющих динамическую систему, на более простые множества. Для авто-
матов ),,,,( iiiiii YXQM )2,1( i , где iii YXQ ,, — множество состояний,
входной и выходной алфавит, а iiii QXQ : и iiii YXQ : — функции
переходов и выходов, это понятие имеет следующий вид. Автомат 2M назы-
вается гомоморфным образом автомата ,1M если существуют такие сюръекции
,: 211 QQ 212 : XX и ,: 213 YY что равенства )),(( 11 xq
))(),(( 212 xq и ))(),(()),(( 21213 xqxq истинны для всех 1Qq
и .1Xx В частности, если отображения ,1 2 и 3 — биекции, то автоматы
1M и 2M называются изоморфными.
Ясно, что для анализа гомоморфизмов автоматов, определенных формулами
(2) и (3), необходимо определить гомоморфизмы упорядоченных пар ),( VV S
)),(( ,1 KV nV а для анализа гомоморфизмов автоматов, определенных формула-
ми (6) и (7), — гомоморфизмы упорядоченных пар ),( V )).(( ,2 KV nV
Рассмотрим вначале упорядоченные пары ),(
ii VV S ),2,1( i где ),(,1 KV
ini V
а ),(
)(
2
)(
1
ii
ii
FFS VV }).,,{},,,{(
)()(
12
)()(
0
)(
1 )(
2
)(
1
i
k
ii
k
ii
ii FF
Будем говорить, что упорядоченная пара ),(
22 VV S — гомоморфный образ
упорядоченной пары ),,(
11 VV S если существует гомоморфизм алгебры
1VS на
алгебру ,
2VS т.е. такая тройка сюръекций ),,,( 321 где ,: 211 VV
)2(
1
)1(
12 : FF и ,:
)2(
2
)1(
23 FF что ))()(())((
)1(
112
)1(
11 vv и )),((
)1(
2
)1(
11 vv
))(),()((
)1(
21
)1(
113 vv для всех ,, 1
)1(
2
)1(
1 Vvv
)1(
1F и .
)1(
2F В этом
случае можно установить следующее:
1) гомоморфным образом автомата )( 1
)1(
1
1
V
n
M A , определенного системой
уравнений
))(),((
)),(),((
)1(
2
)1()1()1()1()1(
1
)1(
1
)1()1()1()1()1(
1
122
111
vqy
vqq
t
t
xtijt
xtijt
),( Zt (8)
является автомат ),( 2
)1(
2
2
V
n
M A определенный системой уравнений
)))()(()),()(()((
))),()(()),()(()((
)1(
21
)1(
2
)1(
1
)1(
2
)1(
3
)2(
1
)1(
11
)1(
2
)1(
1
)1(
2
)1(
3
)2(
1
122
111
vqy
vqq
t
t
xtijt
xtijt
);( Zt (9)
2) гомоморфным образом автомата )( 1
)2(
1
1
V
n
M A , определенного системой
уравнений
)),((
)),(),((
)1(
2
)1(
1
)1()1()1(
1
)1(
1
)1()1()1()1()1(
1
22
111
vqy
vqq
tijt
xtijt t ),( Zt (10)
является автомат ),( 2
)2(
2
2
V
n
M A определенный системой уравнений
))()),()(()((
))),()(()),()(()((
)1(
21
)1(
11
)1(
2
)1(
3
)2(
1
)1(
11
)1(
2
)1(
1
)1(
2
)1(
3
)2(
1
22
111
vqy
vqq
tijt
xtijt t ).( Zt (11)
Международный научно-технический журнал
«Проблемы управления и информатики», 2013, № 4 151
Таким образом, доказана следующая теорема.
Теорема 1. Пусть )(,1 KV
ini V ).2,1( i Если упорядоченная пара ),(
22 VV S —
гомоморфный образ упорядоченной пары ),,(
11 VV S то существуют такие отоб-
ражения )()(: 2
)(
1
)(
21
VV
j
n
j
nj AA ),2,1( j что автомат )()( 2
)(
1
2
V
j
nj M A
))(( 1
)(
1
1
V
j
n
M A — гомоморфный образ автомата .1M
Отметим, что из (8)–(11) вытекает, что для тройки сюръекций ),,,( 321
определяющей гомоморфизм автомата )( 1
)(
1
1
V
j
n
M A на автомат
),()( 2
)(
1
2
V
j
nj M A истинно равенство ,131 а значения 12 2
)( ki Z
)( 11
ki Z определяются равенствами ))()(())((
)1(
112
)1(
11 vv ii
).,(
)1(
11
)1( F iVv
Пример 3. Пусть i )2,1( i — эллиптическая кривая над конечным по-
лем .iK Считается, что 2 — гомоморфный образ ,1 если группа ),(
222 GG —
гомоморфный образ группы ).,(
111 GG Гомоморфизм группы
1
G на груп-
пу
2
G естественным образом определяет условия, при которых алгебра
2
GS
),(
)2(
2
)2(
12
FF G — гомоморфный образ алгебры ).,(
)1(
2
)1(
111
FFS
GG В по-
следнем случае для автоматов, принадлежащих множеству ),()(
11
)2(
2
)1(
2 GG AA
формулы (8)–(11) определяют способ построения их гомоморфных образов, при-
надлежащих множеству ).()(
22
)2(
2
)1(
2 GG AA
Рассмотрим теперь упорядоченные пары ),( )( j
j V ),2,1( j где ),(,2 KV
jnj V
а
ki
j
i
j
N }{
)()( (где jj mmj
i KK :
)( для всех ki N ), а )(τhv j )( jm
Kτ —
параметризация многообразия .jV
Будем считать, что упорядоченная пара ),( )2(
2 V — гомоморфный образ упо-
рядоченной пары ),,( )1(
1 V если существует такая пара сюръекций ),,( 21
где 211 : VV и ,: 21
2
mm
KK что ))(())(( 2211 τhτh и ))((
)1(
2 τi
))(( 2
)2(
τ i для всех 1m
Kτ и .ki N
1. Гомоморфным образом автомата ),,( )1(
1
)1(
,,1
11
V
lkn
M A определенного си-
стемой уравнений
)(
)),((
)1()1()1(
1
)1(
1
)1(
1
1
1
txt
txt
t
t
qry
τhq
),( Zt (12)
является автомат ),,( )2(
2
)1(
,,2
22
V
lkn
M A определенный системой уравнений
))((
)),(((
)1(
1
)2()2(
1
2
)2(
2
)2(
1
1
1
txt
txt
t
t
qry
τhq
),( Zt (13)
где отображения 22:
)2( ln
i KK r )( ki N определены следующим образом.
Пусть ,,11 iM
i
M SS
k
N
где }|{ 2,,1
Vvv iiM SS ),( ki N )),(( 1
1
)1(
, vrv
iiS
а
1M — такое отношение эквивалентности на множестве ,
1MS что
111 ,, iMi SS vv ), ;,( 212 kii NVvv тогда и только тогда, когда существуют
152 ISSN 0572-2691
такая последовательность vvvvv n,,, 21 элементов многообразия 2V
и такая последовательность 2211 ,,, irrri n элементов множества ,kN что
11,, jjjj rr SS vv для всех .1,,1 nj Пусть
1M — такая сюръекция
множества
)1(
Val i
i k
r
N
в фактор-множество ,/
11 MMS что sy )(
1M тогда
и только тогда, когда существует такое ,, sv iS что .,iSvy Положим 2l
⌈ 1) ||(log) ||log
1
KSM ⌉ и зафиксируем инъекцию
1M фактор-множества
11
/ MMS в множество .2lK Определим отображения
)2(
ir )( ki N равенствами
)))(()(()( 1
1
)1()2(
11
vrvr
iMMi ).,( 2 ki NVv
2. Гомоморфным образом автомата ),,( )1(
1
)2(
,,1
11
V
lkn
M A определенного си-
стемой уравнений
)(
)),((
)1(
1
)1()1(
1
)1(
11
)1(
1
tt
ttt
qry
τhq
),( Zt (14)
является автомат ),( )2(
2
)2(
,,2
22
V
lkn
M A , определенный системой уравнений
)(
))),(((
)2(
1
)2()1(
1
)2(
12
)2(
1
tt
ttt
qry
τhq
),( Zt (15)
где отображение 22:)2( ln
KK r определено следующим образом.
Пусть },|{ 21
Vvv SSM где )),(( 1
1
)1(
vrv
S а
1M — такое отношение
эквивалентности на множестве ,
1MS что vv SS M1
),( 2Vvv тогда и только
тогда, когда существует такая последовательность vvvvv n,,, 21 элемен-
тов многообразия ,2V что
1jj
SS vv для всех .1,,1 nj Пусть
1M —
такая сюръекция множества )1( Val r в фактор-множество ,/
11 MMS что
sy )(
1M тогда и только тогда, когда существует такое ,sv S что .vy S По-
ложим 2l ⌈ 1) ||(log) ||log
1
KSM ⌉ и зафиксируем инъекцию
1M фактор-
множества
11
/ MMS во множество .2lK Определим отображение )2(r равен-
ством )))(()(()( 1
1
)1()2(
11
vrvr
MM ).( 2Vv
Таким образом, доказана следующая теорема.
Теорема 2. Пусть )(,2 KV
ini V )2,1( i . Если упорядоченная пара
),( )2(
2 V — гомоморфный образ упорядоченной пары ),,( )1(
1 V то существуют
такие отображения ),(),(: )2(
2
)()1(
1
)(
, ,21
VV
j
n
j
knj
k
AA ),2,1( j что автомат
),()( )2(
2
)(
,1
2
V
j
knj M A )),(( )1(
1
)(
,1
1
V
j
kn
M A — гомоморфный образ автомата .1M
Охарактеризуем теперь свойства исследуемых моделей.
3. Анализ множества автоматов )V()V(
(1) )2(
nn AA ))(V( 1 KV n,
Рассмотрим кратко свойства автоматов )()( )2()1(
VV nnM AA , установлен-
ные в [9]. Автомат называется групповым, если каждый входной символ осу-
ществляет перестановку на множестве его состояний.
Международный научно-технический журнал
«Проблемы управления и информатики», 2013, № 4 153
Из (2) и (3) вытекает, что множество групповых автоматов )()1(
VnM A
)()2(
VnA определяется множеством всех таких пар ,),( 2111
FF ji что
V
1
Val i и V
vV
}{1
Val j для всех 11
Val Fvv , где }.)({Val 11 1
kr ZrvvF
Состояние автомата называется:
1) источником, если в него невозможно перейти ни из одного состояния;
2) стоком, если из него невозможно перейти ни в какое другое состояние.
Из (2) и (3) вытекает, что для автомата )()( )2()1(
VV nnM AA :
1) множество )(MsrcV всех состояний-источников определяется равенством
)( Val\)(
111
1 Val Fv
VV
Valjsrc
i
M
;
2) множество всех состояний-стоков )(MflV определяется равенством
)}( Val}{|{)(
1111 Val)}({ FvqqVqV
ijfl M .
Таким образом, автомат )()( )2()1(
VV nnM AA не имеет состояний-источ-
ников, если V
v
)( Val
111
1 Val Val Fi
j , и не имеет состояний-стоков, если
}{)}( Val
111
1 Val)}({
q
vq
Fi
j для всех Vq .
Для характеристики свойств автомата )()( )2()1(
VV nnM AA , зависящих от
его функции выхода, определим эквивалентности )(1 v )Val( 11
Fvv , )(2 v
)Val( 12
Fvv и )(3 v )Val( 11
Fvv на множестве V :
)),~(( )),(( )()~,(
11111 vqvqvqq ijij ,
)),~(( )),(( )()~,(
22222 vqvqvqq ijij ,
))),),~(((())),),(((()()~,( 223 11221122
vvqvvqvqq ijijijij .
Положим )(1
Val
1
11
v
vv
F
, )(2
Val
2
2
v
vv
F
и )(3
Val
3
1
v
vv
F
.
Два различных состояния автомата называются близнецами, если по каждому
входному символу они переходят в одно и то же состояние и при этом автомат
выдает один и тот же выходной символ.
Из (2) вытекает, что состояния Vqq ~, )~( qq автомата )()1(
VnM A явля-
ются близнецами тогда и только тогда, когда 21)~,( qq .
Следовательно, максимальными множествами состояний-близнецов автомата
)()1(
VnM A являются такие элементы S фактор-множества )/( 21 V , что
2S .
Аналогично, из (3) вытекает, что состояния Vqq ~, )~( qq автомата
)()2(
VnM A являются близнецами тогда и только тогда, когда 31)~,( qq .
Следовательно, максимальными множествами состояний-близнецов автомата
)()1(
VnM A являются такие элементы S фактор-множества )/( 31 V , что
2S .
Автомат называется 1-диагностируемым, если любые два его различных со-
стояния различимы некоторым входным символом.
Из (2) вытекает, что автомат )()1(
VnM A является 1-диагностируемым тогда
и только тогда, когда 2 — отношение равенства на многообразии .V
154 ISSN 0572-2691
Аналогично, из (3) вытекает, что автомат )()2(
VnM A 1-диагностируемый то-
гда и только тогда, когда 3 — отношение равенства на многообразии V.
4. Анализ множества автоматов Θ)V(Θ)V(
(2)
,
(1)
, ,, knkn AA ))(V( 2 KV n,
Если на семейство отображений
kii N }{ не наложить никаких огра-
ничений, то формулы (4) и (5) могут
определять как детерминированные, так и
недетерминированные автоматы.
Ситуация при которой отображение
mm
i KK : приводит к недетермини-
рованному автомату, изображена на рис. 2.
Ясно, что необходимое и достаточ-
ное условие, исключающее эту ситуацию,
имеет следующий вид:
)(ker)(ker
)2(
0
)1(
0
)2(
0
)1(
0 i hττhττ (16)
для всех
mK
)2(
0
)1(
0 ,ττ и i .
Пусть hF — множество всех отображений mm KK : , удовлетворяющих
условию (16).
Таким образом, доказана следующая теорема.
Теорема 3. Пусть )(τhv )( mKτ — полиномиальная параметризация
многообразия ).(,2 KV nV Тогда множество ),(),(
(2)
,
)1(
, VV knkn AA состоит из
следующих автоматов:
1) недетерминированных автоматов тогда и только тогда, когда семейство
kii N }{ содержит хотя бы один элемент, не принадлежащий множеству ;hF
2) детерминированных автоматов тогда и только тогда, когда все элементы
семейства
kii N }{ принадлежат множеству .hF
В дальнейшем рассматриваем только детерминированные автоматы, т.е. счи-
таем, что все элементы семейства
kii N }{ принадлежат множеству .hF
Пусть
)0(
hF — множество всех таких отображений ,hF что
).(ker)(ker
)2(
0
)1(
0
)2(
0
)1(
0 hττhττ (17)
Из (6), (7) и (17) вытекает следующее:
1) множество ),(),(
(2)
,
)1(
, VV knkn AA состоит из групповых автоматов тогда
и только тогда, когда
kii N }{ — семейство элементов множества ;
)0(
hF
2) ни один автомат ),(),(
(2)
,
)1(
, VV knknM AA не является групповым ав-
томатом тогда и только тогда, когда семейство
kii N }{ содержит хотя бы
один элемент, принадлежащий множеству .\
)0(
hh FF
Пусть }.,,{ker/ ||1 Vh BBK m Из (6), (7) и (17) вытекает, что множество
),(),(
(2)
,
)1(
, VV knkn AA состоит из следующих автоматов:
V
h
K
m
i
Рис. 2
Международный научно-технический журнал
«Проблемы управления и информатики», 2013, № 4 155
1) имеющих состояния-источники тогда и только тогда, когда
kii N }{ —
такое семейство элементов множества ,\
)0(
hh FF что существует ,||VNj для ко-
торого истинно включение ;\Val j
m
i
i
BK
k
N
2) имеющих состояния-стоки тогда и только тогда, когда
kii N }{ — та-
кое семейство элементов множества ,hF что существует ,||VNj для которого
истинно включение .)|(Val jBi
i
B
j
k
N
Поскольку ни один групповой автомат не имеет состояний-близнецов, то из
(6) и (7) вытекает следующее:
1) автомат ),(
)1(
, VknM A имеет состояния-близнецы тогда и только тогда,
когда
kii N }{ — семейство элементов множества
)0(
\ hh FF и существуют
такие ,, mKττ что )(kerhττ и ))(ker()( hττ ii для всех ki N и
));ker(( hrττ
N
i
i k
2) автомат ),(
)2(
, VknM A имеет состояния-близнецы тогда и только тогда,
когда
kii N }{ — семейство элементов множества
)0(
\ hh FF и существуют
такие ,, mKττ что )(kerhττ и ))(ker()( hττ ii для всех .ki N
Кроме того, из (6) и (7) вытекает, что:
1) автомат ),(
)1(
, VknM A 1-диагностируем тогда и только тогда, когда
);ker(ker hrh
N
i
i k
2) автомат ),(
)2(
, VknM A 1-диагностируем тогда и только тогда, когда
).ker(ker ii
i k
hrh
N
Заключение
В настоящей работе исследованы автоматные модели, определенные над ко-
нечным кольцом на многообразии с алгеброй и параметризованном многообразии
с заданным множеством траекторий. Определены гомоморфизмы указанных
структур и показано, каким образом гомоморфизм одной структуры на другую
дает возможность по автоматной модели, определенной на исходной структуре,
строить ее гомоморфный образ, определенный на результирующей структуре.
Установлены свойства исследуемых моделей с позиции теории автоматов.
Анализ свойств исследуемых моделей при дополнительных ограничениях на
многообразие и/или определенную на нем алгебру либо заданное множество тра-
екторий, представляет одно из направлений дальнейших исследований. Другое
направление связано с исследованием тех свойств исходных моделей, которые
при дополнительных ограничениях на многообразие сохраняются для их гомо-
морфных образов. При этом с прикладной точки зрения особый интерес пред-
ставляет исследование гомоморфных образов множеств неподвижных точек соот-
ветствующих автоматных преобразований, а также решений задач восстановления
вектора начального состояния и параметрической идентификации исследуемых
моделей. Отметим, что именно эти характеристики и являются теоретическим
обоснованием целесообразности использования исследуемых моделей в процессе
решения задач защиты информации.
156 ISSN 0572-2691
В.В. Скобелєв
АНАЛІЗ АВТОМАТНИХ МОДЕЛЕЙ,
ВИЗНАЧЕНИХ НА БАГАТОВИДАХ
НАД СКІНЧЕННИМ КІЛЬЦЕМ
Досліджено автоматні моделі, визначені над скінченним кільцем на багатовиді
з алгеброю та на параметризованому багатовиді з заданою множиною траєкто-
рій. Визначено гомоморфізми вказаних структур. Встановлено, яким чином го-
моморфізм однієї структури на іншу дає змогу за автоматною моделлю, яку за-
дано на початковій структурі, побудувати її гомоморфний образ, визначений на
результуючій моделі. Охарактеризовано множини групових автоматів, автома-
тів зі станами-джерелами, автоматів зі станами-стоками, автоматів, які мають
стани-близнюки та 1-діагностовних автоматів.
V.V. Skobelev
ANALYSIS OF AUTOMATA MODELS
DETERMINED ON VARIETIES OVER FINITE RING
There are analyzed automata models determined over finite ring on variety with al-
gebra and on parametrized variety with prescribed set of trajectories. Homomor-
phisms of pointed structures are determined. It is proposed some method of exploring
this homomorphism for design for any automata model determined in initial structure
its image determined in resulting structure. The sets of group automata, automata
with source-states, automata with flow-states, automata with twins-states and autom-
ata with 1-distingushisable states and reversible automata are characterized.
1. Шафаревич И.Р. Основы алгебраической геометрии. Т.1. — М. : Наука, 1988. — 352 с.
2. Кокс Д., Литтл Дж., О'Ши Д. Идеалы, многообразия и алгоритмы. Введение в вычисли-
тельные аспекты алгебраической геометрии и коммутативной алгебры. — М.: Мир, 2000.
— 687 с.
3. Скобелев В.В., Глазунов Н.М., Скобелев В.Г. Многообразия над кольцами. — Донецк :
ИПММ НАН Украины, 2011. — 323 с.
4. Харин Ю.С., Берник В.И., Матвеев Г.В., Агиевич С.В. Математические и компьютерные ос-
новы криптологии. — Минск : Новое знание, 2003. — 382 с.
5. Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии. — М. :
Гелиос АРВ, 2002. – 480 с.
6. Болотов А.А., Гашков С.Б., Фролов А. Б. Элементарное введение в эллиптическую крипто-
графию: протоколы криптографии на эллиптических кривых. — М. : КомКнига, 2006. —
280 с.
7. Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. — М. : МЦМНО, 2003. —
328 с.
8. Скобелєв В.В. Аналіз автоматів, які визначено на еліптичних кривих // Вісн. Київ. ун-ту.
Сер.: фіз.-мат. науки. — 2012. — Вип. 1. — С. 223–230.
9. Скобелєв В.В. Автомати на многовидах з алгеброю // Там же. — 2012. — Вип. 2. —
С. 234–238.
10. Скобелев В.В. Моделирование автоматов над кольцом автоматами с конечной памятью //
Международный научно-технический журнал «Проблемы управления и информатики». —
2012. — № 3. — С. 114–122.
11. Скобелев В.В. Анализ задачи распознавания автомата над кольцом // Доповіді НАНУ. —
2012. — № 9. — С. 29–35.
Получено 04.12.2012
|
| id | nasplib_isofts_kiev_ua-123456789-207638 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | Russian |
| last_indexed | 2025-12-07T17:54:08Z |
| publishDate | 2013 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Скобелев, В.В. 2025-10-10T17:38:50Z 2013 Анализ автоматных моделей, определенных на многообразиях над конечным кольцом / В.В. Скобелев // Проблемы управления и информатики. — 2013. — № 4. — С. 147–156. — Бібліогр.: 11 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207638 519.712 + 681.3 10.1615/JAutomatInfScien.v45.i8.30 Досліджено автоматні моделі, визначені над скінченним кільцем на багатовиді з алгеброю та на параметризованому багатовиді із заданою множиною траєкторій. Визначено гомоморфізми вказаних структур. Встановлено, яким чином гомоморфізм однієї структури на іншу дає змогу за автоматною моделлю, яку задано на початковій структурі, побудувати її гомоморфний образ, визначений на результуючій моделі. Охарактеризовано множини групових автоматів, автоматів зі станами-джерелами, автоматів зі станами-стоками, автоматів, які мають стани-близнюки, та 1-діагностовних автоматів. There are analyzed automata models determined over finite ring on variety with algebra and on parametrized variety with prescribed set of trajectories. Homomorphisms of pointed structures are determined. It is proposed some method of exploring this homomorphism for design for any automata model determined in initial structure its image determined in resulting structure. The sets of group automata, automata with source-states, automata with flow-states, automata with twins-states and automata with 1-distinguishable states are characterized. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Проблемы защиты информации Анализ автоматных моделей, определенных на многообразиях над конечным кольцом Аналіз автоматних моделей, визначених на багатовидах над скінченним кільцем Analysis of Automata Models Determined on Varieties over Finite Ring Article published earlier |
| spellingShingle | Анализ автоматных моделей, определенных на многообразиях над конечным кольцом Скобелев, В.В. Проблемы защиты информации |
| title | Анализ автоматных моделей, определенных на многообразиях над конечным кольцом |
| title_alt | Аналіз автоматних моделей, визначених на багатовидах над скінченним кільцем Analysis of Automata Models Determined on Varieties over Finite Ring |
| title_full | Анализ автоматных моделей, определенных на многообразиях над конечным кольцом |
| title_fullStr | Анализ автоматных моделей, определенных на многообразиях над конечным кольцом |
| title_full_unstemmed | Анализ автоматных моделей, определенных на многообразиях над конечным кольцом |
| title_short | Анализ автоматных моделей, определенных на многообразиях над конечным кольцом |
| title_sort | анализ автоматных моделей, определенных на многообразиях над конечным кольцом |
| topic | Проблемы защиты информации |
| topic_facet | Проблемы защиты информации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/207638 |
| work_keys_str_mv | AT skobelevvv analizavtomatnyhmodeleiopredelennyhnamnogoobraziâhnadkonečnymkolʹcom AT skobelevvv analízavtomatnihmodeleiviznačenihnabagatovidahnadskínčennimkílʹcem AT skobelevvv analysisofautomatamodelsdeterminedonvarietiesoverfinitering |