On some Classes of Reversible 2-head Automata

Abstract

Deterministic 2-head finite automata which are machines that process an input word from both ends are analyzed for their ability to perform reversible computations. This implies that the automata are backward deterministic, enabling unique forward and backward computation. We explore the computational power of such automata, discovering that, while some regular languages cannot be accepted by these machines, they are capable of accepting some characteristic linear languages, e.g., the language of palindromes. Additionally, we prove that restricted variants, i.e., both 1-limited reversible 2-head finite automata and complete reversible 2-head finite automata are less powerful and they form a proper hierarchy. In the former, in each computation step exactly one input letter is being processed, i.e., only one of the heads can read a letter. These automata are also characterized by putting their states to classes based on the head(s) used to reach and to leave the state. In the complete reversible 2-head finite automata, it is required that any input can be fully read by the automaton. The accepted families are also compared to the classes generated by left deterministic linear grammars.