Connectivity and Reversibility in Automata

Abstract

If we regard reversibility (in the intuitive sense) as the ability to return to a previous state, automata possess varying types and degrees of reversibility. Several properties of automata are defined, each describing a type of connectivity or reversibility. Their relative strengths are considered, as well as whether they are preserved under generalized homomorphisms. It is shown that in the case of finite automata five of these properties are equivalent. The reverse, Rev(A), of an automaton A is defined and its relationship to A is studied.