Registration Number
0421U102374, Candidate dissertation
Status
Кандидат фізико-математичних наук
Date
07-05-2021
popup.evolution
.
Title
The growth of initial invertible automata
Author
Skochko Volodymyr Mykhailovych,
popup.head Bondarenko Yevhen Volodymyrovych
popup.opponent Oliinyk Bohdana Vitaliivna
popup.opponent Antonenko Oleksandr Sergijovych
popup.rada
Taras Shevchenko National University of Kyiv
Description
Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.01.08 — математична логіка, теорія алгоритмів і дискретна математика. – Київський національний університет імені Тараса Шевченка, Міністерство освіти і науки України, Київ, 2021.
Дисертаційна робота присвячена дослідженню ініціальних оборотних автоматів Мілі та їх функцій росту. Для окремих класів таких автоматів отримано точні значення для функції росту і досліджено питання раціональності її генератриси.
Для ініціальних оборотних автоматів з двома станами над бінарним алфавітом було знайдено відповідні функції росту та встановлено, що функція росту є раціональною тільки тоді, коли автомат має скінченний порядок або є автоматом блимаючих лампочок. За послідовністю ітерацій таких автоматів можна побудувати послідовність простих графів. Для кожного з таких графів було обчислено обхват та хроматичне число. Було показано, що обхват або дорівнює 3, або граф є ациклічним. Хроматичне число для таких графів завжди не більше 3. Також було доведено, що для кожного такого графа мультимножина імбалансів є графічною.
Для додавальної машини, що реалізує додавання одиниці до слів над бінарним алфавітом, було розглянуто узагальнення за розміром алфавіту та підстановкою у вінцевій рекурсії. Для цього класу автоматів було отримано точні формули для обчислення функції росту. Як наслідок було показано, що генератриса функції росту такого автомата є раціональною тоді і тільки тоді, коли він має скінченний порядок.
Registration Date
2021-05-28
popup.nrat_date
2021-05-28 / 2026-06-30