д.ф.-м.н., профессор Гутман Александр Ефимович (OTDE-Workshop, II-2026)
Доклад был прочитан в рамках Воркшопа, посвященного 110 юбилейному выпуску «Владикавказского математического журнала» (10 – 12 июня 2026 г., дистанционный формат). Докладчик: д.ф.-м.н., профессор Гутман Александр Ефимович. Название доклада: «Эффективный анализ префиксной перезаписи». Аннотация: вычисление значений объектных атрибутов в рамках перезаписывающей системы осуществляется путем последовательной перезаписи префиксов, останавливающейся при возникновении неперезаписываемого слова. Проблема останова этой процедуры представляется нетривиальной, поскольку она аналогична общей алгоритмической проблеме останова, которая, как известно, неразрешима. Мы покажем, что проблема останова префиксной перезаписи эффективно разрешима. В основе доказательства лежит аналог леммы о разрастании для регулярных языков (pumping lemma) из теории автоматов. Официальная страница Воркшопа на сайте ЮМИ ВНЦ РАН: https://smath.ru/activities/workshops/news/18819/ -------------------------------------------------- Организаторы Воркшопа: - Владикавказский научный центр Российской академии наук* (Северо-Кавказский центр математических исследований и Южный математический институт); - Московский государственный университет имени М. В. Ломоносова (Механико-математический факультет); - Южный федеральный университет (Институт математики, механики и компьютерных наук имени И.И. Воровича). *Мероприятие проводится при финансовой поддержке Минобрнауки России, соглашение № 075-02-2026-738.
Доклад был прочитан в рамках Воркшопа, посвященного 110 юбилейному выпуску «Владикавказского математического журнала» (10 – 12 июня 2026 г., дистанционный формат). Докладчик: д.ф.-м.н., профессор Гутман Александр Ефимович. Название доклада: «Эффективный анализ префиксной перезаписи». Аннотация: вычисление значений объектных атрибутов в рамках перезаписывающей системы осуществляется путем последовательной перезаписи префиксов, останавливающейся при возникновении неперезаписываемого слова. Проблема останова этой процедуры представляется нетривиальной, поскольку она аналогична общей алгоритмической проблеме останова, которая, как известно, неразрешима. Мы покажем, что проблема останова префиксной перезаписи эффективно разрешима. В основе доказательства лежит аналог леммы о разрастании для регулярных языков (pumping lemma) из теории автоматов. Официальная страница Воркшопа на сайте ЮМИ ВНЦ РАН: https://smath.ru/activities/workshops/news/18819/ -------------------------------------------------- Организаторы Воркшопа: - Владикавказский научный центр Российской академии наук* (Северо-Кавказский центр математических исследований и Южный математический институт); - Московский государственный университет имени М. В. Ломоносова (Механико-математический факультет); - Южный федеральный университет (Институт математики, механики и компьютерных наук имени И.И. Воровича). *Мероприятие проводится при финансовой поддержке Минобрнауки России, соглашение № 075-02-2026-738.