A Hierarchy of Reversible Finite Automata
摘要
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). It is also shown that the hierarchy of sRFA by the number of turns over the input string collapses: two head reversals 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 (MRFA \(^k\) ) recognizes strictly fewer languages than MRFA \(^{k + 1}\) , and also MRFA \(^k\) are incomparable with sRFA. The last result is that MRFA can be simulated by reversible multi-head automata.