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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A Hierarchy of Reversible Finite Automata

  • Maria Radionova,
  • Alexander Okhotin

摘要

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.