Continuity of Inverse Transition Relations of 2-Neighborhood Cellular Automata

In this paper, we discuss the continuousness of inverse transition relations of cellular automata. Generally, the inverse of a function is a relation and is not always a function. Our interest here lies in the inverse transition systems of cellular automata and cellular automata with transition relations, that is, non-deterministic cellular automata. Richardson investigated non-deterministic cellular automata and proved Richardson´s theorem. The theorem provides necessary and sufficient conditions for a transition system to be a cellular automaton, and the continuousness of the transition relation is one of the conditions. We prove that the inverse relation of the transition functions of any 2-neighborhood deterministic cellular automata are continuous, and that for 2-neighborhood cellular automata of which the transition relation does not satisfy the totality, its inverse relation is not always continuous. We show an example that the transition system of the continuous inverse transition relation of a cellular automaton is not a cellular automaton.