Cadenas de longitud 3

Continuando con el proceso, construyamos las relaciones $\rho _3$, para esto se toman todas las posibles cadenas de tres elementos y sus ancestros.

Figura 6.6: Cadenas de longitud $3$ y sus ancestros

Podemos ver que para toda cadena $w \in K^3$, se cumple que $\varphi_w(0)=\varphi_w(1)=\varphi_w(2)=\varphi_w(3)$, por lo que se tiene una única clase de equivalencia formada por todos los estados del autómata.

Tabla 6.7: Clase de equivalencia $\rho _3$

$\begin{array}{c} \mbox{Clase 0,1,2,3} \\ \\ \begin{array}{ccccc} &0&1&2&3 \\ ... ...&1&1 \\ \multicolumn{1}{c\vert}{3}& 1&1&1&1 \\ \end{array}\\ \end{array}$

Esta última clase de equivalencia es identica a $K \times K$, como se esperaba según el proceso, lo que quiere decir que para toda cadena de longitud $3$, los ancestros de cada una tienen $4$ posibles terminaciones derechas y una única terminación izquierda, esta única terminación ya define una regla de evolución inversa a la original.

Una observación a este proceso es que implicitamente nos dice que todos los autómatas reversibles con un tamaño de vecindad igual a $2$ que tenga su índice de Welch izquierdo $L=1$, tiene en su regla de evolución por lo menos dos columnas idénticas, del mismo modo, si tal autómata tuviera su índice de Welch derecho $R=1$, en su regla de evolución al menos existen dos renglones idénticos.

El proceso de Kari utilizando relaciones de equivalencia aprovecha de manera elegante que si el índice $L=1$, en cada columna aparecen todos los estados una sola vez cada uno, por lo que la función $\varphi_w$ simpre es aplicable para todo estado y para toda $w \in K^*$. Otro punto crucial en este proceso lo da la contención $\rho_i \subseteq \rho_{i+1}$ y que si ocurre que $\rho_i = \rho_{i+1}$, esta igualdad se debe conservar de ahí en adelante, ilustrando de manera sencilla que las variaciones en los ancestros disminuyen paso a paso.

Dado que para emular un autómata celular con otro de radio de vecindad $1/2$ debemos reagrupar los ancestros del primero en nodos de de Bruijn, entonces la forma en que este resultado se extiende a todo tipo de autómata es que la máxima longitud de su mínima vecindad inversa es $d-1$.

Hasta el momento, se han presentado dos formas de demostrar que el máximo tamaño de la mínima vecindad inversa en un autómata reversible en donde su índice $L=1$ o $R=1$ es $d-1$. El objetivo es ahora extender estas ideas para encontrar la misma respuesta para autómatas reversibles en donde ninguno de sus índices de Welch sea igual con $1$.

El proceso de Nasu [Nasu 78] utilizando los diagramas de Welch tiene la desventaja de que no es evidente como calcular el número máximo de nodos que pueden tener estos diagramas en autómatas reversibles donde ambos índices de Welch sean distintos de $1$, la pregunta es: ¿podemos utilizar las ideas de Kari para este fin?.