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

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.01.08 — математична логіка, теорія алгоритмів і дискретна математика. – Київський національний університет імені Тараса Шевченка, Міністерство освіти і науки України, Київ, 2021. Дисертаційна робота присвячена дослідженню ініціальних оборотних автоматів Мілі та їх функцій росту. Для окремих класів таких автоматів отримано точні значення для функції росту і досліджено питання раціональності її генератриси. Для ініціальних оборотних автоматів з двома станами над бінарним алфавітом було знайдено відповідні функції росту та встановлено, що функція росту є раціональною тільки тоді, коли автомат має скінченний порядок або є автоматом блимаючих лампочок. За послідовністю ітерацій таких автоматів можна побудувати послідовність простих графів. Для кожного з таких графів було обчислено обхват та хроматичне число. Було показано, що обхват або дорівнює 3, або граф є ациклічним. Хроматичне число для таких графів завжди не більше 3. Також було доведено, що для кожного такого графа мультимножина імбалансів є графічною. Для додавальної машини, що реалізує додавання одиниці до слів над бінарним алфавітом, було розглянуто узагальнення за розміром алфавіту та підстановкою у вінцевій рекурсії. Для цього класу автоматів було отримано точні формули для обчислення функції росту. Як наслідок було показано, що генератриса функції росту такого автомата є раціональною тоді і тільки тоді, коли він має скінченний порядок.