Bisimulations in memory finite automata

[Бисимуляции конечных автоматов с памятью]

A. N. Nepeivoda^a, A. D. Delman^b, A. S. Terentyeva<sup>b

a</sup> Ailamazyan Program Systems Institute of Russian Academy of Sciences
^b Bauman Moscow State Technical University

Аннотация: В статье рассматривается проблема бисимуляции автоматов с памятью, представляющих собой модель расширенных регулярных выражений с группами захвата в память. Построен алгоритм бисимуляции таких автоматов в случае единственной ячейки памяти. Показано, что в случае нескольких ячеек и возможности рекурсивного перезахвата в память, проблема бисимуляции включает в себя проблему проверки истинности произвольного уравнения в словах над элементами линейных контекстно-свободных языков.

Ключевые слова: расширенные регулярные выражения, конечные автоматы с памятью, бисимуляция, уравнения в словах

Язык публикации: английский

DOI: 10.15514/ISPRAS-2025-37(6)-33