Reversibles con Indices $L$ y $R$ Distintos de $1$.

El proceso anteriormente descrito utilizando relaciones de equivalencia para encontrar la máxima longitud de la mínima vecindad inversa, cuando se trata de autómatas reversibles con índices de Welch $L$ y $R$ distintos de $1$ presenta algunos inconvenientes. Para ver esto tomemos el siguiente autómata reversible $(4,1/2)$ regla $CCA566CC$.

Tabla 6.8: Autómata $(4,1/2)$ regla $CCA566CC$

$\begin{array}{ccccc} &0&1&2&3 \\ \cline{2-5} \multicolumn{1}{c\vert}{0}& 0&3&... ...c\vert}{2}& 1&1&2&2 \\ \multicolumn{1}{c\vert}{3}& 0&3&0&3 \\ \end{array}$

Los diagramas de parejas y de subconjuntos de este autómata son los siguientes:

Figura 6.7: Diagramas de parejas y de subconjuntos del autómata $(4,1/2)$ regla $CCA566CC$

Este autómata tiene ambos índices de Welch distintos de $1$; revisando la regla de evolución en la Tabla 6.8, primero se observa que no podemos definir una función $\varphi_s(b)=a$ ya que para este caso las columnas no son permutaciones del conjunto $K$, por lo que $\varphi$ no está definido para toda $s \in K$ en cada columna $b$. En segundo lugar, $\varphi_s(b)$ puede tener más de un resultado, esto es ya que en cada columna puede haber más de una entrada de un mismo elemento, esto impide que $\varphi_s(b)$ se pueda definir como función.

Se ha definido a $\rho_i$ como una relación de $a,b \in K$ si $\varphi_s(a)= \varphi_s(b)$ para toda secuencia $s \in K^i$, esto funcionará en los autómatas donde $L=1$, ya que para toda cadena se tiene que sus ancestros usan todos los estados en sus terminaciones derechas y solo es cuestion de que se utilice una longitud conveniente para que los ancestros de toda cadena fijen una misma terminación izquierda para las terminaciones derechas $a,b$. Esta situación no sucederá en autómatas con índices distintos de $1$.

Para ejemplificar lo anterior, usando el autómata de la Tabla 6.8, se formarán las cadenas $\{02,002,\ldots,0\ldots02\}$ y veamos cuales son sus posibles ancestros.

Tabla: Ancestros de las cadenas $\{0\ldots 02\}$

$\begin{array}{cccc} \begin{array}{\vert c\vert} \hline 32\mbox{{\bf 3}} \\ 0... ... \ldots 02\mbox{{\bf 2}} \\ 0 \ldots 02 \\ \hline \end{array}\\ \end{array}$

Hagamos lo mismo pero ahora para las secuencias $\{12,112,\ldots,1\ldots12\}$ obteniendo sus ancestros.

Tabla: Ancestros de las cadenas $\{1\ldots 12\}$

$\begin{array}{cccc} \begin{array}{\vert c\vert} \hline 11\mbox{{\bf 2}} \\ 2... ...1 \ldots 11\mbox{{\bf0}} \\ 1 \ldots 12 \\ \hline \end{array}\\ \end{array}$

Analizando estas secuencias sobresalen dos cosas:

1. Para las diferentes terminaciones derechas no existe una única terminación izquierda como sucedía cuando el índice de Welch $L=1$, sino que existen $2$ distintas terminaciones y estas se seguiran conservando no importando que tan grande hagamos la cadena.
2. Para la cadena de la forma $0 \ldots 02$ las terminaciones derechas forman la clase $3,2$ mientras que para la cadena con la estructura $1 \ldots 12$ las terminaciones derechas forman la clase $2,0$; es decir, ninguna de estas clases se mantiene para toda secuencia de una longitud dada.

Dados estos argumentos, ¿llegamos a que no es posible utilizar el concepto de relaciones de equivalencia para tratar el problema del máximo tamaño de la mínima vecindad inversa?. Entonces, por qué no hacemos una redefinición del proceso para el caso de autómatas reversibles con tamaño de vecindad $2$.

Sabemos que para este caso el diagrama de de Bruijn tendrá tantos nodos como estados haya en el autómata, en el caso de los autómatas reversibles, cada secuencia de estados tendrá tantos ancestros como nodos en el diagrama de de Bruijn, y para una cierta longitud $n$, toda secuencia de estados tendrá un único estado con el cual regresar hacia atrás en la evolución del autómata.

