Search academic texts

Information × Registration Number 0421U102374, Candidate dissertation Status Кандидат фізико-математичних наук Date 07-05-2021 popup.evolution o 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 Description Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.01.08 — математична логіка, теорія алгоритмів і дискретна математика. – Київський національний університет імені Тараса Шевченка, Міністерство освіти і науки України, Київ, 2021. Дисертаційна робота присвячена дослідженню ініціальних оборотних автоматів Мілі та їх функцій росту. Для окремих класів таких автоматів отримано точні значення для функції росту і досліджено питання раціональності її генератриси. Для ініціальних оборотних автоматів з двома станами над бінарним алфавітом було знайдено відповідні функції росту та встановлено, що функція росту є раціональною тільки тоді, коли автомат має скінченний порядок або є автоматом блимаючих лампочок. За послідовністю ітерацій таких автоматів можна побудувати послідовність простих графів. Для кожного з таких графів було обчислено обхват та хроматичне число. Було показано, що обхват або дорівнює 3, або граф є ациклічним. Хроматичне число для таких графів завжди не більше 3. Також було доведено, що для кожного такого графа мультимножина імбалансів є графічною. Для додавальної машини, що реалізує додавання одиниці до слів над бінарним алфавітом, було розглянуто узагальнення за розміром алфавіту та підстановкою у вінцевій рекурсії. Для цього класу автоматів було отримано точні формули для обчислення функції росту. Як наслідок було показано, що генератриса функції росту такого автомата є раціональною тоді і тільки тоді, коли він має скінченний порядок. Registration Date 2021-05-28 popup.nrat_date 2021-05-28 Close