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

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

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

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

Аннотация:

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

Литература:
  1. Гутман А. Е. Объектно-ориентированные данные и префиксная перезапись. Часть I: Обзор и основные результаты // Сиб. мат. журн. 2026. Т. 67, № 3. С. 392–413.
     
  2. Гутман А. Е. Объектно-ориентированные данные и префиксная перезапись. Часть II: Эффективный анализ перезаписи // Сиб. мат. журн. 2026. Т. 67, № 4. С. 616–625.
     
  3. Brzozowski J. A., Jürgensen H. Representation of semiautomata by canonical words and equivalences // Internat. J. Found. Comput. Sci. 2005. V. 16, N 5. P. 831–850.
     
  4. Geser A., Zantema H. Non-looping string rewriting // RAIRO Theor. Inform. Appl. 1999. V. 33, N 3. P. 279–301. 
     
  5. Lohrey M., Petersen H. Complexity results for prefix grammars // RAIRO Theor. Inform. Appl. 2005. V. 39, N 2. P. 391–401.

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

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

E-mail: gutman@math.nsc.ru 

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