Tomemos una secuencia $w \in K^n$ y sus posibles ancestros, en total serán $k^{2r}$. En el diagrama de de Bruijn solo dibujemos aquellas rutas que tengan la forma de $w$, las cuales tendrán, la siguiente estructura, empezarán desde $L$ nodos distintos, después de $m$ pasos convergerán a un nodo único $u$ con $0 < m < n$, y de este nodo único surgiran $R$ variantes.

Figura 6.8: Estructura de los ancestros de una cadena en el diagrama de de Bruijn para un autómata reversible

Intuitivamente, si se quiere demostrar que la máxima longitud de la mínima vecindad inversa es igual a $d-1$, entonces debemos probar que conforme una ruta crece en el diagrama de de Bruijn, se van perdiendo alternativas intermedias por las cuales estas rutas pasan, hasta que en la longitud deseada $(d-1)$ solo exista una alternativa intermedia y por lo tanto una única forma de regresar en la evolución del autómata.

Sea la secuencia $s \in K^n$ con $n \in \mathbb{Z}^+$; en un autómata reversible, $s$ tiene $d$ posibles rutas que la representan en el diagrama de de Bruijn cumpliendo con la multiplicidad uniforme. Para $0 \leq i \leq n$, sea $A_i$ el conjunto de nodos de de Bruijn que conforma la secuencia $s$ en cada paso. Por ejemplo, si $n=1$ entonces tenemos dos conjuntos de nodos, $A_0$ y $A_1$, donde $A_0$ es el conjunto de nodos iniciales y $A_1$ el conjunto de nodos finales.

Para $s \in K^n$ con $n \in \mathbb{Z}^+$, sea $V=\min\left\{ A_1,A_2,\ldots,A_n \right\}$, es decir, el conjunto $A_i$ con el mínimo número de elementos. Entonces $V$ representa el mínimo conjunto de variantes que tiene la secuencia $s$ en el diagrama de de Bruijn en un paso dado; además $\vert V\vert$ es el mínimo número de variantes que existen en un paso dado al recorrer la secuencia $s$ en el diagrama de de Bruijn.

Con estos simples conceptos se expone el siguiente resultado.

Teorema 1   En el diagrama de de Bruijn de un autómata celular lineal reversible, cada secuencia $s$ de longitud $d-1$ cumple que $V=1$, es decir, el mínimo número de variantes de las rutas que forman cada secuencia $s$ es $1$.

Prueba. Sea $n \in \mathbb{Z}^+$, con $1 \leq i \leq n$. Sea $s \in K^n$ una secuencia de longitud $n$ donde $s_i$ representa la i-ésima parte de la secuencia teniendo que $s_i \in K$. Sea ${\cal D}$ el conjunto de nodos del diagrama de de Bruijn con $\vert{\cal D}\vert=d$.

Representemos cualquier secuencia de longitud $1$ con $s_1$; para $s_1$ tenemos a $A_0$, el conjunto de nodos iniciales y $A_1$ el conjunto de nodos finales que forman a $s_1$ en el diagrama de de Bruijn. Si $\vert A_0\vert >1$ y $\vert A_1\vert >1$, entonces se debe cumplir que $A_0 \neq A_1$, pues de otro modo la secuencia de la forma $\{s_1\}^{*}$ compuesta por repeticiones sucesivas de $s_1$ tendrá $\vert A_0\vert$ rutas posibles que la representen en el diagrama de de Bruijn, y como todos los nodos de $A_0$ funcionan tanto como inicios como terminaciones de cada $s_1$, entonces siempre existirán $\vert A_0\vert$ alternativas internas en dichas rutas evitando que el autómata sea reversible.

Figura 6.9: Si $A_0 = A_1$ entonces no existe un elemento único común en las rutas

Ya que $A_0 \neq A_1$, existe un elemento $e \in {\cal D}$ tal que $e \in A_0$ pero $e \notin A_1$ por lo que $\vert V\vert=\vert A_1\vert \leq d-1$; es decir, a lo más $V$ tiene $d-1$ elementos.

En el caso más sencillo, si conforme la secuencia $s$ se extiende $\vert V\vert$ decrece paso a paso, entonces después de $d-1$ pasos a lo más $\vert V\vert =1$ teniendo una sola alternativa en algún punto de las rutas que forman $s$ y la prueba está completa.

Supongamos que para la secuencia $s \in K^n$, una extensión de $s$ en un elemento conserva el valor de $\vert V\vert$ con $\vert V\vert >1$; es decir, el mínimo número de alternativas internas en las rutas no decrece. Como $V=A_i$ para alguna $i$ con $0 < i \leq n$; se debe cumplir para $0 \leq j \leq n+1$ con $j \neq i$, que $A_j \neq V$, pues de otro modo se tendrán dos casos:

