Detecting some periodical behavior in $({k^{}},1/2)$ reversible one dimensional cellular automata

We can use transitions among block permutations to find periodical orbits in $({k^{}},1/2)$ reversible one dimensional cellular automata. Take the set ${K^{3}}$ formed with all the sequences of $3$ cells, with these sequences we can form ${k^{3}}$ configurations, each one of them obtained with the succesive repetition of one sequence in the set ${K^{3}}$. In this way, for a configuration of this kind, we can know which is its succesor configuraton using the block permutations.

For $0 \leq i \leq {k^{3}}$, every configuration ${{c}_{i}}$ has the form $\ldots {w_{i}} {w_{i}} {w_{i}} \ldots$ for ${w_{i}} \in {K^{3}}$ and every ${w_{i}}$ maps to an unique block with the form $x_iy_i$ for $x_i \in X$ and $y_i \in Y$, then the whole configuration ${{c}_{i}}$ maps to a sequence of blocks with the form $\cdots x_iy_ix_iy_ix_iy_i \cdots$. Thus, we have only two kind of blocks, $x_iy_i$ and $y_ix_i$, and applying the permutation $p_2^{-1}$, the block $y_ix_i$ maps to an unique sequence ${w_{j}} \in {K^{3}}$. Making twice this process we have a mapping from the block $x_iy_i$ to another block $x_ky_k$ placed in the same coordinates in relation to the positions in the configuration ${{c}_{i}}$, this is showed in Figure 10.

Figure 10: Mapping from a block $x_iy_i$ to a block $x_ky_k$ placed in the same position

Applying the previous process to all the ${k^{3}}$ configurations, then we have a bijective mapping among the blocks $xy$ because the cellular automaton is reversible, so every block has one ancestor and successor. With this, we can form a connectivity relation whose indices are blocks with the form $xy$ and the elements show the mapping from one block to another. cr

Table 1: Connectivity relation for periodic behavior defined with blocks $xy$

$xy$
$\vdots$	$\vdots$	$\vdots$	$\vdots$
$x_iy_i$	$\vdots$	1	$\vdots$
$\vdots$	$\vdots$	$\vdots$	$\vdots$
	$\cdots$	$x_ky_k$	$\cdots$	$xy$

tc We can define an equivalence relation in the connectivity relation defined in Table 1. If the block $x_iy_i$ maps to $x_ky_k$ and this block maps to $x_my_m$, then there is a mapping from $x_iy_i$ to $x_my_m$. We can do the transitive closure of the connectivity relation (for example, using the Warshall algorithm), and get the equivalence relation. Due to the periodical behavior of $({k^{}},1/2)$ reversible one dimensional cellular automata, every block $xy$ returns to itself and the transitive closure is also reflexive. If there exists a mapping from the block $x_iy_i$ to the block $x_my_m$, then due also to the periodical behavior, there exists a mapping from $x_my_m$ to $x_iy_i$, thus the relation is symmetric and we have an equivalence relation, as is presented in Figure 11. Every class in this equivalence relation represents a set of periodic configurations. The period of every class is the number of elements that it has.

Figure 11: Representation of some equivalence relation defined by the transitive closure of the connectivity relation described in Table 1