Про незвідні системи твірних у групах автоморфізмів кореневих дерев
Дослiджено iснування незвiдних систем твiрних для деяких груп та класiв груп автоморфiзмiв кореневих дерев. Зокрема, доведено, що група всiх бiєктивних автоматних перетворень та група бiєктивних скiнченно-автоматних перетворень над довiльним
 алфавiтом, що мiстить хоча б двi лiтери, мають не...
Збережено в:
| Опубліковано в: : | Доповіді НАН України |
|---|---|
| Дата: | 2012 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Видавничий дім "Академперіодика" НАН України
2012
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/84399 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Про незвідні системи твірних у групах автоморфізмів кореневих дерев / Я.В. Лавренюк // Доповiдi Нацiональної академiї наук України. — 2012. — № 9. — С. 19-22. — Бібліогр.: 10 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860265195013668864 |
|---|---|
| author | Лавренюк, Я.В. |
| author_facet | Лавренюк, Я.В. |
| citation_txt | Про незвідні системи твірних у групах автоморфізмів кореневих дерев / Я.В. Лавренюк // Доповiдi Нацiональної академiї наук України. — 2012. — № 9. — С. 19-22. — Бібліогр.: 10 назв. — укр. |
| collection | DSpace DC |
| container_title | Доповіді НАН України |
| description | Дослiджено iснування незвiдних систем твiрних для деяких груп та класiв груп автоморфiзмiв кореневих дерев. Зокрема, доведено, що група всiх бiєктивних автоматних перетворень та група бiєктивних скiнченно-автоматних перетворень над довiльним
алфавiтом, що мiстить хоча б двi лiтери, мають незвiднi системи твiрних.
Исследовано существование неприводимых систем образующих для некоторых групп и классов групп автоморфизмов корневых деревьев. В частности, доказано, что группа всех биективных автоматных преобразований и группа биективных конечно-автоматных преобразований над произвольным алфавитом, содержащим хотя бы две буквы, имеют неприводимые
системы образующих.
The existence of minimal generating systems for some automorphism groups of rooted trees is
proved. Particularly, it is proved that the group of all bijective automaton transformations and
the group of all finite bijective automaton transformations over a fixed alphabet with at least two
elements have the irreducible systems of generatrices.
|
| first_indexed | 2025-12-07T18:59:55Z |
| format | Article |
| fulltext |
УДК 512.54
© 2012
Я.В. Лавренюк
Про незв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джується така проблема.
Проблема 1. Чи мають незвiднi системи твiрних групу всiх бiєктивних автоматних
перетворень та групу бiєктивних скiнченно-автоматних перетворень над довiльним ал-
фавiтом, що мiстить хоча б двi лiтери?
Вперше таку проблему поставили B. Csákány та F. Gécseg [1] в 1965 р. Це питання як
вiдкрита проблема формулювалося також P. Dömösi, зокрема, в роботах [2, проблема 2.1]
та [3, проблема 2.31]. Також ця проблема згадується в роботах [4, 5].
У роботi [6] автором анонсовано розв’язання проблеми 1 для випадку групи всiх бiєк-
тивних автоматних перетворень над алфавiтом, що мiстить двi лiтери.
У даному повiдомленнi доводиться iснування незвiдних систем твiрних для деяких груп
та класiв груп автоморфiзмiв кореневих дерев. Зокрема, дано позитивну вiдповiдь на про-
блему 1.
Спочатку нагадаємо визначення кореневого дерева та деяких груп, що дiють на коре-
невих деревах.
Нехай X = (X1,X2, . . .) — послiдовнiсть скiнченних множин Xi = {0, 1, . . . , ni} (ni > 1 для
всiх i). Xn — множина всiх слiв вигляду x1x2 . . . xn, де xi ∈ Xi, i = 1, . . . , n. X∗ — множина
всiх скiнченних слiв вигляду x1x2 . . . xn, де xi ∈ Xi. X
ω — множина всiх нескiнченних слiв
вигляду x1x2 . . . , де xi ∈ Xi. Також вважаємо, що порожнє слово ∅ мiститься в X
∗. Множину
слiв X
∗ можна розглядати як кореневе дерево TX: вершина x1x2 . . . xn сумiжна з вершиною
x1x2 . . . xn−1, ∅ — корiнь. Визначимо також пiддерево Tv для v ∈ X
∗, вершинами якого
є слова вигляду vX∗. Рiвнем номер n називається множина вершин X
n.
Нехай AutTX — група всiх автоморфiзмiв дерева TX. Зауважимо, що AutTX можна ото-
тожнити з AutXω. Нехай G < AutTX. Нагадаємо визначення стандартних пiдгруп групи G:
Пiдгрупа всiх автоморфiзмiв, що фiксують всi вершини рiвня номер n, позначається
StG(n) i називається стабiлiзатором рiвня.
Якщо v ∈ X
∗, то множина всiх автоморфiзмiв, якi фiксують кожну вершину зовнi пiд-
дерева Tv, називається вершинною групою (чи жорстким стабiлiзатором вершини) i по-
значається ristG(v).
Група, породжена множиною
⋃
v∈Xn
rist v, називається жорстким стабiлiзатором рiвня
номер n i позначається RistG(n).
Незлiченнi групи з незвiдними системами твiрних. Нагадаємо, як визначаються
деякi класи автоморфiзмiв TX.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2012, №9 19
Автоморфiзм g називається слабко фiнiтарним, якщо для довiльного w ∈ X
ω iснують
такi n ∈ N, u ∈ X
n, v ∈ X
ω, що виконуються рiвностi w = uv та g(uv) = g(u)v.
Два слова w1, w2 ∈ X
ω називаються конфiнальними, якщо iснують такi n ∈ N, u1,
u2 ∈ X
n, v ∈ X
ω, що w1 = u1v i w2 = u2v.
Автоморфiзм g називається конфiнальним, якщо вiн конфiнальнi слова переводить
у конфiнальнi.
Нагадаємо тепер, як визначаються деякi пiдгрупи AutTX:
Група Autwf TX — група всiх слабко фiнiтарних автоморфiзмiв.
Група Autb TX — група всiх бiконфiнальних автоморфiзмiв. Складається зi всiх конфi-
нальних автоморфiзмiв AutTX, оберненi до яких теж є конфiнальними.
Зауважимо, що з визначень цих груп одразу випливають включення
Autwf TX < Autb TX.
Бiльш детально цi групи описано, наприклад, в [7].
Теорема 1. Нижченаведенi групи мають незвiднi системи твiрних:
група всiх автоморфiзмiв AutTX;
група слабко фiнiтарних автоморфiзмiв Autwf TX;
група бiконфiнальних автоморфiзмiв Autb TX.
Злiченнi групи з незвiдними системами твiрних. Далi ми роглядатимемо дерева
слiв над алфавiтом. Тобто вважатимемо, що X1 = X2 = · · · . У цьому випадку кореневе
дерево TX називається однорiдним.
В однорiдному кореневому деревi TX кожне пiддерево Tv, де v ∈ X
n, може бути природно
ототожнене з усiм деревом TX:
πv : x1x2 . . . xnxn+1 . . . xm 7→ xn+1xn+2 . . . xm,
де x1x2 . . . xn = v.
Таким чином, якщо g ∈ StAutTX
(n), то дiя g на Tv для кожного v ∈ X
n може бути
ототожнена за допомогою πv з автоморфiзмом gv дерева TX, визначеного рiвнiстю πv(u
g) =
= (πv(u))
gv . Автоморфiзм gv називається станом g в v.
Для кожного g ∈ AutTX можна записати g = aggn, де gn ∈ StAutTX
(n), i ag ∈ Autn TX.
Пiд станом g|v елемента g у вершинi v ∈ X
n мається на увазi стан елемента gn ∈ StAutTX
(n)
у вершинi v.
Автоморфiзм g ∈ AutTX називається скiнченно становим автоморфiзмом, якщо мно-
жина всiх його станiв скiнченна. Всi скiнченно становi автоморфiзми дерева TX утворюють
групу FAutTX.
Пiдгрупа G групи AutTX називається самоподiбною, якщо всi стани елементiв G самi
є елементами групи G.
Для довiльного g ∈ AutTX визначимо Θn(g) = {v ∈ X
n|g|v 6= e}.
Вiдомо, що для g ∈ FAutTX послiдовнiсть може рости лише експоненцiйно чи полiно-
мiально (див. [8, наслiдок 7]).
Нагадаємо тепер, як визначаються деякi пiдгрупи AutTX:
Група Pol(m) полiномiальних автоматiв степеня m > 0 складається з усiх g ∈ FAutTX
таких, що послiдовнiсть Θn(g) обмежена полiномом степеня m. Групу Pol(0) також нази-
вають групою обмежених автоматiв.
20 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2012, №9
Група Pol(∞) полiномiальних автоматiв — об’єднання зростаючого ланцюга груп
∞⋃
m=0
Pol(m).
Група RAutTX функцiонально рекурсивних автоморфiзмiв — об’єднання всiх скiнченно
породжених самоподiбних пiдгруп групи AutTX.
Бiльш детально цi групи описано в [8–10].
Теорема 2. Нижченаведенi групи мають незвiднi системи твiрних:
група FAutTX скiнченно станових автоморфiзмiв;
група Pol(0) обмежених автоматiв;
група Pol(m) полiномiальних автоматiв степеня m ∈ N;
група Pol(∞) полiномiальних автоматiв;
група RAutTX функцiонально рекурсивних автоморфiзмiв.
Зауважимо, що при побудовi незвiдних систем твiрних у доведеннях теорем 1 та 2 ви-
користовується 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. Тому проблема 1 розв’язується позитивно:
Теорема 1. Група всiх бiєктивних автоматних перетворень та група бiєктивних
скiнченно-автоматних перетворень над довiльним алфавiтом, що мiстить хоча б двi лi-
тери, мають незвiднi системи твiрних.
1. Чакани К., Гечек Ф. О группе автоматных преобразований // Кибернетика. – 1965. – № 5. – С. 14–17.
2. 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.
3. Dömösi P., Nehaniv C. L. Algebraic theory of automata networks. An introduction. – Philadelphia, PA:
SIAM, 2005. – 265 p.
4. Aleshin S. Automata in algebra // J. Math. Sci. – 2010. – 168. – P. 14–20.
5. Nekrashevych V.V., Sushchansky V. I. Some problems on groups of finitely automatic permutations //
Mat. Stud. – 2000. – 13, No 1. – P. 93–96.
6. Лавренюк Я.В. Про мiнiмальну систему твiрних у групi автоморфiзмiв бiнарного кореневого дере-
ва // Доп. НАН України. – 2012. – № 7. – С. 35–37.
7. Nekrashevych V.V., Sushchansky V. I. On confinal dynamics of rooted tree automorphisms // Computa-
tional and Geometric Aspects of Modern Algebra. – Cambridge: Cambridge Univ. Press, 2000. – Vol. 275. –
P. 229–246.
8. Sidki S. N. Automorphisms of one-rooted trees: growth, circuit structure and acyclicity // J. Math. Sci. –
2000. – 100, No 1. – P. 1925. – 1943.
9. Brunner A.M., Sidki S.N. On the automorphism group of the one-rooted binary tree // J. Algebra. –
1997. – 195. – P. 465–486.
10. Sidki S.N. Regular trees and their automorphisms. – Rio de Janeiro: IMPA, 1998. – Vol. 56. –
ii+42 p.
Надiйшло до редакцiї 08.02.2012Київський нацiональний унiверситет
iм. Тараса Шевченка
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2012, №9 21
Я.В. Лавренюк
О неприводимых системах образующих в группах автоморфизмов
корневых деревьев
Исследовано существование неприводимых систем образующих для некоторых групп и клас-
сов групп автоморфизмов корневых деревьев. В частности, доказано, что группа всех биек-
тивных автоматных преобразований и группа биективных конечно-автоматных преобразо-
ваний над произвольным алфавитом, содержащим хотя бы две буквы, имеют неприводимые
системы образующих.
Ya. V. Lavrenyuk
On the irreducible systems of generatrices in the automorphism groups
of rooted trees
The existence of minimal generating systems for some automorphism groups of rooted trees is
proved. Particularly, it is proved that the group of all bijective automaton transformations and
the group of all finite bijective automaton transformations over a fixed alphabet with at least two
elements have the irreducible systems of generatrices.
22 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2012, №9
|
| id | nasplib_isofts_kiev_ua-123456789-84399 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1025-6415 |
| language | Ukrainian |
| last_indexed | 2025-12-07T18:59:55Z |
| publishDate | 2012 |
| publisher | Видавничий дім "Академперіодика" НАН України |
| record_format | dspace |
| spelling | Лавренюк, Я.В. 2015-07-07T14:03:41Z 2015-07-07T14:03:41Z 2012 Про незвідні системи твірних у групах автоморфізмів кореневих дерев / Я.В. Лавренюк // Доповiдi Нацiональної академiї наук України. — 2012. — № 9. — С. 19-22. — Бібліогр.: 10 назв. — укр. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/84399 512.54 Дослiджено iснування незвiдних систем твiрних для деяких груп та класiв груп автоморфiзмiв кореневих дерев. Зокрема, доведено, що група всiх бiєктивних автоматних перетворень та група бiєктивних скiнченно-автоматних перетворень над довiльним
 алфавiтом, що мiстить хоча б двi лiтери, мають незвiднi системи твiрних. Исследовано существование неприводимых систем образующих для некоторых групп и классов групп автоморфизмов корневых деревьев. В частности, доказано, что группа всех биективных автоматных преобразований и группа биективных конечно-автоматных преобразований над произвольным алфавитом, содержащим хотя бы две буквы, имеют неприводимые
 системы образующих. The existence of minimal generating systems for some automorphism groups of rooted trees is
 proved. Particularly, it is proved that the group of all bijective automaton transformations and
 the group of all finite bijective automaton transformations over a fixed alphabet with at least two
 elements have the irreducible systems of generatrices. uk Видавничий дім "Академперіодика" НАН України Доповіді НАН України Математика Про незвідні системи твірних у групах автоморфізмів кореневих дерев О неприводимых системах образующих в группах автоморфизмов корневых деревьев On the irreducible systems of generatrices in the automorphism groups of rooted trees Article published earlier |
