Reversible Multi-head Finite Automata Characterize Reversible Logarithmic Space
Reversible Multi-head Finite Automata Characterize Reversible Logarithmic Space
复制标题
可逆多头有限自动机表征可逆对数空间
DOI：
10.1007/978-3-642-28332-1_9
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Holger Bock Axelsen
中科院分区：
文献类型：
--
作者：
Holger Bock Axelsen
已知确定性和非确定性多头有限自动机分别表征确定性和非确定性对数空间复杂度类。最近，Morita引入了可逆多头有限自动机（rmfa），并提出了rmfa是否也表征可逆对数空间的问题。在这里，我们通过展示对数空间可逆图灵机的整洁RMFA模拟，肯定地解决了这个问题。间接证明了可逆和确定性多头有限自动机可以识别相同的语言。
Deterministic and non-deterministic multi-head finite automata are known to characterize the deterministic and non- deterministic logarithmic space complexity classes, respectively. Recently, Morita introduced reversible multi-head finite automata (RMFAs), and posed the question of whether RMFAs characterize reversible logarithmic space as well. Here, we resolve the question affirmatively, by exhibiting a clean RMFA simulation of logarithmic space reversible Turing machines. Indirectly, this also proves that reversible and deterministic multi-head finite automata recognize the same languages.