Объектно-ориентированные данные и префиксная перезапись.

Объектно-ориентированные данные и префиксная перезапись. Часть II: Эффективный анализ перезаписи

Гутман А. Е.
Сибирский математический журнал, 67, 4, 616-625 (2026)
Скачать статью

УДК 519.682.1+519.683+519.7+519.1 
DOI: 10.33048/smzh.2026.67.404

Аннотация:

Для произвольной детерминированной префиксной перезаписывающей системы получен критерий бесконечной перезаписываемости слова, на основе которого разработана алгоритмическая процедура анализа последовательности перезаписи.

Литература:
  1. Гутман А. Е. Объектно-ориентированные данные и префиксная перезапись. Часть I: Обзор и основные результаты // Сиб. мат. журн. 2026. Т. 67, № 3. С. 392–413.
     
  2. Rabin M. O., Scott D. Finite automata and their decision problems // IBM J. Res. Dev. 1959. V. 3, N 2. P. 114–125.
     
  3. Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. Москва: Вильямс, 2015.
     
  4. Пентус А. Е., Пентус М. Р. Математическая теория формальных языков. Москва: ИНТУИТ; Бином. Лаборатория знаний, 2006.
     
  5. Барвайс Дж. Справочная книга по математической логике. Часть III: Теория рекурсии. Москва: Наука, 1982.

Работа выполнена в рамках государственного задания ИМ СО РАН (проект № FWNF– 2026–0022).

Гутман Александр Ефимович (ORCID 0000-0003-2030-7459)
  1. Институт математики им. С. Л. Соболева СО РАН, 
    пр. Академика Коптюга, 4, Новосибирск 630090

E-mail: gutman@math.nsc.ru 

Статья поступила 28 мая 2026 г.
После доработки — 28 мая 2026 г.
Принята к публикации 26 июня 2026 г.