Про мінімальну систему твірних у групі автоморфізмів бінарного кореневого дерева
Доведено iснування мiнiмальної системи твiрних у групi всiх автоморфiзмiв бiнарного кореневого дерева.
Збережено в:
| Дата: | 2012 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Видавничий дім "Академперіодика" НАН України
2012
|
| Назва видання: | Доповіді НАН України |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/84294 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Про мінімальну систему твірних у групі автоморфізмів бінарного кореневого дерева / Я.В. Лавренюк // Доп. НАН України. — 2012. — № 7. — С. 35-37. — Бібліогр.: 10 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-84294 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-842942015-07-07T03:02:25Z Про мінімальну систему твірних у групі автоморфізмів бінарного кореневого дерева Лавренюк, Я.В. Математика Доведено iснування мiнiмальної системи твiрних у групi всiх автоморфiзмiв бiнарного кореневого дерева. Доказано существование минимальной системы образующих в группе всех автоморфизмов бинарного корневого дерева. The existence of a basis in the full automorphism group of a binary rooted tree is proved. 2012 Article Про мінімальну систему твірних у групі автоморфізмів бінарного кореневого дерева / Я.В. Лавренюк // Доп. НАН України. — 2012. — № 7. — С. 35-37. — Бібліогр.: 10 назв. — укр. 1025-6415 http://dspace.nbuv.gov.ua/handle/123456789/84294 512.54 uk Доповіді НАН України Видавничий дім "Академперіодика" НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| topic |
Математика Математика |
| spellingShingle |
Математика Математика Лавренюк, Я.В. Про мінімальну систему твірних у групі автоморфізмів бінарного кореневого дерева Доповіді НАН України |
| description |
Доведено iснування мiнiмальної системи твiрних у групi всiх автоморфiзмiв бiнарного
кореневого дерева. |
| 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/84294 |
| citation_txt |
Про мінімальну систему твірних у групі автоморфізмів бінарного кореневого дерева / Я.В. Лавренюк // Доп. НАН України. — 2012. — № 7. — С. 35-37. — Бібліогр.: 10 назв. — укр. |
| series |
Доповіді НАН України |
| work_keys_str_mv |
AT lavrenûkâv promínímalʹnusistemutvírnihugrupíavtomorfízmívbínarnogokorenevogodereva |
| first_indexed |
2025-07-06T11:16:45Z |
| last_indexed |
2025-07-06T11:16:45Z |
| _version_ |
1836896081367007232 |
| fulltext |
УДК 512.54
© 2012
Я.В. Лавренюк
Про мiнiмальну систему твiрних у групi автоморфiзмiв
бiнарного кореневого дерева
(Представлено академiком НАН України М.О. Перестюком)
Доведено iснування мiнiмальної системи твiрних у групi всiх автоморфiзмiв бiнарного
кореневого дерева.
1. B. Csákány та F. Gécseg [1] в 1965 р. поставили питання — чи мають мiнiмальнi сис-
теми твiрних напiвгрупа всiх автоматних перетворень, напiвгрупа скiнченно-автоматних
перетворень, група всiх бiєктивних автоматних перетворень та група бiєктивних скiнчен-
но-автоматних перетворень над довiльним алфавiтом, який мiстить хоча б двi лiтери?
Невдовзi для напiвгруп була отримана негативна вiдповiдь. Це довели незалежно
С. Альошин [2] в 1970 р. та P. Dömösi [3] в 1972 р. Питання для груп залишається вiд-
критим i сьогоднi. Згадана проблема формулювалася також у роботах P. Dömösi, зокрема,
в [4, Problem 2.1].
З робiт, пов’язаних з даною проблемою, вiдзначимо роботу А. Олiйника [5], в якiй до-
водиться, що скiнченно становий вiнцевий добуток напiвгруп перетворень не є скiнченно
породженим i в певних випадках навiть не має мiнiмальної системи твiрних.
Також вiдзначимо ряд робiт про системи твiрних у проективних границях вiнцевих до-
буткiв груп, в яких вивчалися рiзнi аспекти скiнченної породженостi таких груп (як про-
скiнченних груп) [6–9].
Зауважимо, що група вс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тер.
2. Нехай X = {a, b} — алфавiт. Нагадаємо визначення дерева слiв TX над алфавiтом X.
Множина вершин V (TX) дерева слiв TX є множиною найможливiших послiдовностей ви-
гляду
i0i1 · · · in−1, ik ∈ X, n > 0, 0 6 k 6 n,
разом з порожньою послiдовнiстю Λ, яка вiдповiдає випадку n = 0. Вершини u, v ∈ V (TX)
з’єднуються ребром у деревi TX в тому i лише в тому випадку, коли одна з них є безпо-
середнiм продовженням iншої, тобто одна з них має вигляд i0 · · · in−1in, а iнша i0 · · · in−1,
ik ∈ X (0 6 k 6 n). Множина всiх слiв довжини n називається рiвнем номер n дерева TX .
Кожне бiнарне кореневе дерево iзоморфне дереву слiв над алфавiтом з двох елементiв.
Нехай v = i1 · · · in ∈ V (TX). Ми позначатимемо TX(v) повне пiддерево дерева TX , мно-
жина вершин якого є такою:
V (TX(v)) = {j1 · · · jk | k > n, j1 = i1, . . . , jn = in}.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2012, №7 35
Бiєкцiя
f : V (TX) → V (TX)
називається автоморфiзмом дерева слiв TX , якщо Λf = Λ i f зберiгає вiдношення iнци-
дентностi вершин. Множина всiх автоморфiзмiв дерева слiв TX утворює групу, яку ми
позначатимемо AutTX .
Група всiх автоморфiзмiв, якi фiксують всi вершини рiвня номер n, позначається Stab(n)
i називається стабiлiзатором рiвня номер n.
Якщо v ∈ V (T ), то множина всiх автоморфiзмiв g ∈ AutTX , якi фiксують кожну верши-
ну зовнi пiддерева TX(v), називається вершинною групою (або жорстким стабiлiзатором
вершини) i позначається rist v.
Поняття “жорсткий стабiлiзатор” та “вершинна група” належать Р. I. Григорчуку [10].
Говоритимемо, що елемент g є нетривiальною пiдстановкою у вершинi v, якщо g ∈ rist v
i для довiльного скiнченного слова w над алфавiтом X виконуються рiвностi g(vaw) = vbw
та g(vbw) = vaw.
Для кожного натурального i визначимо дiю групи C
(i)
2 порядку 2 на деревi TX таким
чином. Нетривiальний елемент g з C
(i)
2 визначається як нетривiальна пiдстановка у вершинi
aa · · · a
︸ ︷︷ ︸
i
b.
Нехай
C =
∏
i>1
C
(i)
2 .
Тодi C є пiдгрупою жорсткого стабiлiзатора rist a.
Група C має мiнiмальну систему твiрних (базис Гамеля) як лiнiйний простiр над полем
з двох елементiв.
Нехай також
R = (rist b)′.
Зауважимо, що так визначена група R iзоморфна комутанту всiєї групи AutTX .
Визначимо ще два елементи з AutTX : σ — нетривiальнапiдстановка у кореневiй верши-
нi Λ та σ0 = (σ, 1) — нетривiальна пiдстановка у вершинi a.
Нехай I — множина iндексiв, 1 ∈ I, B = {ci | i ∈ I} — мiнiмальна система твiрних C,
причому c1 — це нетривiальна пiдстановка у вершинi ab, а решта твiрних належать стабi-
лiзатору третього рiвня.
Зафiксуємо бiєкцiю φ : I → R i визначимо множину елементiв з AutTX :
H = {ciφ(i) : i ∈ I}.
Теорема 1. Множина
H
⋃
{σ, σ0}
є мiнiмальною системою твiрних групи AutTX .
1. Чакани К., Гечек Ф. О группе автоматных преобразований // Кибернетика. – 1965. – № 5. – С. 14–17.
36 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2012, №7
2. Алешин С. Об отсутствии базиса в определенных классах инициальных автоматов // Пробл. кибер-
нетики. – 1970. – 22. – С. 67–74.
3. Dömösi P. On the semigroup of automaton mappings with finite alphabet // Acta cybernetica. – 1972. –
1. – P. 251–254.
4. Dömösi P. Some of my favourite unsolved problems // Unsolved problems on mathematics for the 21st
century. – Amsterdam: IOS Press; Tokyo: Ohmsha, 2001. – P. 159–168.
5. Oliynyk A. Finite state wreath powers of transformation semigroups // Semigroup Forum. – 2011. – 82. –
P. 423–436.
6. Bhattacharjee M. The probability of generating certain profinite groups by two elements // Isr. J. Math. –
1994. – 86, No 1–3. – P. 311–329.
7. Quick M. Probabilistic generation of wreath products of non-Abelian finite simple groups // Commun.
Algebra. – 2004. – 32, No 12. – P. 4753–4768.
8. Bondarenko I.V. Finite generation of iterated wreath products // Arch. Math. – 2010. – 95, No 4. –
P. 301–308.
9. Lucchini A. Profinite groups with nonabelian crowns of bounded rank and their probabilistic zeta func-
tion // Isr. J. Math. – 2011. – 181. – P. 53–64.
10. Grigorchuk R. I. Just infinite branch groups // New Horizons in pro-p Groups / Ed. by A. Shalev, M.P. F. du
Sautoy, D. Segal. – Basel: Birkhäuser, 2000. – P. 121–179.
Надiйшло до редакцiї 01.07.2011Київський нацiональний унiверситет
iм. Тараса Шевченка
Я.В. Лавренюк
О минимальной системе образующих в группе автоморфизмов
бинарного корневого дерева
Доказано существование минимальной системы образующих в группе всех автоморфизмов
бинарного корневого дерева.
Yа. V. Lavrenyuk
On the minimal system of generatrices in the full automorphism group
of a binary rooted tree
The existence of a basis in the full automorphism group of a binary rooted tree is proved.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2012, №7 37
|