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

Інформація × Реєстраційний номер 0216U003392, 0115U000164 , Науково-дослідна робота Назва роботи Автоматні групи: алгебраїчні, алгоритмічні та комбінаторні проблеми. Назва етапу роботи Керівник роботи Лавренюк Ярослав Васильович, Дата реєстрації 27-01-2016 Організація виконавець Київський національний університет імені Тараса Шевченка Опис етапу Об'єкт дослідження: автоматні групи та їхні графи дії.. Мета роботи: вивчити питання існування мінімальних систем твірних (базисів) для т.з. великих підгруп групи всіх автоматних перетворень; розробити нові методи дослідження автоматних груп та побудова нових прикладів таких груп із "цікавими" властивостями; встановити зв'язок між дією скінченних автоматів та такими відомими комбінаторними конструкціями в теорії графів як добуток заміщення та зіг-заг добуток; розробити методи для оцінки складності проблеми слів в автоматних групах. Методи дослідження: методи теорії автоматних груп, зокрема алгоритмічні та комбінаторні методи (вказані в Технічному завданні). Розглянуто проблеми побудови незвідних систем твірних автоматних груп, побудови нових прикладів автоматних груп із цікавими властивостями, алгоритмічні та комбінаторні проблеми автоматних груп та їхніх графів дії. Доведено існування мінімальних систем твірних для широкого класу вінцево-гіллястих груп, які є щільними підгрупами у групі всіх бієктивних автоматних перетворень. Опис продукції Доведено існування мінімальних систем твірних для широкого класу вінцево-гіллястих груп, які є щільними підгрупами у групі всіх бієктивних автоматних перетворень. Побудувано приклади самоподібних груп, графи дії яких утворюють експандери. Встановлено зв'язок між графами дії автоматів та відомими конструкціями в теорії графів. Отримано оцінки складності проблеми слів в деяких класах автоматних груп, та оцінено функцію глибини для деяких класів автоматів. Автори роботи Бондаренко Є. Лавренюк Я.В. Додано в НРАТ 2020-04-02 Закрити