2024/11/21 by Maria Radionova, Radionova, Maria, Alexander Okhotin +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #68Q45 #Computability, Logic, AI Algorithms #DNA and Biological Computing #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2411.14538
openalex publication_date 2024/11/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, different variants of reversible finite automata are compared, and their hierarchy by the expressive power is established. It is shown that one-way reversible automata with multiple initial states (MRFA) recognize strictly more languages than sweeping reversible automata (sRFA), which are in turn stronger than one-way reversible automata with a single initial state (1RFA). The latter recognize strictly more languages than one-way permutation automata (1PerFA). It is also shown that the hierarchy of sRFA by the number of passes over the input string collapses: it turns out that three passes are always enough. On the other hand, MRFA form a hierarchy by the number of initial states: their subclass with at most k initial states (MRFAk) recognize strictly fewer languages than MRFAk + 1, and also MRFAk are incomparable with sRFA. In the unary case, sRFA, MRFAk and MRFA become equal in their expressive power, and the inclusion of 1RFA into sRFA remains proper.