Бондаренко Євген Володимирович. Алгоритмічні та геометричні властивості автоматичних груп

Короткий опис

Бондаренко Євген Володимирович. Назва дисертаційної роботи: "Алгоритмічні та геометричні властивості автоматичних груп "

Київський нацiональний унiверситет
iменi Тараса Шевченка
На правах рукопису
Бондаренко Євген Володимирович
УДК 519.713
АЛГОРИТМIЧНI ТА ГЕОМЕТРИЧНI
ВЛАСТИВОСТI АВТОМАТНИХ ГРУП
01.01.08 — математична логiка, теорiя алгоритмiв i дискретна математика
Дисертацiя
на здобуття наукового ступеня доктора
фiзико–математичних наук
Науковий консультант:
доктор фiз.–мат. наук, професор,
СУЩАНСЬКИЙ В. I.
Київ — 2015
2
Змiст
ВСТУП 7
1 ПОПЕРЕДНI ВIДОМОСТI 32
1.1. Групи автоморфiзмiв кореневих дерев . . . . . . . . . . . . . 32
1.1.1. Простори слiв . . . . . . . . . . . . . . . . . . . . . . . 32
1.1.2. Дерева . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.1.3. Рiст графiв та рiст груп . . . . . . . . . . . . . . . . . 34
1.1.4. Автоморфiзми кореневих дерев . . . . . . . . . . . . . 35
1.2. Автомати та автоматнi групи . . . . . . . . . . . . . . . . . . 39
1.2.1. Автомати . . . . . . . . . . . . . . . . . . . . . . . . . 39
1.2.2. Дiя автоматiв на словах . . . . . . . . . . . . . . . . . 40
1.2.3. Полiномiальнi автоморфiзми та автомати . . . . . . . 43
1.2.4. Ханойськi автомати та гра Ханойськi вежi . . . . . . 46
1.3. Самоподiбнi дiї груп . . . . . . . . . . . . . . . . . . . . . . . 48
1.3.1. Вiртуальнi ендоморфiзми самоподiбних груп . . . . . 49
1.3.2. Стискуючi групи . . . . . . . . . . . . . . . . . . . . . 50
1.4. Висновки до роздiлу . . . . . . . . . . . . . . . . . . . . . . . 51
2 АЛГОРИТМIЧНI ВЛАСТИВОСТI АВТОМАТНИХ ГРУП 52
2.1. Проблема слiв в автоматних групах . . . . . . . . . . . . . . 52
2.1.1. Класичний алгоритм розв’язання проблеми слiв . . . 52
2.1.2. Проблема слiв в ханойських групах . . . . . . . . . . 55
3
2.1.3. Проблема слiв в групах, породжених полiномiальними
автоматами . . . . . . . . . . . . . . . . . . . . . . . . 58
2.1.4. Проблема слiв в групах, якi узагальнюють полiномiальнi автомати та стискуючi групи . . . . . . . . . . . 63
2.2. Проблема порядку в групах автоморфiзмiв кореневих дерев 68
2.2.1. Орбiтальнi стани автоморфiзмiв . . . . . . . . . . . . 70
2.2.2. Граф порядку автоморфiзмiв . . . . . . . . . . . . . . 71
2.2.3. Проблема порядку для обмежених автоморфiзмiв . . 73
2.3. Проблема спряженостi в групах автоморфiзмiв дерев . . . . 74
2.3.1. Спряженiсть в групах Aut(X∗
) i RAut(X∗
) . . . . . . 74
2.3.2. Спряженiсть стискуючих автоморфiзмiв . . . . . . . . 82
2.3.3. Спряженiсть обмежених автоморфiзмiв в групi фiнiтарних автоморфiзмiв . . . . . . . . . . . . . . . . . . 86
2.3.4. Проблема спряженостi в групi обмежених автоматiв . 91
2.3.5. Спряженiсть обмежених автоморфiзмiв в групах
полiномiальних автоматiв . . . . . . . . . . . . . . . . 99
2.4. Проблема скiнченностi для груп, породжених обмеженими
автоматами . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
2.5. Висновки до роздiлу . . . . . . . . . . . . . . . . . . . . . . . 106
3 САМОПОДIБНI МIРИ НА ГРАНИЧНИХ ПРОСТОРАХ
САМОПОДIБНИХ ГРУП 108
3.1. Мiри Бернуллi на софiчних зсувах . . . . . . . . . . . . . . . 109
3.2. Граничнi простори самоподiбних груп . . . . . . . . . . . . . 118
3.3. Iнварiантнi мiри на граничних просторах XG . . . . . . . . . 122
3.4. Самоподiбнi мiри на граничних просторах JG . . . . . . . . . 129
3.5. Мiра Лебега самоафiнних множин . . . . . . . . . . . . . . . 136
3.6. Замощення граничних просторiв XG . . . . . . . . . . . . . . 142
4
3.7. Висновки до роздiлу . . . . . . . . . . . . . . . . . . . . . . . 146
4 ДИНАМIКА КУСКОВО-ЛIНIЙНИХ ВIДОБРАЖЕНЬ
ВИГЛЯДУ fK(v) = minA∈K Av 148
4.1. Необхiднi вiдомостi про невiд’ємнi матрицi . . . . . . . . . . 148
4.1.1. Властивостi невiд’ємних матриць . . . . . . . . . . . . 149
4.1.2. Блочно-трикутна структура невiд’ємних матриць . . 150
4.1.3. Кореневi вектори для невiд’ємних матриць . . . . . . 154
4.1.4. Степенi невiд’ємних матриць . . . . . . . . . . . . . . 154
4.2. Вiдображення fK та рядково-замкненi множини K . . . . . . 157
4.3. Iснування додатнього власного вектора для fK . . . . . . . . 163
4.4. Iснування невiд’ємних кореневих векторiв для fK . . . . . . 167
4.5. Асимптотична поведiнка iтерацiй fK . . . . . . . . . . . . . . 173
4.6. Висновки до роздiлу . . . . . . . . . . . . . . . . . . . . . . . 174
5 ГРАФИ ШРАЙЄРА АВТОМАТНИХ ГРУП 176
5.1. Графи Шрайєра груп та графи дiї автоматiв . . . . . . . . . 176
5.1.1. Основнi означення . . . . . . . . . . . . . . . . . . . . 176
5.1.2. Локальна топологiя на помiчених графах . . . . . . . 178
5.1.3. Графи Шрайєра та граничний простiр . . . . . . . . . 179
5.2. Графи Шрайєра обмежених автоматiв . . . . . . . . . . . . . 182
5.2.1. Конструкцiя графiв Γn(A) та Tn(A) . . . . . . . . . . 182
5.2.2. Кусково-лiнiйнi вiдображення, асоцiйованi з обмеженими автоматами . . . . . . . . . . . . . . . . . . . . . 184
5.2.3. Рiст дiаметрiв графiв Γn(A) та Tn(A) . . . . . . . . . 186
5.3. Графи Шрайєра полiномiальних автоматiв . . . . . . . . . . 189
5.4. ω-перiодичнi графи . . . . . . . . . . . . . . . . . . . . . . . . 193
5.4.1. Конструкцiя графiв Xw . . . . . . . . . . . . . . . . . 197
5
5.4.2. Проблема iзоморфiзму для графiв Xw . . . . . . . . . 198
5.4.3. Локальнi iзоморфiзми графiв Xw . . . . . . . . . . . . 204
5.4.4. Графи Xw як графи Шрайєра автоматної групи . . . 209
5.4.5. Рiст графiв Xw . . . . . . . . . . . . . . . . . . . . . . 212
5.4.6. Рiст ω-перiодичних графiв . . . . . . . . . . . . . . . . 213
5.5. Графи Шрайєра ханойських автоматiв . . . . . . . . . . . . 218
5.6. Графи Шрайєра самоподiбної дiї групи Гейзенберга . . . . . 221
5.6.1. Постановка задачi . . . . . . . . . . . . . . . . . . . . 221
5.6.2. Самоподiбна дiя групи Гейзенберга . . . . . . . . . . . 223
5.6.3. Графи Шрайєра групи Гейзенберга . . . . . . . . . . 225
5.7. Висновки до роздiлу . . . . . . . . . . . . . . . . . . . . . . . 230
6 САМОПОДIБНI ТА АВТОМАТНI ДIЇ ГРУП 231
6.1. Скiнченна породженiсть iтерованих вiнцевих добуткiв . . . . 231
6.2. Самоподiбнi групи скiнченного типу . . . . . . . . . . . . . . 240
6.2.1. Означення та простi властивостi самоподiбних груп
скiнченного типу . . . . . . . . . . . . . . . . . . . . . 241
6.2.2. Скiнченна породженiсть . . . . . . . . . . . . . . . . . 246
6.3. Групи Сущанського . . . . . . . . . . . . . . . . . . . . . . . 250
6.3.1. Оригiнальне означення через таблицi Калужнiна . . . 251
6.3.2. Автоматний пiдхiд . . . . . . . . . . . . . . . . . . . . 252
6.3.3. Самоподiбне замиканння груп Сущанського . . . . . . 254
6.3.4. Промiжний рiст груп Сущанського . . . . . . . . . . . 258
6.4. Рiст спряженостi гiллястих груп . . . . . . . . . . . . . . . . 264
6.5. Самоподiбнi дiї нiльпотентних груп . . . . . . . . . . . . . . 268
6.5.1. Допомiжна iнформацiя про нiльпотентнi групи Лi . . 271
6.5.2. Доведення теорем 6.33 i 6.34 . . . . . . . . . . . . . . 273
6.5.3. Приклад самоподiбної дiї групи Гейзенберга . . . . . 280
6
6.6. Цаппа-Зеп добуток груп i автоматнi групи . . . . . . . . . . 281
6.7. Висновки до роздiлу . . . . . . . . . . . . . . . . . . . . . . . 285
7 КЛАСИФIКАЦIЯ ГРУП, ПОРОДЖЕНИХ (3, 2) АВТОМАТАМИ 288
7.1. Загальнi результати класифiкацiї . . . . . . . . . . . . . . . . 288
7.2. Опис автоматних груп для вибраних (3, 2) автоматiв . . . . 289
7.3. Висновки до роздiлу . . . . . . . . . . . . . . . . . . . . . . . 295
ВИСНОВКИ 296
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ 299
7
ВСТУП
Актуальн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модул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дним алфавiтами. Такi автомати перетворюють вхiднi слова лiтера за лiтерою, змiнюючи активний внутрiшнiй стан
автомата. Таким чином, кожен стан автомата, прийнятий за iнiцiальний
стан, визначає перетворення на множинi скiнченних та нескiнченних слiв
над алфавiтом.
8
Першi кроки у вивченнi напiвгруп та груп, породжених автоматними
перетвореннями, були здiйсненi в 60-х роках двадцятого столiття в Київськiй математичнiй школi пiд керiвництвом академiка В. М. Глушкова [6].
Першi суттєвi результати, якi привернули увагу до автоматних груп, були
конструкцiї скiнченних автоматiв [1, 17, 10], якi визначають нескiнченнi
скiнченно породженi перiодичнi групи, таким чином, даючи простi контрприклади до загальної проблеми Бернсайда. Пiзнiше Р. I. Григорчук довiв [11], що автоматна група, яку вiн побудував для проблеми Бернсайда,
має промiжний рiст мiж полiномiальним та експоненцiйним. Це дало вiдповiдь на питання Дж. Мiлнора про iснування таких груп, а також на проблему М. Дея про iснування аменабельних, але не елементарно аменабельних
груп. Навiть на даний момент всi вiдомi конструкцiї груп промiжного росту
основанi на автоматних перетвореннях.
Подальшi дослiдження груп, породжених автоматами, показали, що
вони мають багато iнших цiкавих властивостей (див. оглядовi роботи [22, 8,
23, 65] та списки лiтератури в них). Зокрема, клас автоматних груп мiстить
приклади слабко нескiнченних груп [72, 13, 63], груп скiнченної ширини [24,
22], з гiллястою структурою пiдгруп [97, 9, 22], груп експоненцiйного, але не
рiвномiрно експоненцiйного росту [114, 20] (надаючи вiдповiдь на питання
М. Громова про iснування таких груп), першi приклади аменабельних, але
не субекспоненцiйно аменабельних груп [69, 21].
Геометричнi методи прийшли в теорiю автоматних груп пiсля їх геометричного зображення як груп автоморфiзмiв регулярних кореневих дерев
[71]. Кожне таке дерево є самоподiбним об’єктом: пiддерево, яке висить пiд
кожною вершиною, iзоморфне всьому дереву. Це пiдштовхнуло розвиток
iдей самоподiбностi в теорiї груп i привело до виникнення класу самоподiбних груп автоморфiзмiв дерев та самоподiбних групових дiй [23, 65, 96].
9
Кожна автоматна група є самоподiбною, i навпаки, кожну самоподiбну групу можна задати, взагалi кажучи, нескiнченним автоматом.
Iнший клас груп, який виник з узагальнення деяких прикладiв автоматних груп, — це гiллястi групи, введенi в роботi [9]. Назва вiдображає
властивiсть пiдгруп в цих групах: ґратка субнормальних пiдгруп нагадує
структуру дерева. Важливiсть цього класу пiдкреслюється тим фактом, що
гiллястi групи є одним з трьох класiв груп, на якi природно розбивається
клас слабко нескiнченних груп [63].
Однiєю з важливих тем дослiджень у цьому напрямку є алгоритмiчнi
проблеми навколо автоматiв та груп, породжених автоматами. Слiд вiдзначити, що бiльшiсть таких проблем є вiдкритими на даний момент. Зокрема,
невiдомо, чи можна алгоритмiчно перевiрити, чи заданий скiнченний автомат породжує скiнченну, перiодичну, гiллясту, аменабельну групу, який
рiст групи тощо. Нещодавно було показано, що проблема скiнченностi для
автоматних напiвгруп є алгоритмiчно нерозв’язною [59]. Стосовно класичних алгоритмiчних проблем Дена вiдомо, що проблема слiв в кожнiй автоматнiй групi є розв’язною [8]. Проблема спряженостi була розв’язана тiльки
в деяких автоматних групах [16, 67, 70], а в роботi [109] побудовано приклад автоматної групи з нерозв’язною проблемою спряженостi. Проблема
спряженостi в групi всiх автоматних перетворень та проблема iзоморфiзму в класi автоматних груп є вiдкритими. Тому увага математикiв була
придiлена окремим класам автоматiв. Бiльшiсть дослiджених автоматних
груп, зокрема, група Григорчука, породжуються обмеженими або полiномiальними автоматами, якi визначив С. Сiдкi [104], розглядаючи циклiчну
структуру автоматiв. Серед вiдомих загальних результатiв видiлимо такi:
групи, породженi полiномiальними автоматами, не мiстять вiльних неабелевих пiдгруп [105], а групи, породженi обмеженими автоматами, є амена-
10
бельними [21].
З кожним автоматом природно асоц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
(див. оглядову роботу [12] та список лiтератури в нiй). Зокрема, використовуючи автомати, були побудованi першi приклади регулярних графiв,
спектр яких є множиною Кантора [25]. Реалiзацiя автоматом групи блимаючих лампочок [69] та дослiдження спектральних властивостей вiдповiдних графiв [67] привело до конструкцiї 7-вимiрного замкненого многовиду
з не цiлим третiм числом L
2
-Беттi [68], який став першим контрприкладом
до сильної гiпотези Ат’ї. В роботi [61] побудовано автомати, якi моделюють
вiдому гру “Ханойськi вежi”, що дозволило обчислити спектр ханойських
графiв.
Фундаментальний зв’язок був знайдений В. В. Некрашевичем [96] мiж
автоматними групами, фрактальною геометрiєю та комплексною динамiкою. З автоматною групою асоцiюється граничний простiр, який часто має
фрактальну структуру, а графи дiї автомата вiдображають топологiю простору, та гранична динамiчна система. В комплекснiй динамiцi автоматнi
групи виникають як групи iтерованих монодромiй рацiональних функцiй.
При цьому гранична динамiчна система спряжена з дiєю функцiї на її множинi Жулiа. Цей зв’язок був використаний в роботi [27] для розв’язання проблеми Хаббарда про топологiчний тип розгалужених самонакриттiв
сфери. Стало зрозумiло, що автоматнi групи не тiльки мають унiкальнi
властивостi, а i природно виникають в рiзних роздiлах математики.
11
Все вищесказане св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ї 0111U005264, 2011 – 2015 рр.). Також дисертацiйнi дослiдження виконувалися в рамках науково-дослiдної теми «Автоматнi групи: алгебраїчнi, алгоритмiчнi та комбiнаторнi проблеми» (номер
державної реєстрацiї 0115U000164, 2015 р.), що виконувалася при науководосл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дження є властивостi оборотних автоматiв, автоматних та самоподiбних груп, графiв дiї автоматiв та динамiчних систем,
12
асоцiйованих з автоматами, застосування автоматiв.
Методи дослiдження
У роботi використовуються методи теорiї автоматiв, геометричної та комбiнаторної теорiї груп, динамiчних систем, теорiї графiв, лiнiйної алгебри.
Наукова новизна одержаних результатiв
В дисертацiї автором отримано такi новi результати:
1. Доведено, що проблема слiв в автоматних групах, породжених полiномiальними та ханойськими автоматами, розв’язується за субекспоненцiйний час.
2. Доведено, що проблема спряженостi в групi обмежених автоматiв є алгоритмiчно розв’язною. Доведено, що проблема скiнченностi в класi
груп, породжених обмеженими автоматами без нетривiальних фiнiтарних станiв, є алгоритмiчно розв’язною.
3. Встановлено алгоритмiчний критерiй, коли два стискуючих автоморфiзми регулярного кореневого дерева зi скiнченною кiлькiстю орбiтальних станiв є спряженими в групi скiнченно станових автоморфiзмiв
цього дерева.
4. Вперше визначено самоподiбнi мiри на граничних просторах самоподiбних стискуючих груп. Доведено, що гранична динамiчна система
для самоподiбних стискуючих груп є спряженою з одностороннiм зсувом Бернуллi. Винайдено алгоритмiчний метод для знаходження мiри
Лебега цiлих самоафiнних множин та мiри плиток самоподiбних груп.
13
5. Узагальнено основнi результати з теорiї невiд’ємних матриць на певнi
кусково-лiнiйнi вiдображення, заданi скiнченними множинами невiд’-
ємних матриць. Зокрема, доведено iснування спецiальних невiд’ємних
кореневих векторiв для цих вiдображень, встановлено критерiй iснування додатнього власного вектора та знайдено метод для знаходження
асимптотичної поведiнки iтерацiї таких вiдображень.
6. Винайдено метод для знаходження росту дiаметрiв графiв дiї обмежених автоматiв.
7. Доведено гiпотезу В. В. Некрашевича про те, що орбiтальнi графи дiї
полiномiальних автоматiв мають субекспоненцiйний рiст. Цей результат узагальнено на широкий клас груп, зроблено оцiнку зверху на рiст
i застосовано до ω-перiодичних та ханойських графiв. Побудовано клас
автоматних груп, для яких всi орбiтальнi графи дiї мають промiжний
рiст мiж полiномiальним та експоненцiйним.
8. Встановлено критерiй топологiчної скiнченної породженостi iтерованих
вiнцевих добуткiв груп пiдстановок з рiвномiрно обмеженою кiлькiстю
твiрних.
9. Побудовано приклади скiнченно породжених гiллястих автоматних груп
з максимальними пiдгрупами нескiнченного iндексу, що вiдповiло на
питання з Коурiвського зошита.
10. Доведено, що p-групи Сущанського мають промiжний рiст мiж полiномiальним та експоненцiйним.
11. Знайдено критерiй iснування скiнченно станової самоподiбної дiї для
скiнченно породжених нiльпотентних груп без скруту iз заданим вiртуальним ендоморфiзмом.
14
Практичне значення одержаних результат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змiв, розроблений в дисертацiї, був впроваджений у програмному пакетi AutomGrp
для системи комп’ютерної алгебри GAP.
Дисертацiя може бути використана для читання спецкурсiв з теорiї
автоматiв та теорiї груп на механiко-математичних факультетах унiверситетiв.
Особистий внесок автора
Основнi результати дисертацiї, якi виносяться на захист, отриманi автором
особисто. У роботах, опублiкованих у спiвавторствi, особистий внесок здобувача полягає в наступному: у роботах [1,5,6,8] — опис автоматних груп,
породжених деякими автоматами з трьома станами над бiнарним алфавiтом, та встановлення властивостей для частини автоматних груп; [4] — переведення оригiнального означення груп Сущанського з мови таблиць Калужнiна на мову скiнченних автоматiв та встановлення оцiнок на функцiї
росту цих груп; [10] — визначення самоподiбних мiр на граничних просторах самоподiбних стискуючих груп та опис вiдповiдних динамiчних систем,
15
алгоритмiчний метод для знаходження мiри плиток самоподiбних груп; [11]
— алгоритмiчний метод для знаходження мiри Лебега цiлих самоафiнних
множин; [13] — опис груп автоморфiзмiв для графiв, якi вводяться в роботi,
та оцiнки на функцiї росту цих графiв; [15] — критерiй iснування скiнченно станової самоподiбної дiї для скiнченно породжених нiльпотентних груп
без скруту iз заданим вiртуальним ендоморфiзмом; [17] — опис самоподiбних груп скiнченного типу через граф шаблонiв, алгоритмiчний метод
для перевiрки транзитивностi дiї цих груп та деякi необхiднi умови їхньої
топологiчної скiнченної породженостi; [18] — введене поняття орбiтальних
станiв для автоморфiзмiв кореневих дерев, алгоритмiчний критерiй, коли
два скiнченно станових автоморфiзми iз скiнченною кiлькiстю орбiтальний
станiв є спряженими в групi скiнченних автоматiв, розв’язання проблеми
спряженостi в групi обмежених автоматiв; [19] — опис стабiлiзаторiв точок
для однiєї самоподiбної дiї дискретної групи Гейзенберга.
Апробацiя результатiв дисертацiї
Результати дисертацiї доповiдалися i обговорювалися на:
1. Workshop «Analysis on Graphs and Fractals» (Cardiff, United Kingdom,
2007);
2. Шостiй Мiжнароднiй алгебраїчнiй конференцiї в Українi (Кам’янецьПодiльський, 2007);
3. Сьомiй Мiжнароднiй алгебраїчнiй конференцiї в Українi (Харкiв, 2009);
4. International Conference of Humboldt-Kolleg Series «Humboldt Cosmos:
Science and Society» (Київ, 2009);
5. Spring school «Geometry, Topology and Computation in Groups» (Les Diablerets, Switzerland, 2010);
16
6. Восьмiй Мiжнароднiй алгебраїчнiй конференцiї в Українi (Луганськ,
2011);
7. Мiжнароднiй математичнiй конференцiї, присвяченiй 70-рiччю професора Володимира Кириченка (Миколаїв, 2012);
8. Чотирнадцятiй Мiжнароднiй науковiй конференцiї, iменi академiка
М. Кравчука (Київ, 2012);
9. Мiжнароднiй алгебраїчнiй конференцiї, присвяченiй 100-рiччю вiд дня
народження С. М. Чернiкова (Київ, 2012);
10. Дев’ятiй Мiжнароднiй алгебраїчнiй конференцiї в Українi (Львiв, 2013);
11. П’ятiй Мiжнароднiй конференцiї з аналiтичної теорiї чисел i просторових мозаїк (Київ, 2013);
12. Мiжнароднiй алгебраїчнiй конференцiї, присвяченiй 100-рiччю вiд дня
народження Л. А. Калужнiна (Київ, 2014),
а також на семiнарах у Київському нацiональному унiверситетi iменi Тараса Шевченка, Iнститутi математики Нацiональної Академiї Наук України, Женевському унiверситетi (Швейцарiя, 2009 i 2010), Техаському A&M
Унiверситетi (США, 2007 i 2015), Технiчному унiверситетi Граца (Австрiя,
2014), Унiверситетi Пiвденної Флориди (США, 2015).
Публiкацiї
Результати дисертацiї опублiковано у 21 науковiй публiкацiї [2–4, 33–50], у
тому числi 10 статей у наукових фахових виданнях України, серед них 2
статтi у виданнях, якi включенi до мiжнародних наукометричних баз, та
11 статей у закордонних перiодичних виданнях.
17
Структура та обсяг дисертацiї
Дисертацiйна робота складається зi вступу, семи роздiлiв, висновкiв та списку використаних джерел. Повний обсяг дисертацiї становить 312 сторiнок
друкованого тексту, з яких 298 сторiнок основного тексту. Дисертацiя мiстить 18 рисункiв. Список використаних джерел обсягом 14 сторiнок налiчує 116 найменувань.
Автор висловлює подяку своєму науковому консультанту, професору
Вiталiю Iвановичу Сущанському та професору Ростиславу Iвановичу Григорчуку за пiдтримку в роботi.
Змiст роботи
У першому роздiлi дисертацiї вводяться основнi необхiднi означення i наводяться вiдомi результати, якi використовуються далi в дисертацiї. В тому
числi, розглядаються простори слiв X∗
, Xω
та X−ω над алфавiтом X, групи
автоморфiзмiв регулярних кореневих дерев, автомати та автоматнi групи,
самоподiбнi групи та самоподiбнi дiї груп.
Розглядаються автомати-транслятори, якi є автоматами Мiлi з однаковими вхiдним та вихiдним алфавiтами (далi просто автомати). Кожен
автомат A над алфавiтом X визначається набором (S, π, λ), де S — множина станiв автомата, π : S × X → S — функцiя переходiв автомата, а
λ : S × X → X — функцiя виходiв. Скiнченний автомат A можна ототожнювати iз помiченим орiєнтованим графом ΓA, вершинами якого є стани
автомата, а орiєнтованими ребрами (стрiлками) є s → π(s, x) з мiткою
x|λ(s, x) для всiх s ∈ A i x ∈ X.
Кожен стан автомата s ∈ A визначає вiдображення на просторi X∗
всiх скiнченних слiв над алфавiтом X та на просторi Xω
всiх нескiнченних
18
вправо послiдовностей над X. В термiнах графiчного зображення автоматiв рiвнiсть s(x1x2 . . . xn) = y1y2 . . . yn означає, що в автоматi A iснує шлях,
який починається у станi s i помiчений послiдовно парами x1|y1, x2|y2, . . . ,
xn|yn. Автомат називається оборотним, якщо всi його стани визначають
оборотнi перетворення простору слiв. Для скiнченного оборотного автомата A група, породжена вiдображеннями, якi задаються станами автомата,
вiдносно композицiї вiдображень, називається автоматною групою GA, породженою автоматом A.
Множину слiв X∗ можна розглядати як множину вершин регулярного
кореневого дерева T, коренем якого є порожнє слово i ребрами є (v, vx)
для v ∈ X∗
, x ∈ X. Перетворення простору X∗
, заданi станами оборотних автоматiв, є автоморфiзмами дерева T. Тому кожна автоматна група
є пiдгрупою групи автоморфiзмiв дерева Aut(T). Множина всiх автоморфiзмiв, заданих станами скiнченних оборотних автоматiв, утворюють пiдгрупу в Aut(T), яка називається групою скiнченно станових автоморфiзмiв
FAut(T).
Цикл в автомат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в дерева, заданих обмеженими автоматами, утворює групу Pol(0), яка називається групою обмежених автоматiв.
Множина всiх автоморфiзмiв, заданих полiномiальними автоматами, утворює групу Pol(∞) полiномiальних автоматiв. Також визначається степiнь
полiномiального автомата i розглядаються групи Pol(n) полiномiальних автоматiв степеня не бiльше n.
19
В другому роздiлi «Алгоритмiчнi властивостi автоматних груп» розглядаються алгоритмiчнi проблеми в групах, породжених автоматами, групах Aut(T), FAut(T) та групi функцiйно рекурсивних автоморфiзмiв RAut(T).
В пiдроздiлi 2.1 розглядається проблема слiв в автоматних групах. Для
оцiнки складностi проблеми слiв введено функцiю глибини для скiнченних
автоматiв. Основним результатом є верхня оцiнка на функцiю глибини для
полiномiальних автоматiв:
Теорема 2.11. Нехай A — полiномiальний автомат степеня m. Функцiя
глибини автомата A задовольняє dA(n) = O((log n)
m+1) (n → ∞).
Звiдси виводиться
Теорема 2.13. Нехай A — полiномiальний автомат степеня m. Проблема слiв в групi, породженiй автоматом A, розв’язується за субекспоненцiйний час exp(O((log n)
m+1)) (n → ∞).
Аналогiчнi результати також доводяться для ханойських автоматiв
(теорема 2.7) та класу автоматних груп, який одночасно узагальнює стискуючi самоподiбнi групи i групи, породженi полiномiальними автоматами
(теорема 2.17).
В пiдроздiлi 2.2 розглядається проблема порядку в групах автоморфiзмiв регулярних кореневих дерев. Вводиться поняття орбiтальних станiв
автоморфiзмiв. Показується, що порядок автоморфiзма iз скiнченною кiлькiстю орбiтальних станiв можна знайти за допомогою спецiального скiнченного графа, який алгоритмiчно будується за даним автоморфiзмом. Звiдси
випливає
Наслiдок 2.23. Проблема порядку для скiнченно станових автоморфiзмiв iз скiнченною кiлькiстю орбiтальних станiв є алгоритмiчно розв’язною.
20
Доводиться, що обмеженi автоморфiзми мають скiнченну кiлькiсть орбiтальних станiв. Отже, проблема порядку для обмежених автоморфiзмiв
є алгоритмiчно розв’язною (наслiдок 2.25).
В пiдроздiлi 2.3 розглядається проблема спряженостi в групах автоморфiзмiв Aut(T), RAut(T), FAut(T) та групах полiномiальних автоматiв
Pol(n), n ≥ 0. З кожною парою автоморфiзмiв a, b ∈ Aut(T) асоцiюється
граф спряженостi CΓ(a, b), який будується алгоритмiчно, якщо a, b є скiнченно становими i мають скiнченну кiлькiсть орбiтальних станiв. Доводяться такi результати:
Теорема 2.29. Нехай a, b ∈ FAut(T) мають скiнченну кiлькiсть орбiтальних станiв i CΓ(a, b) — граф спряженостi для пари (a, b). Наступнi
умови рiвносильнi:
1. a i b спряженi в групi Aut(T);
2. a i b спряженi в групi RAut(T);
3. граф CΓ(a, b) непорожнiй.
Проблема одночасної спряженостi в групах формулюється так: для
заданих наборiв елементiв групи a1, . . . , ak i b1, . . . , bk перевiрити, чи iснує
елемент h такий, що h
−1aih = bi для i = 1, . . . , k.
Теорема 2.30. Проблема (одночасної) спряженостi для скiнченно станових автоморфiзмiв зi скiнченною кiлькiстю орбiтальних станiв в групах
Aut(T) та RAut(T) є алгоритмiчно розв’язною.
Зокрема, проблема (одночасної) спряженостi для обмежених автоморфiзмiв в групах Aut(T) та RAut(T) є алгоритмiчно розв’язною.
Теорема 2.32. Два стискуючих автоморфiзми a, b ∈ Aut(T) зi скiнченною кiлькiстю орбiтальних станiв спряженi в групi Aut(T) тодi i лише
тодi, коли вони спряженi в групi FAut(T).
21
Наступним основним результатом цього пiдроздiлу є
Теорема 2.43. Проблема (одночасної) спряженостi в групi обмежених
автоматiв Pol(0) є алгоритмiчно розв’язною.
Доведення теореми конструктивне. Запропоновано два алгоритмiчних
методи для розв’язання проблеми спряженостi в Pol(0), якi також знаходять спрягаючий елемент, якщо заданi елементи є спряженими.
Доводиться, що два обмежених автоморфiзми спряженi в групi Pol(∞)
полiномiальних автоматiв тодi i лише тодi, коли вони спряженi в групi
Pol(0). Звiдси отримується наступний результат:
Наслiдок 2.45. Проблема спряженостi для обмежених автоморфiзмiв
в групах Pol(n), n ∈ N, є алгоритмiчно розв’язною.
В пiдроздiлi 2.4 доводиться, що проблема скiнченностi в класi груп,
породжених обмеженими автоматами без нетривiальних фiнiтарних станiв,
є алгоритмiчно розв’язною.
Третiй роздiл «Самоподiбнi мiри на граничних просторах самоподiбних груп» присвячено побудовi теорiї мiри на граничних просторах самоподiбних груп.
У пiдроздiлi 3.1 розглядаються властивостi мiри Бернуллi на софiчних
зсувах. Нехай Γ – скiнченний орiєнтований граф, ребра якого помiченi лiтерами з алфавiту X. Для кожної вершини v ∈ Γ позначимо через Fv ⊂ X−ω
множину всiх нескiнченних влiво послiдовностей, якi читаються вздовж
орiєнтованих шляхiв, що закiнчуються у вершинi v. Для мiри Бернуллi
µp на просторi X−ω розглядаються µp(Fv), а число κ(Γ) = P
v∈Γ µp(Fv)
називається кратнiстю графа Γ. Винаходяться алгоритмiчнi методи для
знаходження чисел κ(Γ) та µp(Fv) для всiх v ∈ Γ.

