Группы RS-автоматных преобразований
Досліджено RS-автомати та групи, ними визначені. Встановлено зв'язки між групами лінійних RS-автоматних перетворень та групами нескінченних унітрикутних матриць.
Збережено в:
| Дата: | 2010 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Видавничий дім "Академперіодика" НАН України
2010
|
| Назва видання: | Доповіді НАН України |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/30785 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Группы RS-автоматных преобразований / А.С. Олийнык // Доп. НАН України. — 2010. — № 11. — С. 12-17. — Бібліогр.: 6 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-30785 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-307852012-02-15T12:07:40Z Группы RS-автоматных преобразований Олийнык, А.С. Математика Досліджено RS-автомати та групи, ними визначені. Встановлено зв'язки між групами лінійних RS-автоматних перетворень та групами нескінченних унітрикутних матриць. RS-automata and groups defined by them are investigated. Connections between the groups of linear RS-automaton transformations and the groups of infinite unitriangular matrices are established. 2010 Article Группы RS-автоматных преобразований / А.С. Олийнык // Доп. НАН України. — 2010. — № 11. — С. 12-17. — Бібліогр.: 6 назв. — рос. 1025-6415 http://dspace.nbuv.gov.ua/handle/123456789/30785 512.54 ru Доповіді НАН України Видавничий дім "Академперіодика" НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Математика Математика |
| spellingShingle |
Математика Математика Олийнык, А.С. Группы RS-автоматных преобразований Доповіді НАН України |
| description |
Досліджено RS-автомати та групи, ними визначені. Встановлено зв'язки між групами лінійних RS-автоматних перетворень та групами нескінченних унітрикутних матриць. |
| format |
Article |
| author |
Олийнык, А.С. |
| author_facet |
Олийнык, А.С. |
| author_sort |
Олийнык, А.С. |
| title |
Группы RS-автоматных преобразований |
| title_short |
Группы RS-автоматных преобразований |
| title_full |
Группы RS-автоматных преобразований |
| title_fullStr |
Группы RS-автоматных преобразований |
| title_full_unstemmed |
Группы RS-автоматных преобразований |
| title_sort |
группы rs-автоматных преобразований |
| publisher |
Видавничий дім "Академперіодика" НАН України |
| publishDate |
2010 |
| topic_facet |
Математика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/30785 |
| citation_txt |
Группы RS-автоматных преобразований / А.С. Олийнык // Доп. НАН України. — 2010. — № 11. — С. 12-17. — Бібліогр.: 6 назв. — рос. |
| series |
Доповіді НАН України |
| work_keys_str_mv |
AT olijnykas gruppyrsavtomatnyhpreobrazovanij |
| first_indexed |
2025-07-03T11:09:48Z |
| last_indexed |
2025-07-03T11:09:48Z |
| _version_ |
1836623843738779648 |
| fulltext |
УДК 512.54
© 2010
А.С. Олийнык
Группы RS-автоматных преобразований
(Представлено членом-корреспондентом НАН Украины В.В. Шарко)
Дослiджено RS-автомати та групи, ними визначенi. Встановлено зв’язки мiж гру-
пами лiнiйних RS-автоматних перетворень та групами нескiнченних унiтрикутних
матриць.
1. Автоматы-преобразователи (синхронные или асинхронные) были введены в рассмотрение
прежде всего в связи с потребностями математического моделирования вычислительных
процессов. Алфавиты, над которыми рассматривались такие автоматы, предполагались ко-
нечными [1]. Позже сфера применений автоматов-преобразователей была существенно рас-
ширена за счет алгебры, геометрии, теории динамических систем и других разделов мате-
матики [2, 3]. С этой точки зрения конечность алфавитов не является необходимым ограни-
чением и естественно возникает потребность рассматривать автоматы над произвольными
алфавитами. При этом, учитывая прежде всего алгебраические аспекты исследований, при-
ходится накладывать иные ограничения как на алфавиты, так и на функции выходов и пе-
реходов автоматов.
Данное сообщение посвящено синхронным автоматам-преобразователям над алфави-
том R, который наделен структурой коммутативного кольца. Вводится понятие RS-авто-
мата и рассматривается группа GAS(R) преобразований, определяемых RS-автоматами.
Показано, что она раскладывается в бесконечно итерированное сплетение регулярных ад-
дитивных групп кольца R. Доказано, что каждая неединичная подстановка из этой группы
не имеет нетривиальных циклов конечной длины. Выделяются естественные подгруппы
в группе GAS(R). К ним относятся подгруппа конечно RS-автоматных преобразований,
подгруппы полиномиальных и линейных преобразований. Изучены связи между группой
линейных RS-автоматных преобразований и группой бесконечных унитреугольных матриц
над кольцом R. Охарактеризована подгруппа конечно RS-автоматных линейных преобра-
зований.
2. Пусть R — коммутативное кольцо с единицей, которое мы рассматриваем как алфа-
вит. Cимволом R∗ обозначается множество всех слов над алфавитом R, e — пустое слово,
а символом Rω — множество всех ω-слов над R. Длину слова u ∈ R∗ будем обозначать |u|.
Конкатенацией слова u = t1 . . . tm и слова (либо ω-слова) v = z1 . . . zn . . . называется слово
(соответственно, ω-слово) u · v = t1 . . . tmz1 . . . zn . . .. Слово u называется подсловом слова
(или ω-слова) w, если существуют слово v1 и слово (соответственно, ω-слово) v2 такие, что
w = v1uv2. Если при этом v1 = e, то слово u называется префиксом w.
Напомним, что синхронным автоматом над алфавитом R называется четверка
A = 〈R,Q,ϕ, ψ〉,
где Q — непустое множество, множество внутренних состояний автомата A; ϕ : R×Q→ Q —
функция переходов автомата A; ψ : R ×Q → R — функция выходов автомата A.
12 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2010, №11
Автомат A называется конечным, если множество его внутренних состояний конечно,
и бесконечным — в противном случае.
Функции ϕ и ψ распространяются на множество R∗×Q согласно следующим рекурент-
ным соотношениям:
ϕ(e, q) = q, ϕ(uz, q) = ϕ(z, ϕ(u, q))
ψ(e, q) = e, ψ(uz, q) = ψ(z, ϕ(u, q)),
где q ∈ Q, z ∈ R и u ∈ R∗. По расширенной функции ψ : R∗ × Q → R∗ для каждого q ∈ Q
определяется отображение fA,q : R
∗ → R∗ или fA,q : R
ω → Rω следующим образом. Для
любого слова z1z2 . . . zn ∈ R∗ положим
fA,q(z1z2 . . . zn) = ψ(z1, q)ψ(z1z2, q) . . . ψ(z1z2 . . . zn, q).
Если же u = z1z2 . . . — ω-слово, то
fA,q(u) = ψ(z1, q)ψ(z1z2, q) . . . .
Отображение fA,q называется преобразованием множества R∗ (или, соответственно, Rω),
определяемым автоматом A в состоянии q.
Преобразование f : R∗ → R∗ или f : Rω → Rω будем называть автоматным преобразо-
ванием, если существует автомат A над алфавитом R и состояние q этого автомата такие,
что f = fA,q. Если при этом автомат A является конечным, то f называют конечно автома-
тным преобразованием. Имеет место аналог хорошо известного [4] критерия автоматности.
А именно, преобразование f : R∗ → R∗ будет автоматным в том и только том случае, когда
оно удовлетворяет таким двум условиям:
а) f сохраняет длины слов;
б) f не уменьшает длину общего начала слов.
Символом Πn обозначим оператор вычеркивания первых n букв в словах из R∗ или
ω-словах их Rω. Для автоматного отображения f : R∗ → R∗ определим его состояние в слове
u ∈ R∗ как отображение fu : R
∗ → R∗, значение которого на произвольном слове v ∈ R∗
определяется равенством
fu(v) = Π|u|f(uv).
Множество всех состояний автоматного отображения f обозначим R(f). Тогда, как и в [4],
можно показать, что отображение f : Z∗ → Z∗, удовлетворяющее условиям а, б, будет ко-
нечно автоматным в том и только том случае, когда множество R(f) конечно.
Функция выходов ψ автомата A определяет для каждого состояния q ∈ Q некоторое
преобразование алфавита R, которое будем обозначать ψq, т. е.
ψq(r) = ψ(r, q), r ∈ R.
Автомат A называется групповым или подстановочным автоматом, если для любого состо-
яния q ∈ Q функция ψq является биекцией множества R.
Определение 1. Подстановочный автомат A = 〈R,Q,ϕ, ψ〉 называется RS-автоматом,
если в любом состоянии q ∈ Q функция ψq является сдвигом на некоторый элемент sq ∈ R:
ψq(r) = r + sq, r ∈ R.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2010, №11 13
Лемма 1. Каждое преобразование множества R∗ или Rω, задаваемое подстановочным
автоматом, обратимо, причем обратное также задается некоторым подстановочным
автоматом. Преобразование, обратное к преобразованию, заданному RS-автоматом, так-
же задается RS-автоматом.
Доказательство. Пусть A = 〈R,Q,ϕ, ψ〉 — некоторый подстановочный автомат. Это
означает, что для каждого состояния q ∈ Q функция ψq : R → R является обратимой.
Определим новый автомат A1 = 〈R,Q,ϕ1, ψ1〉 с тем же множеством внутренних состояний,
функции выходов и переходов которого определяются согласно равенствам:
ϕ1(r, q) = ϕ(ψ−1
q (r), q), ψ1(r, q) = ψ−1
q (r), r ∈ R, q ∈ Q.
Заметим, что построенный автомат будет подстановочным, а в случае, если A является
RS-автоматом, то и A1 также будет RS-автоматом. Непосредственная проверка показывает,
что для каждого q ∈ Q обе суперпозиции fA1,q(fA,q) и fA,q(fA1,q) являются тождественными
преобразованиями, откуда следуют утверждения леммы.
На множестве всех автоматов над алфавитом R определим операцию их суперпозиции.
Определение 2. Суперпозицией автоматов A1 = 〈R,Q1, ϕ1, ψ1〉 и A2 = 〈R,Q2, ϕ2, ψ2〉
называется автомат A1 ∗A2 = 〈R,Q,ϕ, ψ〉 такой, что Q = Q1×Q2, а его функции переходов
и выходов определяются равенствами
ϕ(r, (q1, q2)) = (ϕ1(r, q1), ϕ2(ψ1(r, q1), q2)),
ψ(r, (q1, q2)) = ψ2(ψ1(r, q1), q2).
Автомат A1 ∗A2 обрабатывает слова или ω-слова посимвольно так, что вначале символ
алфавита R перерабатывается автоматом A1, а затем полученный символ — автоматом A2.
Заметим, что суперпозиция RS-автоматов снова будет RS-автоматом.
Операция суперпозиции автоматов представляет интерес в связи со следующим хорошо
известным утверждением.
Лемма 2. Предположим, что автоматы A1 = 〈R,Q1, ϕ1, ψ1〉 и A2 = 〈R,Q2, ϕ2, ψ2〉
в состояниях q1 ∈ Q1 и q2 ∈ Q2 определяют функции fA1,q1 и fA2,q2. Тогда их суперпозиция
A1 ∗A2 в состоянии (q1, q2) определяет функцию fA1∗A2,(q1,q2), являющуюся суперпозицией
fA2,q2(fA1,q1).
Отсюда как следствие получаем, что множество всех RS-автоматных преобразований
на R∗ или Rω образует группу. Как абстрактные группы группа RS-автоматных преобра-
зований множества R∗ и группа RS-автоматных преобразований множества Rω изоморфны
между собой. Будем обозначать так определяемую абстрактную группу GAS(R).
В дальнейшем образ элемента x ∈ X под действием подстановки g на множестве X будем
обозначать xg, т. е. будем придерживаться правосторонней записи действия подстановки на
элемент.
Группа GAS(R) может быть получена из аддитивной группы кольца R с помощью кон-
струкции бесконечно итерированного сплетения групп подстановок. Напомним соответст-
вующее определение [5].
Определение 3. Сплетением по бесконечной последовательности групп подстановок
(G1,X1), (G2,X2), . . . называется группа всевозможных преобразований g декартова прои-
зведения X =
∏
i>1
Xi, которое для каждого i > 1 удовлетворяет таким двум условиям:
1) i-тая координата yi образа (x1, x2, . . .)
g = (y1, y2, . . .) зависит только от i первых
координат элемента (x1, x2, . . .) ∈ X;
14 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2010, №11
2) если зафиксировать первые i − 1 координат x01, x
0
2, . . . , x
0
i−1, то преобразование gi
множества Xi, определяемое равенством
(x01, x
0
2, . . . , x
0
i−1, xi, . . .)
g = (y01 , y
0
2 , . . . , y
0
i−1, x
gi
i , . . .),
принадлежит группе Gi.
Обозначим сплетение по бесконечной последовательности (G1,X1), (G2,X2), . . . симво-
лом
∞
≀
i=1
Gi.
Из условий 1 и 2 определения сплетения следует, что любое преобразование g ∈
∞
≀
i=1
Gi
определяет бесконечную последовательность g1, g2, . . . , где g1 ∈ G1, gi : X1×· · ·×Xi−1 → Gi
(i > 2). Обратно, каждая такая последовательность определяет преобразование декартового
произведения
∞
∏
i=1
Xi, удовлетворяющее условиям 1 и 2. А именно, последовательности такого
вида можно охарактеризовать бесконечными кортежами, которые, следуя Л.А. Калужнину,
называют таблицами:
g = [g1, g2(x1), g3(x1, x2), . . .], (1)
где g1 ∈ G1, gi : X1 × . . .×Xi−1 → Gi (i > 2). Таблица (1) действует на последовательность
u = (t1, t2, . . .) ∈
∞
∏
i=1
Xi согласно правилу
ug = (tg11 , t
g2(t1)
2 , t
g3(t1,t2)
3 ). (2)
Пусть R(i), i ∈ N — копия алфавита R. Счетную декартову степень
∞
∏
i=1
R(i) алфавита R
естественным образом отождествим с множеством Rω всех ω-слов над R. Тогда сплетение
∞
≀
i=1
(R,+)(i) регулярных аддитивных групп (R,+)(i), i ∈ N, кольца R действует на множе-
стве Rω согласно равенству (2).
Теорема 1. Группа RS-автоматных преобразований GAS(R) совпадает со сплетением
по бесконечной последовательности регулярных аддитивных групп кольца R:
GAS(R) =
∞
≀
i=1
(R,+)(i).
Теорема 2. Если группа (R,+) без кручения, то в группе подстановок (GAS(R), R
∞)
каждая неединичная подстановка не имеет конечных циклов длины, большей 1.
3. Выделим в группе GAS(R) несколько естественных подгрупп, пользуясь условия-
ми, которые аналогичны ранее возникавшим в теории групп автоматных подстановок над
конечными алфавитами.
Если преобразования f1, f2 множества R∞ определяются конечными RS-автоматами, то
из доказательства леммы 1 и леммы 2 следует, что их суперпозиция и обратные к ним также
задаются конечными RS-автоматами. Поэтому все конечно RS-автоматные преобразования
образуют подгруппу в GAS(R), которую будем обозначать символом FGAS(R).
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2010, №11 15
В терминах таблиц она может быть охарактеризована следующим образом. Для любой
таблицы
u = [g1, g2(x), . . .] ∈ GAS(R)
и слова t = z1 . . . zs ∈ R∗ осуществим подстановку t в u. Получим последовательность вида
[g1, g2(z1), . . . , gs+1(z1, . . . , zs), gs+2(z1, . . . , zs, xs+1), . . .].
Отбрасывая первые s членов этой последовательности и меняя названия переменных, по-
лучаем новую таблицу
ut = [h1, h2(x1), . . .],
h1 = gs+1(z1, . . . , zs), hk(x1, . . . , xk−1) = gs+k(z1, . . . , zs, x1, . . . , xk−1) (k > 2). Таблицу ut
назовем t-остатком таблицы u, а множество всех остатков u обозначим символом R(u):
R(u) = {ut | t ∈ R∗}.
Лемма 3. Таблица u определяет конечно автоматное преобразование множества R∞
тогда и только тогда, когда множество R(u) конечно.
Обозначим символом ∆ оператор вычеркивания первого члена последовательности (или
первой буквы слова или ω-слова), т. е. если t = (t1, t2, t3, . . .), то ∆t = (t2, t3, . . .). Применяя ∆
повторно k раз подряд (k > 0), получаем последовательность ∆kt = (tk+1, tk+2, . . .).
Напомним что последовательность t = (t1, t2, t3, . . .) (или ω-слово t1t2t3 . . .) называется
остаточно периодической, если существуют неотрицательное целое число m и натуральное
число n такие, что для всех k > m имеет место равенство tn+k = tk. Это равносильно
выполнению равенства ∆mt = ∆m+nt. Число m называется предпериодом, а n — периодом
остаточно периодической последовательности t. Пара чисел (m,n) определяется последо-
вательностью t неоднозначно. Среди всех таких пар выделяется такая пара (m0, n0), что
m0 — наименьшее возможное число, для которого последовательность ∆m0t является пе-
риодической, а n0 — минимальный период этой последовательности.
Лемма 4. Множество остаточно периодических ω-слов инвариантно относительно
действия группы FGAS(R).
Преобразование множества R∗ или R∞, определяемое таблицей из GAS(R), назовем
полиномиальным, если все координаты этой таблицы можно задать полиномами над коль-
цом R от соответствующего числа переменных. Такую таблицу также будем называть по-
линомиальной. Произведение полиномиальных преобразований и обратное к полиномиаль-
ному преобразованию также будут полиномиальными, т. е. все полиномиальные преобразо-
вания образуют подгруппу в GAS(R). Обозначим группу полиномиальных преобразований
символом PGAS(R).
Отметим, что в общем случае полиномиальное преобразование можно задать полино-
миальной таблицей не единственным способом. Если же кольцо R является простым полем
характеристики p, то группа PGAS(R) в этом случае совпадает с GAS(R) и является си-
ловской p-подгруппой группы всех автоматных подстановок над p-элементным алфавитом.
Таблицу из PGAS(R) назовем линейной, если все ее координаты являются линейными
многочленами, т. е. не содержат одночленов степени > 2. Ясно, что произведение линей-
ных таблиц и обратная к линейной таблице будут линейными, т. е. все линейные таблицы
16 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2010, №11
образуют группу. Будем называть ее группой линейных RS-автоматных преобразований
и обозначать LGAS(R).
Группа LGAS(R) допускает естественную матричную характеризацию. А именно,
пусть UT∞(R) — бесконечномерная унитреугольная матричная группа над кольцом R,
AffUT∞(R) = UT∞(R) ⋉ R∞ — соответствующая афинная группа. Группа AffUT∞(R)
действует на R-модуле R∞ согласно правилу
x(A,b) = xA+ b, x, b ∈ R∞, A ∈ UT∞(R).
Определение корректно, поскольку произведение последовательности на унитреугольную
матрицу в этом случае определено корректно.
Теорема 3. Группы подстановок (LGAS(R), R
ω) и (AffUT∞(R), R∞) изоморфны.
Таким образом, группу линейных RS-автоматных преобразований можно рассматри-
вать, как группу афинных унитреугольных преобразований и даже унитреугольных пре-
образований. Соответствующий изоморфизм группы AffUT∞(R) в группу UT∞(R) зада-
ется правилом
(A, b) 7→
(
1 b
0 A
)
,
где (A, b) ∈ AffUT∞(R),
(
1 b
0 A
)
∈ UT∞(R).
Охарактеризуем теперь группу линейных конечно RS-автоматных преобразований, т. е.
пересечение LGAS(R)
⋂
FGAS(R). В общем случае справедлива теорема, аналогичная те-
ореме 4.2 из работы [6]. Для бесконечного кольца R при некоторых дополнительных пред-
положениях имеет место следующая характеризация.
Теорема 4. Пусть в кольце R дополнения к аннуляторам всех ненулевых элементов
бесконечны. Пара (A, b), A ∈ UT∞(R), b ∈ R∞ определяет преобразование множества R∞,
содержащееся в FGAS(R), в том и только том случае, когда матрица A является еди-
ничной, а последовательность b — остаточно периодической.
1. Eilenberg S. Automata, languages and machines. Vol. A. – New York; London: Academic Press, 1974. –
452 p.
2. Григорчук Р.И., Некрашевич В. В., Сущанский В.И. Автоматы, динамические системы и группы //
Тр. Мат. ин-та им. В. А. Стеклова. – 2000. – 231. – С. 134–214.
3. Nekrashevych V. Self-similar groups. – Providence, RI: AMS, 2005. – 232 p.
4. Raney G.N. Sequential functions // J. Assoc. Comput. Mach. – 1958. – 5, No 2. – P. 177–180.
5. Kaloujnine L. A., Beleckij P.M., Fejnberg V. Z. Kranzprodukte. – Leipzig: Teubner, 1987. – 168 p.
6. Olijnyk A., Sushchansky V. Representations of free products by infinite unitriangular matrices over finite
fields // Int. J. Alg. Comput. – 2004. – 14, No 5–6. – P. 741–749.
Поступило в редакцию 12.03.2010Киевский национальный университет
им. Тараса Шевченко
A. S. Oliynyk
Groups of RS-automaton transformations
RS-automata and groups defined by them are investigated. Connections between the groups of linear
RS-automaton transformations and the groups of infinite unitriangular matrices are established.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2010, №11 17
|