Скочко Володимир Миколайович Ріст ініціальних оборотних автоматів

Краткое описание

Скочко Володимир Миколайович, фізична особа підприємець. Назва дисертації: «Ріст ініціальних оборотних автоматів». Шифр та назва спеціальності 01.01.08 математична логіка, теорія алгоритмів і дискретнаматематика. Спецрада Д26.001.18 Київського національного університету імені Тараса Шевченка

Київський нацiональний унiверситет iменi Тараса Шевченка
Мiнiстерство освiти i науки України
Київський нацiональний унiверситет iменi Тараса Шевченка
Мiнiстерство освiти i науки України
Квалiфiкацiйна наукова
праця на правах рукопису
Скочко Володимир Миколайович
УДК 519.713.2
ДИСЕРТАЦIЯ
Рiст iнiцiальних оборотних автоматiв
01.01.08 – математична логiка, теорiя алгоритмiв i дискретна математика
Подається на здобуття наукового ступеня
кандидата фiзико-математичних наук
Дисертацiя мiстить результати власних дослiджень. Використання iдей,
результатiв i текстiв iнших авторiв мають посилання на вiдповiдне джерело.
В. М. Скочко
Науковий керiвник: Бондаренко Євген Володимирович
доктор фiз.-мат. наук, доцент
Київ – 2021

