Block permutations

bp Using the properties of reversible one dimensional cellular automata we can characterize the evolution of these systems. For a reversible one dimensional cellular automaton with invertible rules ${\varphi}$ and ${\varphi^{-1}}$, take the greatest value of the neighborhood radius among both evolution rules, and represent these rules with this neighborhood radius, in such a way that both rules have the same neighborhood size.

Since both rules have the same neighborhood size, then a sequence of $2{r_{}}+1$ cells maps to a single state applying the inverse evolution rule ${\varphi^{-1}}$, but the same sequence has ${k^{2{r_{}}}}$ ancestors with the evolution rule ${\varphi}$. In this way we have that a sequence of $2{r_{}}+1$ has ${k^{2{r_{}}}}$ ancestors which share a unique common central cell, as is presented in Figure 4 .

Figure 4: Ancestors of a neighborhood in a reversible one dimensional cellular automaton

This is extensible for sequences of states with a length greater than $2{r_{}}+1$, a long sequence can be taken as successive overlaps of sequences with length $2{r_{}}+1$. Therefore we have that for $n \geq 2{r_{}}+1$, a sequence of length $n$ has ${k^{2{r_{}}}}$ ancestors, each one of them with $n+2{r_{}}$ cells, where the ancestors share a common sequence with length $n-2{r_{}}$; this is showed in Figure 5.

Figure 5: Ancestors of a sequence of $n$ cells in a reversible one dimensional cellular automaton

Take a sequence of $4{r_{}}$ cells, this sequence has ${k^{2{r_{}}}}$ ancestors of length $6{r_{}}$ cells, and these ancestors have a common central sequence with $2{r_{}}$ cells, as we can see in Figure 6.

Figure 6: Ancestors of a sequence of $4{r_{}}$ cells in a reversible one dimensional cellular automaton

The same behavior exists for the inverse evolution rule ${\varphi^{-1}}$ but in inverse direction and with inverted values of its Welch indices. That is, the index $L$ in the inverse evolution rule ${\varphi^{-1}}$ has the same value that the index $R$ in the original evolution rule ${\varphi}$, and the index $R$ in ${\varphi^{-1}}$ has the same value that the index $L$ in ${\varphi}$. With the construction in Figure 6, we can define $2$ sets $L_{\varphi }$ and $R_{\varphi }$, where the elements of $L_{\varphi }$ are sequences of length $2{r_{}}$ cells and the left ancestor sequences of each one of them, also of length $2{r_{}}$ cells. This is analogous for constructing the elements of set $R_{\varphi }$.

Figure 7: Elements of the sets $L_{\varphi }$ and $R_{\varphi }$

Thus, the set $L_{\varphi }$ has as many elements as ${\mid L_{\varphi}\mid}=L{k^{2{r_{}}}}$ and the set $R_{\varphi }$ has as many elements as ${\mid R_{\varphi}\mid}=R{k^{2{r_{}}}}$. We now define two sets, $X$ and $Y$, such that the cardinality of $X$ is ${\mid X\mid}={\mid L_{\varphi}\mid}$ and the cardinality of the set $Y$ is ${\mid Y\mid}={\mid R_{\varphi}\mid}$. Then, there exists a bijection both from the set $L_{\varphi }$ to the set $X$, and from the set $R_{\varphi }$ to the set $Y$. In this way, we can define two block permutations $p_1$ and $p_2$.

The permutation $p_1$ goes from the set of sequences with length $6{r_{}}$ cells to all the possible sequences with the form $x_iy_j$, where $x_i \in X$ and $y_j \in Y$, for $0 \leq i \leq L{k^{2{r_{}}}}$ and $0 \leq j \leq R{k^{2{r_{}}}}$. The second permutation $p_2$ is almost analogous, it goes from the set of sequences with length $6{r_{}}$ cells to the set of all the possible sequences with the form $y_jx_i$. With these permutations, we can represent the evolution of a reversible one dimensional cellular automaton as the composition ${p_1 \circ p_2^{-1}}$ of two block permutations and a shift of length $3{r_{}}$ cells between both permutations.

Figure 8: Evolution of a reversible one dimensional cellular automaton represented by the composition ${p_1 \circ p_2}$ of block permutations and a shift of $3r$ cells among the permutations

We shall use these block permutations in $({k^{}},1/2)$ reversible one dimensional cellular automata to analyze the dynamical behavior of these systems. The following section establishes the basic concepts of dynamical system theory that we use in this study.