Introduction

One dimensional cellular automata are discrete dynamical systems characterized by simple interaction of their parts, but at the same time, these systems are able to produce very complex global behavior. The cellular automata theory has three important periods; the concept rises with the work developed by John von Neumann in the middle of the 50's [vN66], he used these systems to demonstrate the possibility of constructing self-reproducing systems. Later, in the beginning of the 70's, we have the work developed by John H. Conway [Gar70], standing out his cellular automata in two dimensions called ``Life'' which has been widely studied due to the simplicity of its behavior but its capacity to produce complex global behavior. Finally, in the middle of the 80's, Stephen Wolfram [Wol86] was the first in analyze the behavior of the whole set of one dimensional cellular automata with $2$ states and neighborhood radius equal $1$.

Another important theory in relationship with cellular automata is the study in dynamical systems. The work developed by Henry Poncairé and George Birkhoff among others, had a very strong influence in the work developed by Gustav A. Hedlund [Hed69] at the ends of the 60's. In this paper, Hedlund analyzes in some way the dynamical behavior of cellular automata. In this sense, one result in the work of Wolfram [Wol86] is give the following classification of cellular automata according to their dynamical behavior:

• Class I.- Cellular automata which tend to a fixed point.
• Class II.- Cellular automata which tend to recurrent points.
• Class III.- Cellular automata with chaotic behavior.
• Class IV.- Cellular automata with complex behavior.

However, this classification has the failure that for a given cellular automaton, we can't know which class belongs to, until we observe its behavior. This is a strong problem in the study of dynamical comportment of one dimensional cellular automata since there is not a general characterization of their behavior. Nevertheless, in the case of reversible one dimensional cellular automata we have such a characterization due to the work developed by Jarkko Kari [Kar96]. He explains that the behavior of reversible one dimensional cellular automata is given by block permutations and shifts.

Taking advantage of this characterization, we shall analyze the dynamical behavior in reversible one dimensional cellular automata.

The work has the following organization, section 2 gives the basic concepts about one dimensional cellular automata, explains that every one dimensional cellular automaton can be simulated by another one dimensional cellular automaton with neighborhood size equal $2$ and introduces the cylinder sets for handling the configuration space of cellular automata. Section 3 explains the behavior of reversible one dimensional cellular automata using block permutations and shifts, this is done for cellular automata with neighborhood size equal $2$ because the other cases can be simulated with this kind of automata. Section 4 gives the basic concepts in dynamical systems that we use in this study. Section 5 shows the dynamical behavior of reversible one dimensional cellular automata using the cylinder sets. We will see that we can use block permutations to give matrix methods that detect the existence of fixed, periodic and transitive points, and ergodic, mixing and non-wandering cylinder sets. Section 6 takes the matrix procedure for detecting periodic points and depending on the equivalence classes that they form with this procedure we can classify the dynamical behavior of reversible one dimensional cellular automata . Section 7 gives some examples of the functionality of this methods in $(4,1/2)$ reversible one dimensional cellular automata and section 8 has conclusions of this work. Trying to do more clear the exposition and the understanding of this work, section 9 presents a list of symbols commonly used in the development of this paper, making easier their reference.