Змiст
ВСТУП 10
1 ОГЛЯД ЛIТЕРАТУРИ ЗА ТЕМОЮ
ДИСЕРТАЦIЇ 18
1.1 Обчислювальна технiка та автомати . . . . . . . . . . . . . . 18
1.2 Алгебраїчнi аспекти теорiї автоматiв . . . . . . . . . . . . . . 20
2 ПОПЕРЕДНI ВIДОМОСТI 36
2.1 Графи та їх властивостi . . . . . . . . . . . . . . . . . . . . . 36
2.2 Автомати та їх функцiї росту . . . . . . . . . . . . . . . . . . 40
2.3 Кореневi регулярнi дерева та їх автоморфiзми . . . . . . . . 44
3 РIСТ (2,2)-АВТОМАТIВ 51
3.1 Функцiї росту (2,2)-автоматiв . . . . . . . . . . . . . . . . . . 51
3.1.1 Автомати скiнченного порядку . . . . . . . . . . . . . 53
3.1.2 Автомати блимаючих лампочок . . . . . . . . . . . . 56
3.1.3 Додавальна машина . . . . . . . . . . . . . . . . . . . 59
3.1.4 Автомат a = (a, a−2
)σ . . . . . . . . . . . . . . . . . . 60
3.2 Графи iтерацiй (2, 2)-автоматiв . . . . . . . . . . . . . . . . . 68
9
3.2.1 Автомати скiнченного порядку . . . . . . . . . . . . . 69
3.2.2 Додавальна машина та циклiчний автомат . . . . . . 70
3.2.3 Автомат блимаючих лампочок . . . . . . . . . . . . . 72
4 РIСТ УЗАГАЛЬНЕНИХ ДОДАВАЛЬНИХ
МАШИН 77
4.1 Узагальнена додавальна машина . . . . . . . . . . . . . . . . 77
4.2 Автомати з циклiчною групою . . . . . . . . . . . . . . . . . 82
5 РIСТ ОБМЕЖЕНИХ АВТОМАТIВ 90
5.1 Порядок обмеженого автомата . . . . . . . . . . . . . . . . . 90
5.2 Граф степенiв P(a) . . . . . . . . . . . . . . . . . . . . . . . . 93
5.3 Рiвняння abm = cdn
в групi обмежених автоматiв . . . . . . . 96
5.4 Алгоритм для обчислення мiнiмiзацiї a
n
. . . . . . . . . . . . 101
5.5 Функцiї росту циклiчних обмежених автоматiв . . . . . . . . 103
ВИСНОВКИ 108
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ 110
ДОДАТОК 121
10
ВСТУП
Актуальн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в 20 столiття В. М. Глушков почав дослiджувати абстрактнi автомати як алгебраїчнi об’єкти. У цих роботах було
започатковано дослiдження груп та напiвгруп, що породжуються множиною автоматiв вiдносно операцiї їх композицiї. Справжнiй iнтерес до груп,
що заданi автоматами, почався пiсля того, як у 1983 роц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
11
з рiзноманiтними типами росту: n
α
з iррацiональним α, e
√
n
, n
log(n)/ log(m)
для натуральних значень m. Точна асимптотика росту групи Григорчука
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зує n-кратну 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 Тараса Шевченка, тема № 16БФ038-01 «Якiсний аналiз та керування еволюцiйними системами складної структури» (номер дер-
12
жавної реєстрацiї 0116U004752).
Мета та задач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 результати:
1) знайдено функцiї росту для iнiцiальних оборотних автоматiв з двома
станами над бiнарним алфавiтом;
2) знайдено хроматичнi числа та обхвати для графiв, що виникають з
iтерацiй iнiцiальних оборотних автоматiв з двома станами над бiнарним
13
алфавiтом. Доведено, що кожен такий граф має графiчну мультимножину
iмбалансiв.
3) знайдено функцiї росту для узагальнених додавальних машин;
4) знайдено ефективний метод для м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 [1]
Є.В.Бондаренку належить постановка задачi та загальне керiвництво роботою. У спiльнiй роботi [2] В. М. Скочку належать доведення деяких тверджень (Proposition 2, Proposition 4 та Proposition 7), а також перевiрка
iмбаланс гiпотези для графiв зi степенем не бiльше 9 (Remark 1).
Апробацiя результатiв. Результати дисертацiйного дослiдження були
представленi на наукових конференцiях та наукових семiнарах, а саме:
1. Сiмнадцята мiжнародна наукова конференцiя iменi академiка Михайла
Кравчука. 19-20 травня, 2016 року, Київ.
2. XI Лiтня школа «Алгебра, Топологiя, Аналiз», 1-14 серпня 2016 року,
Одеса.
3. International mathematical conference «Groups and Actions: Geometry
and Dynamics», Taras Shevchenko National University of Kyiv, December
14
19-22, 2016, Київ.
4. Мiжнародна конференцiя молодих математикiв присвячена 100-рiччю з дня народження академiка НАН України
Ю. О. Митропольського(1917-2008), 7-10 червня 2017 року, Київ.
5. 11-та мiжнародна алгебраїчна конференцiя в Українi присвячена
75-рiччю В.В. Кириченка, 3-7 липня 2017 року, Київ.
6. Мiжнародна конференцiя молодих математикiв, 6-8 червня 2019 року,
Київ;
7. Засiдання наукового семiнару кафедри алгебри i комп’ютерної математики Київського нацiонального унiверситету iменi Тараса Шевченка
пiд керiвництвом д. ф.–м. н., проф. А.П. Петравчука, 2021, м. Київ.
Публiкацiї. Основнi результати дисертацiйної роботи опублiкованi в 10
наукових працях, з них п’ять статей в наукових фахових виданнях [1–5],
з яких 2 статтi([2, 5]) надрукованi в журналi, що входить до мiжнародної
наукометричної бази даних Scopus, та п’ять тез у матерiалах наукових конференцiй [6–10].
Структура i обсяг роботи. Дисертацiя складається з анотацiї, вступу,
5 роздiлiв, розбитих на пiдроздiли, загальних висновкiв, списку використаних джерел та додатку. Повний обсяг роботи мiстить 123 сторiнки друкованого тексту, список використаних джерел мiстить 115 найменувань.
У вступi обґрунтовано актуальнiсть теми, вказано зв’язок роботи з науковими програмами, планами, темами, встановлено мету i завдання, об‘єкт,
предмет та методи дослiдження, наведено наукову новизну та практичне
значення отриманих результатiв, особистий внесок здобувача та короткий
опис змiсту роботи.
Перший роздiл мiстить огляд лiтератури за тематикою дисертацiї. Також зроблено короткий iсторичний огляд розвитку теорiї автоматiв та автоматних груп. Розглянуто деякi результати, що були отриманi iншими
авторами у спорiднених напрямках за останнi кiлька десятирiч.
15
Другий роздiл мiстить означення понять, що використовуються у дослiдженнi. Зокрема, поняття iнiцiального оборотного автомата, функцiї росту та автоморфiзму кореневого регулярного дерева.
Третiй роздiл присвячений обчисленню функцiй росту iнiцiальних оборотних автоматiв з двома станами над бiнарним алфавiтом, множину яких
позначатимемо через Ai
(2,2). Також показано, що рацiональнiсть для таких
функцiй має мiсце лише для випадку коли автомат має скiнченний порядок
або як неiнiцiальний породжує групу блимаючих лампочок. Також дослiджено властивостi графiв отриманих з послiдовностей iтерацiй автоматiв з
цього класу. Основний результат даного роздiлу формулюється наступною
теоремою:
Теорема 1. Нехай s ∈ Ai
(2,2) i γs(n) - функцiя росту автомата s. Тодi:
1. Якщо автомат s має скiнченний порядок тодi вiн має рацiональну
функцiю росту. У цьому випадку γs(n) = 1 або γs(n) = 1 + (n mod 2).
2. Автомат s одночасно має нескiнченний порядок i рацiональну функцiю росту тодi i тiльки тодi, коли вiн як неiнiцiальний автомат
породжує групу блимаючих лампочок. Функцiя росту такого автомата визначається формулою γs(n) = 2n
.
3. Iнакше s має неалгебраїчну функцiю росту. Бiльш того, має мiсце
наступна нерiвнiсть для функцiї росту:
2[log2 n] − p − 1 ≤ γs(n) ≤ 2[log2 n] − p + 2,
де n = 2pm з непарним m.
Для автомата a та натурального числа n визначимо простий неорiєнтовний граф Ga(n) наступним чином. Множина вершин Ga(n) це множина
станiв автомата m(a
n
). Двi вершини Ga(n) з’єднанi ребром тодi i тiльки
тодi, коли мiж ними iснує хоча б одна стрiлка в дiаграмi Мура для m(a
n
).
Теорема 2. Нехай s — мiнiмальний iнiцiальний автомат, що належить
множинi Ai
(2,2). Тодi для довiльного n ∈ N:
16
• мультимножина iмбалансiв графа Gs(n) є графiчною;
• хроматичне число χ(Gs(n)) належить множинi {1, 2, 3};
• граф Gs(n) має обхват g(Gs(n)) = 3 або є ациклiчним.
Четвертий роздiл присвячений дослiдженню узагальненої додавальної
машини. Було наведено конструктивний пiдхiд до побудови iтерацiй таких
автоматiв. Основним результатом є наступна теорема.
Теорема 3. Нехай aπ — узагальнена додавальна машина на d лiтерах i
π ∈ Sym(X).
1. Якщо π(d − 1) = d − 1, то aπ має скiнченний порядок |aπ| = |π| i
функцiя росту є перiодичною.
2. Якщо π(d−1) 6= d−1, то γaπ
(n) дорiвнює функцiї росту стандартної
додавальної машини на l лiтерах, де l — довжина орбiти d − 1 пiд
дiєю π. Бiльш точно, нехай n = ε0 +ε1l+. . .+εml
m є розкладом числа
n за основою l i p — перша ненульова позицiя. Тодi
(а) Якщо l > 2, то
γaπ
(n) = (
2m − p + 2, якщо εm = 1;
2m − p + 3, iнакше.
(б) Якщо l = 2, то
γaπ
(n) = (
2m − p + 2, якщо εm−1 = 1 чи p=m;
2m − p + 1, iнакше.
П’ятий роздiл присвячений дослiдженню обмежених iнiцiальних оборотних автоматiв. Показано, що для кожного такого автомата iснує алгоритм, що дозволяє для довiльного числа n побудувати мiнiмiзацiю n-тої
iтерацiї та обчислити кiлькiсть станiв у ньому, тобто обчислити функцiю
росту в точцi n, за час O((log n)
2
).
17
Для побудови алгоритму для заданого автомата ми використовуємо спец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льше 3. Також було показано, що кожен такий граф або
є ациклiчним, або має обхват 3. Було доведено, що для кожного такого
графа мультимножина 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сть O((log n)
2
). На-
109
слiдком доведень є логарифмiчна оцiнка на функцiю росту. Показано, що
функцiя росту обмеженого iнiцiального оборотного автомата рацiональна
тодi i тiльки тодi, коли вiн має скiнченний порядок. У роботi наведено
пiдхiд до побудови формул функцiї росту обмежених автоматiв за умови
накладення на них додаткових умов.