| spellingShingle | Про незвідні системи твірних у групах автоморфізмів кореневих дерев Лавренюк, Я.В. Математика |
| title | Про незвідні системи твірних у групах автоморфізмів кореневих дерев |
| title_alt | О неприводимых системах образующих в группах автоморфизмов корневых деревьев On the irreducible systems of generatrices in the automorphism groups of rooted trees |
| title_full | Про незвідні системи твірних у групах автоморфізмів кореневих дерев |
| title_fullStr | Про незвідні системи твірних у групах автоморфізмів кореневих дерев |
| title_full_unstemmed | Про незвідні системи твірних у групах автоморфізмів кореневих дерев |
| title_short | Про незвідні системи твірних у групах автоморфізмів кореневих дерев |
| title_sort | про незвідні системи твірних у групах автоморфізмів кореневих дерев |
| topic | Математика |
| topic_facet | Математика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84399 |
| work_keys_str_mv | AT lavrenûkâv pronezvídnísistemitvírnihugrupahavtomorfízmívkorenevihderev AT lavrenûkâv oneprivodimyhsistemahobrazuûŝihvgruppahavtomorfizmovkornevyhderevʹev AT lavrenûkâv ontheirreduciblesystemsofgeneratricesintheautomorphismgroupsofrootedtrees |