Graph-theoretical characterization of invertible cellular automata

A cellular automaton is defined to be invertible if its induced global rule is surjective on the set of all finite configurations. It is shown that all one-dimensional invertible cellular automata are obtainable from invertible nearest-pair ones, i.e., cellular automata given by a rule matrix. For these, an algorithm is proposed, which runs in a time which is a polynomial function of the number of letters of the alphabet. The result is expressed in a graph-theoretical way: the cellular automaton is invertible if and only if two graphs constructed by the algorithm have no edges in common. It follows that if the number of letters in the alphabet is a prime, the only invertible cellular automata are those for which every row or column of the rule matrix is a permutation of the alphabet. For composite alphabet cardinalities, several methods (analytical and computational ones) to obtain more complicated invertible cellular automata are proposed and used to construct examples. All four-letter invertible automata are constructed.