Пошук академічних текстів

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