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

Abstract: This research aims at studying the bisimulation relation for memory finite automata, which are used as the automata model for extended regular expressions in the series of works, and encapsulate the expressiveness of the named capture groups. We propose an experimental algorithm for checking bisimulation of one-memory MFAs. For multi-memory automata, we show that, in some borderline cases, the bisimulation problem is closely related to a question of whether a parameterized word is always a solution of a given word equation of an arbitrary form.

Keywords: extended regular expressions, memory finite automata, bisimulation, word equations

Language: English

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