On reversibility of cellular automata with periodic boundary conditions

Abstract

Reversibility of one-dimensional cellular automata with periodic boundary conditions is discussed. It is shown that there exist exactly 16 reversible elementary cellular automaton rules for infinitely many cell sizes by means of a correspondence between elementary cellular automaton and the de Bruijn graph. In addition, a sufficient condition for reversibility of three-valued and two-neighbour cellular automaton is given.