д.ф.-м.н., профессор Гутман Александр Ефимович

Доклад был прочитан в рамках Воркшопа, посвященного 110 юбилейному выпуску «Владикавказского математического журнала» (10 – 12 июня 2026 г., дистанционный формат). Докладчик: д.ф.-м.н., профессор Гутман Александр Ефимович. Название доклада: «Эффективный анализ префиксной перезаписи». Аннотация: вычисление значений объектных атрибутов в рамках перезаписывающей системы осуществляется путем последовательной перезаписи префиксов, останавливающейся при возникновении неперезаписываемого слова. Проблема останова этой процедуры представляется нетривиальной, поскольку она аналогична общей алгоритмической проблеме останова, которая, как известно, неразрешима. Мы покажем, что проблема останова префиксной перезаписи эффективно разрешима. В основе доказательства лежит аналог леммы о разрастании для регулярных языков (pumping lemma) из теории автоматов. ------------------------------------------------------- -------------------------------------------------- Организаторы Воркшопа: - Владикавказский научный центр Российской академии наук (Северо-Кавказский центр математических исследований* (далее – СКЦМИ ВНЦ РАН) и Южный математический институт (далее – ЮМИ ВНЦ РАН)); - Московский государственный университет имени М. В. Ломоносова (Механико-математический факультет (далее – мехмат МГУ)); - Южный федеральный университет (Институт математики, механики и компьютерных наук имени И.И. Воровича (далее – ИММиКН ЮФУ)). *Мероприятие проводится при финансовой поддержке Минобрнауки России...