Reversible Marker Automata on Two-Dimensional Tapes
Kenichi Morita
A marker automaton is a kind of a finite automaton with markers, which can be placed on tape squares to memorize positions. In this paper, reversible marker automata on two-dimensional tapes are defined, and their accepting capability is investigated. It is shown that an irreversible deterministic k-marker automaton is simulated by reversible deterministic one with the same number of markers. Therefore, the constraint of reversibility does not decrease its accepting power. It is also shown that a reversible nondeterministic k-marker automaton is simulated by reversible deterministic one with the same number of markers. Therefore, adding nondeterminism to reversible ones does not increase their accepting power. By above, these three models are equivalent. We give concrete conversion procedures for these two cases. Based on them, we can construct a reversible deterministic marker automaton from irreversible deterministic one, or reversible nondeterministic one by a mechanical method.
Keywords: Reversible marker automaton, reversible finite automaton, twodimensional tape automaton, reversible computing