Анализ задачи распознавания автомата над кольцом
Разработан метод приближенного решения задачи идентификации семейств автоматов, представленных системами уравнений с параметрами над конечным ассоциативно-коммутативным кольцом с единицей. Предложенный метод основан на построении имитационной модели для исследуемого семейства автоматов. Выделены им...
Saved in:
| Date: | 2012 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Видавничий дім "Академперіодика" НАН України
2012
|
| Series: | Доповіді НАН України |
| Subjects: | |
| Online Access: | http://dspace.nbuv.gov.ua/handle/123456789/84401 |
| 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: | Анализ задачи распознавания автомата над кольцом / В.В. Скобелев // Доповiдi Нацiональної академiї наук України. — 2012. — № 9. — С. 29-35. — Бібліогр.: 5 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-84401 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-844012015-07-08T03:02:07Z Анализ задачи распознавания автомата над кольцом Скобелев, В.В. Інформатика та кібернетика Разработан метод приближенного решения задачи идентификации семейств автоматов, представленных системами уравнений с параметрами над конечным ассоциативно-коммутативным кольцом с единицей. Предложенный метод основан на построении имитационной модели для исследуемого семейства автоматов. Выделены имитационные модели, моделирующие поведение автоматов исследуемого семейства автоматов с заданной точностью в “наихудшем случае” и “в среднем”. Розроблено метод наближеного розв’язання задачi iдентифiкацiї сiмей автоматiв, наведених системами рiвнянь з параметрами над скiнченним асоцiативно-комутативним кiльцем з одиницею. Запропонований метод базується на побудовi iмiтацiйної моделi для дослiджуваної сiм’ї автоматiв. Видiлено iмiтацiйнi моделi, якi моделюють поведiнку сiм’ї автоматiв з заданою точнiстю у “найгiршому випадку” та “у середньому”. A method of approximate solution of the problem of identification for families of automata presented by systems of equations with parameters over a finite associative-commutative ring with unity is proposed. The method is based on the construction of a simulation model for the family of automata under study. The models simulating the behavior of such family with given exactness “in the worst case” and “on the average” are separated. 2012 Article Анализ задачи распознавания автомата над кольцом / В.В. Скобелев // Доповiдi Нацiональної академiї наук України. — 2012. — № 9. — С. 29-35. — Бібліогр.: 5 назв. — рос. 1025-6415 http://dspace.nbuv.gov.ua/handle/123456789/84401 512.55+519.17 ru Доповіді НАН України Видавничий дім "Академперіодика" НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Інформатика та кібернетика Інформатика та кібернетика |
| spellingShingle |
Інформатика та кібернетика Інформатика та кібернетика Скобелев, В.В. Анализ задачи распознавания автомата над кольцом Доповіді НАН України |
| description |
Разработан метод приближенного решения задачи идентификации семейств автоматов, представленных системами уравнений с параметрами над конечным ассоциативно-коммутативным кольцом с единицей. Предложенный метод основан на построении
имитационной модели для исследуемого семейства автоматов. Выделены имитационные модели, моделирующие поведение автоматов исследуемого семейства автоматов с заданной точностью в “наихудшем случае” и “в среднем”. |
| format |
Article |
| author |
Скобелев, В.В. |
| author_facet |
Скобелев, В.В. |
| author_sort |
Скобелев, В.В. |
| title |
Анализ задачи распознавания автомата над кольцом |
| title_short |
Анализ задачи распознавания автомата над кольцом |
| title_full |
Анализ задачи распознавания автомата над кольцом |
| title_fullStr |
Анализ задачи распознавания автомата над кольцом |
| title_full_unstemmed |
Анализ задачи распознавания автомата над кольцом |
| title_sort |
анализ задачи распознавания автомата над кольцом |
| publisher |
Видавничий дім "Академперіодика" НАН України |
| publishDate |
2012 |
| topic_facet |
Інформатика та кібернетика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/84401 |
| citation_txt |
Анализ задачи распознавания автомата над кольцом / В.В. Скобелев // Доповiдi Нацiональної академiї наук України. — 2012. — № 9. — С. 29-35. — Бібліогр.: 5 назв. — рос. |
| series |
Доповіді НАН України |
| work_keys_str_mv |
AT skobelevvv analizzadačiraspoznavaniâavtomatanadkolʹcom |
| first_indexed |
2025-07-06T11:23:37Z |
| last_indexed |
2025-07-06T11:23:37Z |
| _version_ |
1836896503863443456 |
| fulltext |
УДК 512.55+519.17
© 2012
В.В. Скобелев
Анализ задачи распознавания автомата над кольцом
(Представлено академиком НАН Украины А.А. Летичевским)
Разработан метод приближенного решения задачи идентификации семейств автома-
тов, представленных системами уравнений с параметрами над конечным ассоциатив-
но-коммутативным кольцом с единицей. Предложенный метод основан на построении
имитационной модели для исследуемого семейства автоматов. Выделены имитацион-
ные модели, моделирующие поведение автоматов исследуемого семейства автоматов
с заданной точностью в “наихудшем случае” и “в среднем”.
1. Актуальность задачи распознавания автоматных моделей обусловлена их многочислен-
ными применениями при решении задач преобразования информации. Высокая сложность
этой задачи стимулировала исследования приближенных методов ее решения, анализ ко-
торых содержится в [1]. Многочисленные попытки применения автоматно-алгебраических
моделей при анализе современных шифров [2] выделяют в качестве новой актуальной зада-
чи распознавание конечного автомата, представленного системой уравнений с параметрами
над конечным ассоциативно-коммутативным кольцом K = (K,+, ·) с единицей. Анализ этой
задачи дает возможность установить глубокие внутренние связи между современной алгеб-
рой, теорией систем, теорией автоматов и криптологией.
2. Зафиксируем числа l, n1, n2, n3 ∈ N, множество A ⊆ K l (|A| > 1) и отображения
f1 : K
n1+n2+l → Kn1 и f2 : K
n1+n2+l → Kn3 . Система уравнений
{
qt+1 = f1(qt,xt+1,a),
yt+1 = f2(qt,xt+1,a)
(t ∈ Z+) (1)
определяет над кольцом K такое семейство конечных автоматов M = {Ma}a∈A, что для
каждого значения параметров a ∈ A элементы qt ∈ Kn1 , xt ∈ Kn2 и yt ∈ Kn3 являют-
ся, соответственно, состоянием, входным символом и выходным символом автомата Ma
в момент t.
Обозначим через Fa,q0
(a ∈ A,q0 ∈ Kn1) отображение множества входных слов (Kn2)+
в множество выходных слов (Kn3)+, реализуемое инициальным автоматом (Ma,q0). Ясно,
что каждому автомату Ma (a ∈ A) может быть поставлено в соответствие семейство авто-
матных отображений Fa = {Fa,q0
}q0∈K
n1 .
Расстоянием (по Хеммингу) между словами v = u
(1)
1 . . . u(1)m и w = u
(2)
1 . . . u(2)m в алфа-
вите U , где u
(i)
j ∈ U (i = 1, 2; j = 1, . . . ,m), назовем количество ̺(v,w) таких позиций i
(1 6 i 6 m), что u
(1)
i 6= u
(2)
i .
Рассмотрим следующую задачу распознавания автомата над кольцом K.
Дан автомат M , о котором известно только то, что M ∈ M. Требуется на основе
(возможно, кратного) эксперимента с автоматом M построить его следствие, т. е. автомат-
но-алгебраическую модель, которая с заданной точностью моделирует поведение автома-
та M на множестве входных слов (Kn2)+.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2012, №9 29
Таким образом, предметом настоящего исследования является построение имитацион-
ной модели для семейства автоматов (1), т. е. алгоритма, основанного на использовании
некоторого семейства автоматов над кольцом K, более простого, чем семейство M, осу-
ществляющего моделирование поведения любого автомата Ma ∈ M с заданной точностью.
3. Построим имитационную модель семейства автоматов M следующим образом.
Зафиксируем числа r, l1 ∈ N, непустое множество B ⊆ K l1 (|B| 6 |A|) и три семейства
отображений
{ϕ
(1)
b : Kn1 ×Kn2 → Kn3}b∈B,
{
ϕ
(2)
b : Kn1 ×
(
r−1⋃
j=1
Kn3
)j
×Kn2 → Kn3
}
b∈B
,
{ϕ
(3)
b
: Kn1 × (Kn3)r ×Kn2 → Kn3}b∈B.
Рассмотрим семейство таких отображений
GB = {Gb : K
n1 × (Kn2)+ → (Kn3)+}b∈B,
что Gb(q0,x1 . . .xm) = y1 . . . ym (b ∈ B,m ∈ N), где
yi =
ϕ
(1)
b (q0,x1), если i = 1,
ϕ
(2)
b (q0,y1 . . .yi−1,xi), если i = 2, . . . , r,
ϕ
(3)
b (q0,yi−r . . .yi−1,xi), если r < i 6 m,
(2)
для любых q0 ∈ Kn1 и x1 . . .xm ∈ (Kn2)+.
Определим отображения Hb,q0
: (Kn2)+ → (Kn3)+ (b ∈ B,q0 ∈ Kn1) следующим обра-
зом: Hb,q0
(x1 . . . xm) = Gb(q0,x1 . . .xm) для любых x1 . . .xm ∈ (Kn2)+ (m ∈ N).
Из (2) вытекает, что Hb,q0
(b ∈ B,q0 ∈ Kn1) — автоматные отображения, причем каждое
семейство автоматных отображений Hb = {Hb,q0
}q0∈K
n1 (b ∈ B) определяет конечный
автомат над кольцом K.
Зафиксировав сюръекцию h : A → B, мы можем каждому автомату Ma ∈ M поставить
в соответствие автомат, определяемый семейством автоматных отображений Hh(a).
Таким образом, упорядоченная пара (GB, h) может быть выбрана в качестве имитацион-
ной модели семейства автоматов M, если выполнены следующие три условия:
1) построение семейства отображений GB и сюръекции h осуществляется только на осно-
ве анализа системы уравнений (1) без дополнительных ограничений на значения параметра
a ∈ A;
2) для каждого фиксированного значения параметра a ∈ A сложность вычислений
в соответствии с семейством отображений Fa не меньше, чем сложность вычислений в со-
ответствии с семейством отображений Hh(a);
3) для каждого фиксированного значения параметра a ∈ A автомат, определяемый
семейством автоматных отображений Hh(a), моделирует поведение автомата Ma ∈ M с за-
данной точностью.
Ясно, что те или иные ограничения на структуру отображений ϕ
(1)
b , ϕ
(2)
b , ϕ
(3)
b (b ∈ B)
накладывают соответствующие ограничения на каждое семейство автоматных отображений
Hb и, следовательно, на структуру автомата, определяемого этим семейством.
30 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2012, №9
Естественно потребовать, чтобы для имитационной модели (GB, h) отображения ϕ
(1)
h(a)
и ϕ
(2)
h(a) были выбраны так, чтобы истинными были равенства
Hh(a),q0
∣∣
r⋃
i=1
Kn2
= Fa,q0
∣∣
r⋃
i=1
Kn2
(a ∈ A,q0 ∈ Kn1). (3)
Содержательный смысл равенств (3) состоит в следующем: имитационная модель
(GB, h), подсоединенная к входу и выходу исследуемого автомата Ma (a ∈ A), пропускает
первые r выходных символов, после чего блокирует выход автомата Ma и начинает моде-
лировать его поведение на оставшейся части входного слова. Всюду в дальнейшем считаем,
что это условие выполнено.
Среди ограничений на структуру отображений ϕ
(3)
b (b ∈ B) с прикладной точки зре-
ния представляет интерес следующее ограничение: для каждого отображения ϕ
(3)
b
(b ∈ B)
переменная q0 является фиктивной. Это ограничение означает, что имитационная модель
(GB, h) осуществляет моделирование поведения каждого автомата Ma (a ∈ A) посредством
использования автоматов с конечной памятью.
4. Определим точность имитационной модели (GB, h), используя стандартный подход
прикладной теории алгоритмов [3, 4].
Пусть Fa,q0
(x . . .xm) = y1 . . .ym и Hh(a),q0
(x . . . xm) = ỹ1 . . . ỹm, где q0 ∈ Kn1 , a ∈ A
и x1 . . .xm ∈ (Kn2)m (m ∈ N).
Число
αa,q0,m =
∑
x1...xm∈(Kn2 )m
(m− ̺(y1 . . .ym, ỹ1 . . . ỹm)) (a ∈ A, q0 ∈ Kn1 , m ∈ N)
является средним количеством позиций в выходных словах, в которых отображения Fa,q0
и Hh(a),q0
совпадают на множестве входных слов длины m. Отсюда вытекает, что число
βa,q0,m = m−1αa,q0,m (a ∈ A, q0 ∈ Kn1 , m ∈ N)
является средним количеством позиций в выходных словах, приходящимся на одну букву
входного слова, в которых отображения Fa,q0
и Hh(a),q0
совпадают на множестве входных
слов длины m. Следовательно, число
γa,q0,m =
|Kn2 | − 1
|Kn2 |m+1 − |Kn2 |
m∑
i=1
|Kn2 |iβa,q0,m (a ∈ A, q0 ∈ Kn1 , m ∈ N)
является средним количеством позиций в выходных словах, приходящимся на одну букву
входного слова, в которых отображения Fa,q0
и Hh(a),q0
совпадают на множестве всех вход-
ных слов длины, не превосходящей число m.
Числа
γ
a,q0
= limγa,q0,m = lim
m→∞
inf{γa,q0,i | i ∈ Nm} (a ∈ A,q0 ∈ Kn1)
и
γa,q0
= limγa,q0,m = lim
m→∞
sup{γa,q0,i | i ∈ Nm} (a ∈ A,q0 ∈ Kn1)
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2012, №9 31
определяют, соответственно, нижнюю и верхнюю границу для среднего количества позиций
в выходных словах, приходящегося на одну букву входного слова, в которых отображения
Fa,q0
и Hh(a),q0
совпадают на своей области определения (Kn2)+.
Следовательно, для каждого a ∈ A:
1) числа η
a
= min
q0∈K
n1
γ
a,q0
и ηa = max
q0∈K
n1
γa,q0
определяют, соответственно, нижнюю
и верхнюю границу для среднего количества позиций в выходных словах, приходящегося на
одну букву входного слова, в которых отображения, принадлежащие семейству отображе-
ний Fa, реализуемых автоматом Ma ∈ M, совпадают с соответствующими отображениями,
принадлежащими семейству отображений Hh(a);
2) если γ
a,q0
= γa,q0
= γa,q0
для всех q0 ∈ Kn1 , то:
а) число ηa = min
q0∈K
n1
γa,q0
определяет в наихудшем случае среднее количество пози-
ций в выходных словах, приходящееся на одну букву входного слова, в которых отобра-
жения, принадлежащие семейству отображений Fa, реализуемых автоматом Ma ∈ M,
совпадают с соответствующими отображениями, принадлежащими семейству отображе-
ний Hh(a);
б) число ζa = |Kn1 |−1 ∑
q0∈K
n1
γa,q0
определяет в среднем количество позиций в выходных
словах, приходящееся на одну букву входного слова, в которых отображения, принадлежа-
щие семейству отображений Fa, реализуемых автоматом Ma ∈ M, совпадают с соответст-
вующими отображениями, принадлежащими семейству отображений Hh(a).
Таким образом,
1) числа η = min
a∈A
η
a
и η = max
a∈A
η
a
определяют, соответственно, нижнюю и верхнюю
границу для среднего количества позиций в выходных словах, приходящегося на одну бу-
кву входного слова, в которых автоматные отображения, реализуемые семейством автома-
тов M, совпадают с автоматными отображениями, реализуемыми имитационной моделью
(GB, h);
2) если γ
a,q0
= γa,q0
= γa,q0
для всех q0 ∈ Kn1 и a ∈ A, то
а) число ν1 = min
a∈A
ηa определяет в наихудшем случае среднее количество позиций в выхо-
дных словах, приходящееся на одну букву входного слова, в которых автоматные отобра-
жения, реализуемые семейством автоматов M, совпадают с автоматными отображениями,
реализуемыми имитационной моделью (GB, h);
б) число ν2 = |A|−1 ∑
a∈A
ηa определяет среднее для наихудших случаев от средних ко-
личеств позиций в выходных словах, приходящихся на одну букву входного слова, в кото-
рых автоматные отображения, реализуемые семейством автоматов M, совпадают с авто-
матными отображениями, реализуемыми имитационной моделью (GB, h);
в) число ν3 = min
a∈A
ζa определяет наихудший случай для средних от средних количеств
позиций в выходных словах, приходящееся на одну букву входного слова, в которых ав-
томатные отображения, реализуемые семейством автоматов M, совпадают с автоматными
отображениями, реализуемыми имитационной моделью (GB, h);
г) число ν4 = |A|−1 ∑
a∈A
ζa определяет среднее от средних количеств позиций в выходных
словах, приходящееся на одну букву входного слова, в которых автоматные отображения,
реализуемые семейством автоматов M, совпадают с автоматными отображениями, реали-
зуемыми имитационной моделью (GB, h).
32 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2012, №9
Рассмотренные случаи охватывают все представляющие интерес комбинации понятий
“в наихудшем случае” и “в среднем” и дают возможность охарактеризовать имитационную
модель (GB, h) как [η, η]-точную или, в случае, когда γ
a,q0
= γa,q0
для всех q0 ∈ Kn1
и a ∈ A, как ν-точную, где ν — любое из чисел ν1, ν2, ν3 или ν4. Естественно определить
имитационную модель (GB, h) как асимптотически точную, если ν = 1.
5. Проиллюстрируем построение имитационной модели (GB, h) на примере семейства
автоматов M с лагом 2, определенного над кольцом K системой уравнений
{
qt+2 = a1 + a2q
2
t+1 + a3qt + a4xt+1,
yt+1 = a5qt+2,
(t ∈ Z+), (4)
где множество параметров имеет вид
A = {(a1, a2, a3, a4, a5) | a1, a2, a3 ∈ K \ {0}; a4, a5 ∈ Kinv}.
При каждом фиксированном a ∈ A для автомата Ma ∈ M вектор qt = (qt+1, qt) — состояние
в момент t, а xt+1 и yt+1 — соответственно, входной и выходной символы в момент t + 1.
Таким образом, для рассматриваемого примера l = 5, n1 = 2, а n2 = n3 = 1.
Отметим, что уравнение
qt+2 = a1 + a2q
2
t+1 + a3qt + a4
определяет над кольцом K аналоги ряда модельных хаотических динамических систем [5],
в том числе отображения Эно.
Подставив значение qt+2, определенное 1-м уравнением системы (4), во 2-е уравнение
этой системы, получим
yt+1 = a1a5 + a2a5q
2
t+1 + a3a5qt + a4a5xt+1. (5)
Подставив t = 0, 1, . . . в (5), учитывая 2-е уравнение системы (4) и то обстоятельство,
что a4 ∈ Kinv, получим, что для каждого автомата Ma ∈ M система уравнений (4) экви-
валентна системе уравнений
y1 = a1a5 + a2a5q
2
1 + a3a5q0 + a4a5x1,
y2 = a1a5 + a2a
−1
5 y21 + a3a5q1 + a4a5x2,
yt+1 = a1a5 + a2a
−1
5 y2t+1 + a3yt + a4a5xt+1,
(t > 2), (6)
Из (6) вытекает, что для семейства автоматов M, представленного над кольцом K си-
стемой уравнений (4), система уравнений
y1 = b1 + b2q
2
1 + b3q0 + b4x1,
y2 = b1 + b5y
2
1 + b3q1 + b4x2,
yt+1 = b1 + b5y
2
t+1 + b6yt + b4xt+1,
(t > 2), (7)
где
b1 = a1a5, b2 = a2a5, b3 = a3a5, b4 = a4a5, b5 = a2a
−1
5 , b6 = a3, (8)
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2012, №9 33
определяет для каждого ν ∈ {ν1, ν2, ν3, ν4} асимптотически точную имитационную модель
(GB, h) (B ⊂ K6). Таким образом, l1 = 6, r = 2, а отображение h : A → B, определенное
равенствами (8), является биекцией (т. е. условие |B| 6 |A| выполнено).
Для каждого a ∈ A значение h(a) = (b1, . . . , b6) вычисляется следующим образом. Осу-
ществляется поиск входного слова x1 . . . xm ∈ Km (m > 6) заранее неизвестной длины,
которое дает возможность сформировать в результате эксперимента с автоматом Ma ∈ M
систему линейных уравнений
b1 + b2q
2
1 + b3q0 + b4x1 = y1,
b1 + b5y
2
1 + b3q1 + b4x2 = y2,
b1 + b5y
2
2 + b6y1 + b4x3 = y3,
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
b1 + b5y
2
m−1 + b6ym−2 + b4xm = ym
относительно неизвестных b1, . . . , b6, ранг матрицы которой равен 6. Решив эту систему,
найдем значения b1, . . . , b6.
Так как a4 ∈ Kinv, то из (4) вытекает, что M — семейство обратимых автоматов, причем
для каждого автомата Ma ∈ M обратный автомат M−1
a имеет следующий вид:
{
qt+2 = a−1
5 yt+1,
xt+1 = −a1a
−1
4 − a2a
−1
4 q2t+1 − a3a
−1
4 qt + a−1
4 a−1
5 yt+1
(t ∈ Z+).
Из (7) вытекает, что для семейства автоматов M−1 = {M−1}a∈A асимптотически точная
для каждого ν ∈ {ν1, ν2, ν3, ν4} имитационная модель (G−1
B , h) (B ⊂ K6) имеет вид
x1 = −b−1
4 b1 − b−1
4 b2q
2
1 − b−1
4 b3q0 + b−1
4 y1,
x2 = −b−1
4 b1 − b−1
4 b5y
2
1 − b−1
4 b3q1 + b−1
4 y2,
xt+1 = b−1
4 b1 − b−1
4 b5y
2
t+1 − b−1
4 b6yt + b−1
4 yt+1
(t > 2). (9)
Отметим, что если упорядоченная пара (Ma,M
−1
a ) (Ma ∈ M) используется в качест-
ве математической модели симметричного поточного шифра (в этом случае параметры
a1, . . . , a5 играют роль долговременного секретного ключа, а начальное состояние q0 — роль
секретного сеансового ключа), то имитационные модели (GB, h) и (G−1
B , h) предоставляют
криптоаналитику большие возможности для вмешательства как в процесс шифрования ин-
формации, так и в процесс расшифрования.
6. Таким образом, разработан подход к приближенному решению задачи идентифи-
кации семейств автоматов, представленных системами уравнений с параметрами над коль-
цом K. Выделение над кольцом K нетривиальных классов семейств автоматов, для которых
построение любой достаточно точной имитационной модели — трудная задача, а также не-
тривиальных классов семейств автоматов, для которых построение некоторой достаточно
точной имитационной модели — легкая задача, представляет собой одно из направлений
исследований. Другое направление исследований связано с выделением над кольцом K не-
тривиальных классов семейств автоматов, для которых существуют такие [η, η]-точные ими-
тационные модели, для которых |η − η| < ε, где ε — заданное положительное число.
34 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2012, №9
1. Бабаш А.В. Приближенные модели конечных автоматов // Обозрение прикл. и промышл. матема-
тики. – 2005. – 12, вып. 2. – С. 108–117.
2. Харин Ю.С., Берник В.И., Матвеев Г. В. и др. Математические и компьютерные основы криптоло-
гии. – Минск: Новое знание, 2003. – 382 с.
3. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – Москва:
Мир, 1979. – 536 с.
4. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы: теория и практика. – Москва:
Мир, 1980. – 476 с.
5. Кузнецов С.П. Динамический хаос. – Москва: Физматлит, 2001. – 296 с.
Поступило в редакцию 22.12.2011Институт прикладной математики
и механики НАН Украины, Донецк
В.В. Скобелєв
Аналiз задачi розпiзнавання автомата над кiльцем
Розроблено метод наближеного розв’язання задачi iдентифiкацiї сiмей автоматiв, наведе-
них системами рiвнянь з параметрами над скiнченним асоцiативно-комутативним кiль-
цем з одиницею. Запропонований метод базується на побудовi iмiтацiйної моделi для до-
слiджуваної сiм’ї автоматiв. Видiлено iмiтацiйнi моделi, якi моделюють поведiнку сiм’ї
автоматiв з заданою точнiстю у “найгiршому випадку” та “у середньому”.
V.V. Skobelev
Analysis of the problem of recognition of an automaton over some ring
A method of approximate solution of the problem of identification for families of automata presented
by systems of equations with parameters over a finite associative-commutative ring with unity is
proposed. The method is based on the construction of a simulation model for the family of automata
under study. The models simulating the behavior of such family with given exactness “in the worst
case” and “on the average” are separated.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2012, №9 35
|