Список літератури

ВИСНОВКИ
В дисертац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зм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змiв. Доведено, що проблема спряженостi в групi обмежених автоматiв є алгоритмiчно
розв’язною. Показано, що проблема спряженостi для обмежених автоморфiзмiв в групах полiномiальних автоморфiзмiв є алгоритмiчно розв’язною.
Винайдено алгоритмiчний метод, який для заданого обмеженого автомата
без нетривiальних фiнiтарних станiв перевiряє, чи вiн породжує скiнченну
групу.
297
Вводяться та дослiджуються самоподiбнi мiри на граничних просторах
самоподiбних груп. Показано, що введенi мiри визначаються однозначно
групою та її вiртуальним ендоморфiзмом. Доведено, що гранична динамiчна система для стискуючої самоподiбної групи спряжена з одностороннiм
зсувом Бернуллi. Отриманi результати застосовано до знаходження мiри
Лебега самоафiнних множин. Розглянуто замощення граничного простору
плитками групи.
Розглянуто вiдображення вигляду fK(v) = minA∈K Av, v ∈ R
N , де K
— скiнченна множина квадратних невiд’ємних матриць розмiрностi N, а
“min” означає покоординатний мiнiмум. Знайдено критерiй iснування додатнього власного вектора для вiдображень fK. Доведено iснування невiд’-
ємних кореневих векторiв для fK, у яких спецiальнi координати є додатнiми. Це дозволило дати метод для знаходження асимптотичної поведiнки
iтерацiй f
n
K(v), де v — додатнiй вектор.
Дослiджуються графи Γn(A) дiї скiнченних автоматiв на словах довжини n та графи Γw(A) дiї автоматiв на орбiтi нескiнченної послiдовностi w.
В термiнах теорiї груп цi графи є графами Шрайєра автоматної групи. Для
обмежених автоматiв винайдено рекурсивний метод побудови графiв Γn(A),
що дозволило асоцiювати з кожним обмеженим автоматом кусково-лiнiйне
вiдображення вигляду fA(x) = minM∈K Mx. Використовуючи iтерацiї таких вiдображень, винайдено метод для знаходження асимптотичної поведiнки дiаметрiв графiв Γn(A). Доведена гiпотеза В. В. Некрашевича про те,
що орбiтальнi графи Шрайєра Γw(A) для полiномiальних автоматiв степеня m мають субекспоненцiйний рiст, обмежений зверху exp (O((log n)
m+1))
(n → ∞). Наведено конструкцiю полiномiальних автоматiв, для яких попередня оцiнка є точною. Для ханойських автоматiв Hm доведено, що графи
Γw(Hm) мають промiжний рiст, еквiвалентний exp (O((log n)
m−2
)) (n → ∞).
298
Побудовано сiм’ю нескiнченних 4-регулярних графiв Xw для w ∈ {0, 1}
ω
,
якi узагальнюють ω-перiодичнi графи. Описано проблему iзоморфiзму та
локального iзоморфiзму для цих графiв, визначено їхнi групи автоморфiзмiв та доведено, що вони мають промiжний рiст.
Доведено ряд результатiв про рiзнi алгебраїчнi властивостi самоподiбних та автоматних груп. Доведено, що для скiнченних транзитивних
груп пiдстановок (Gn, Xn), n ≥ 1, з обмеженою мiнiмальною кiлькiстю
твiрних нескiнченно iтерований вiнцевий добуток ≀n≥1Gn буде топологiчно
скiнченно породженим тодi i лише тодi, коли проскiнченна абелева група
Q
n≥1 Gn/[Gn, Gn] є тополог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нченно становi самоподiбнi дiї нiльпотентних груп. Описано автоматнi
групи, асоцiйованi iз Цаппа-Зеп добутками груп.
Наведено результати по класифiкацiї груп, породжених автоматами з
трьома станами над бiнарним алфавiтом. Описано групи, породженi вибраними (3, 2) автоматами