Офіційний веб сайт

Цикл наукових праць "Алгебраїчні, геометричні та динамічні властивості скінченних автоматів"

м37

Представлено Київським національним університетом імені Тараса Шевченка.

Автор: Бондаренко Є.В., к.ф.-м.н.

Цикл наукових праць складається з 2 навчальних посібників, 12 наукових статей та 7 тез конференцій, опублікованих протягом 5 років. 

Роботи циклу присвячено вивченню алгебраїчних та геометричних об’єктів, асоційованих зі скінченними автоматами, а також застосуванню отриманих результатів в інших розділах математики. Розв’язано ряд алгоритмічних проблем навколо груп, породжених автоматами, зокрема доведено, що проблема слів в групах, породжених поліноміальними автоматами, розв’язується за субекспоненційний час.

Досліджено алгебраїчні властивості груп, породжених автоматами, зокрема дано відповідь на питання з Коурівського зошита. Побудовано теорію міри на граничних просторах автоматних груп та отримано фундаментальні результати про асоційовану граничну динамічну систему. Ці результати застосовано до проблем з фрактальної геометрії про міру Лебега самоафінних множин.

Отримано низку результатів про графи дії скінченних автоматів, зокрема доведено гіпотезу В.В. Некрашевича про ріст графів дії поліноміальних автоматів. Показано, що графи дії автоматів можуть утворювати послідовність графів експандерів, які мають широке застосування у галузі інформаційних технологій.

Кількість публікацій: 25, в т.ч. 2 навчальних посібника, 12 статей (9 - у зарубіжних виданнях), 7 тез доповідей.