Welch sets for random generation and representation of reversible one-dimensional cellular automata !

Reversible one-dimensional cellular automata are studied from the perspective of Welch Sets. This paper presents an algorithm to generate random Welch sets that de?ne a re- versible cellular automaton. Then, properties of Welch sets are used in order to establish two bipartite graphs describing the evolution rule of reversible cellular automata. The ?rst graph gives an alternative representation for the dynamics of these systems as block map- pings and shifts. The second graph offers a compact representation for the evolution rule of reversible cellular automata. Both graphs and their matrix representations are illustrated by the generation of random reversible cellular automata with 6 and 18 states.