1. Si $j<i$, entonces la secuencia $\{s_j s_{j+1} \ldots s_i\}^*$ que se forma repitiendo sucesivamente la cadena $\{s_j s_{j+1} \ldots s_i\}$ tendrá al menos $\vert V\vert$ posibles alternativas internas en las rutas que la forman.

2. Si $j>i$, entonces la secuencia $\{s_i s_{i+1} \ldots s_j\}^*$ que se forma repitiendo sucesivamente la cadena $\{s_i s_{i+1} \ldots s_j\}$ tendrá al menos $\vert V\vert$ posibles alternativas internas en las rutas que la forman.

En ambos casos se impide que el autómata sea reversible.

Figura 6.10: Si $A_i = A_j$ la secuencia de $\{s_j \ldots s_i\}^*$ o $\{s_i \ldots s_j\}^*$)tendrá más de una variante interna posible

Esta restricción es mucho más fuerte; para $0 \leq j < k \leq n+1$, se debe cumplir que $A_j \neq A_k$; pues de otro modo la secuencia $\{s_j \ldots s_k\}^*$ formada repitiendo sucesivamente la cadena $\{s_j \ldots s_k\}$ tendrá más de una alternativa interna en las rutas que la generan ya que $\vert V\vert >1$.

Figura 6.11: Si $A_j = A_k$ la secuencia de $\{s_j \ldots s_k\}^*$ tendrá más de una variante interna posible

De aquí llegamos a que $V \neq A_j$ para toda $j$ con $0 \leq j \leq n+1$ y $j \neq i$. Cada una de estas diferencias debe ser distinta a las demás; dado que $V$ es el conjunto $A_i$ con menos elementos, entonces cada $A_j$ tiene al menos un elemento $e_j \in A_j$ pero $e_j \notin A_i$. Para que se presenten estas $n+1$ diferencias distintas se deben utilizar al menos $n+1$ elementos de ${\cal D}$ que no aparecen en $A_i$, por lo que $\vert A_i\vert \leq d-(n+1)$ y a lo más $\vert V\vert$ es igual a $d-(n+1)$.

Teniendo esto, si $n=d-2$, entonces $n+1=d-1$ y $\vert V\vert \leq d-(d-1)$ por lo que para una secuencia $s$ de longitud $d-1$ el mínimo número de variantes internas en las rutas que la producen esta dado por $\vert V\vert = d-(d-1)=1$. $\blacksquare$

De este resultado podemos obtener las siguientes extensiones.

Corolario 1   En un autómata celular lineal reversible, para una secuencia $s$ de longitud $n$, tenemos que:

$$V= \cases{ d-n & si $n \leq d-1$\ \cr 1 & si $n > d-1$}$$

Ya que para una secuencia $s$ de longitud $d-1$ se cumple que $\vert V\vert =1$ entonces se tiene ya una única forma de regresar en la evolución de $s$; con esta observación podemos responder cual es la máxima longitud de la mínima vecindad inversa.

Corolario 2   En un autómata celular lineal reversible, la máxima longitud de la mínima vecindad inversa es igual a $d-1$.

Como los ancestros de una secuencia $S$ con una longitud de $d-1$ fijan un único elemento en común, se cumple que estos tienen $L$ extremos de de Bruijn distintos y $R$ extremos de de Bruijn derechos distintos, entonces otra consecuencia del resultado es:

Corolario 3   En un autómata celular lineal reversible, para una secuencia $s$ de longitud $d-1$, el conjunto $A_0$ especifica un nodo de Welch izquierdo y el conjunto $A_{d-1}$ especifica un nodo de Welch derecho.

Este resultado nos presenta una nueva característica a observar en el diagrama de subconjuntos; cada ruta en este diagrama en realidad representa a un conjunto de rutas del diagrama de de Bruijn. Así en el caso de autómatas con índices de Welch distintos de $1$ se verá que desde la clase completa todas las rutas irán decreciendo al nivel de Welch correspondiente y en el n-ésimo paso el mínimo número de variantes internas estará dado por $d-n$ si $n<d$ o $1$ en otro caso, es decir, es permitido que el mínimo número de variantes internas se conserve si este número y la longitud de la ruta son relativamente pequeños en comparación con $d$.

A continuación se presentan algunos casos de estudio que ejemplifican el funcionamiento de este proceso.