Abstract: Вычисление значений объектных атрибутов в рамках перезаписывающей системы осуществляется путем последовательной перезаписи префиксов, останавливающейся при возникновении неперезаписываемого слова. Проблема останова этой процедуры представляется нетривиальной, поскольку она аналогична общей алгоритмической проблеме останова, которая, как известно, неразрешима. Мы покажем, что проблема останова префиксной перезаписи эффективно разрешима. В основе доказательства лежит аналог леммы о разрастании для регулярных языков (pumping lemma) из теории автоматов.

Cite: Гутман А.Е.
Эффективный анализ префиксной перезаписи
Воркшоп, посвященный юбилейному выпуску «Владикавказского математического журнала» 10-12 июн. 2026