A closed formula for the inverse of a reversible cellular automaton with (2R+1)-cyclic rule

Abstract

[EN]Reversibility of cellular automata (CA) has been an extensively studied problem from both a theoretical and a practical point of view. It is known when a -cyclic cellular automaton with periodic boundary conditions (p.b.c.) is reversible but, as far as we know, no explicit expression is given for its inverse cellular automaton apart from the case. In this paper we give a closed formula for the inverse rule of a reversible (2R+1)-cyclic cellular automaton with p.b.c. over the finite field for any value of the neighbourhood radius R. It turns out that the inverse of a reversible cyclic CA with p.b.c. is again a cyclic CA with p.b.c., but with a different neighbourhood radius, and this radius depends on certain numbers which need to be computed by a new algorithm we introduce. Finally, we apply our results to the case (which is the ECA with Wolfram rule number 150) to introduce an alternative and improved expression for the inverse transition dipolynomial formulated in Encinas and del Rey (2007). We also illustrate these results by giving explicit computations for the inverse transition dipolynomial of a reversible cellular automaton with penta-cyclic rule.