Реєстраційний номер
0421U102374, Кандидатська дисертація
На здобуття
Кандидат фізико-математичних наук
Дата захисту
07-05-2021
Статус
Захищена
Назва роботи
Ріст ініціальних оборотних автоматів
Здобувач
Скочко Володимир Михайлович,
Керівник Бондаренко Євген Володимирович
Опонент Олійник Богдана Віталіївна
Опонент Антоненко Олександр Сергійович
Установа, організація, у вченій раді якої відбудеться/відбувся захист
Київський національний університет імені Тараса Шевченка
Опис
Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.01.08 — математична логіка, теорія алгоритмів і дискретна математика. – Київський національний університет імені Тараса Шевченка, Міністерство освіти і науки України, Київ, 2021.
Дисертаційна робота присвячена дослідженню ініціальних оборотних автоматів Мілі та їх функцій росту. Для окремих класів таких автоматів отримано точні значення для функції росту і досліджено питання раціональності її генератриси.
Для ініціальних оборотних автоматів з двома станами над бінарним алфавітом було знайдено відповідні функції росту та встановлено, що функція росту є раціональною тільки тоді, коли автомат має скінченний порядок або є автоматом блимаючих лампочок. За послідовністю ітерацій таких автоматів можна побудувати послідовність простих графів. Для кожного з таких графів було обчислено обхват та хроматичне число. Було показано, що обхват або дорівнює 3, або граф є ациклічним. Хроматичне число для таких графів завжди не більше 3. Також було доведено, що для кожного такого графа мультимножина імбалансів є графічною.
Для додавальної машини, що реалізує додавання одиниці до слів над бінарним алфавітом, було розглянуто узагальнення за розміром алфавіту та підстановкою у вінцевій рекурсії. Для цього класу автоматів було отримано точні формули для обчислення функції росту. Як наслідок було показано, що генератриса функції росту такого автомата є раціональною тоді і тільки тоді, коли він має скінченний порядок.
Дата реєстрації
2021-05-28
Додано/оновлено в НРАТ
2021-05-28 / 2026-06-30
