Reversibility of cellular automata

We establish a on-to-one correspondence between the configurations in the Wolfram cellular automaton, which is abbreviated to the WCA, and the paths in the de Bruijn quiver. Extending the correspondence to that between the associative algebra whose underlying vector space is generated by the configurations in the WCA and the path algebra of the de Bruijn quiver, we obtain the global transition of the associative algebra associated with the WCA. Thus we translate the problem concerning reversibility of the WCA into that concerning surjectivity of the endomorphism on the associative algebra. We then show that the induced problem concerning the endomorphism can be solved in terms of the adjacency matrix of the WCA, which is defined from that of the de Bruijn quiver through the one-to-one correspondence. Indeed, we give a necessary and sufficient condition for reversibility of the WCA. By virtue of the necessary and sufficient condition, we classify all 16 reversible rules in the ECA imposing periodic boundary conditions.