Observaciones Finales

El problema de encontrar el máximo tamaño de la mínima vecindad inversa en un autómata celular lineal reversible tiene una solución simple cuando algunos de sus índices de Welch $L$ o $R$ es igual con $1$. Esto lo hemos visto a través de el proceso de Nasu [Nasu 78] o el de Kari [Kari 92], lo siguiente sucede ya que podemos fijar en un extremo el elemento inverso en el conjunto de ancestros.

El tener un índice de Welch igual con $1$ implica que para un autómata reversible con radio de vecindad $r=1/2$, las columnas o los renglones son permutaciones del conjunto de estados, lo que sirve para definir una función entre lo que se produce y un lado de la vecindad.

El problema de los autómatas reversibles con índices de Welch distintos de $1$ es que el elemento único se fija en las partes internas del conjunto de ancestros y no se puede definir una función entre la evolución de una vecindad y un extremo de la misma, ya que esta correspondencia no es biyectiva.

La evidencia práctica [Gómez 96] [Seck 98] apunta a que en ambos casos el máximo tamaño es igual a $d-1$, donde $d$ es el número de nodos del diagrama de de Bruijn correspondiente a cada autómata reversible. Tratar el problema de conocer la máxima longitud de la mínima vecindad inversa por medio del diagrama de de Bruijn no es nuevo, en el trabajo de Klaus Sutner [Sutner 97] encontramos que esto se discute pero construyendo el diagrama de parejas, por lo que el límite vuelve a ser $d^2$.

En este capítulo se ha presentado un resultado el cual indica que en el diagrama de de Bruijn, conforme una secuencia se recorre, sus rutas o bien van decreciendo en el mínimo número de sus variantes internas, o este mínimo número de variantes se puede conservar si es más pequeño que la longitud actual de la secuencia, y de aquí llegamos a resolver el problema.

Por supuesto, un mayor número de observaciones y análisis detallado es necesario para enriquecer este resultado, hay que señalar que el resultado actual es puramente cuantitativo, pues no indica en cual conjunto $A_i$ se establece el elemento común.

Otro punto a notar es que tanto el resultado de Nasu, el de Kari y el presentado aquí no hacen un uso explícito de la teoría clásica desarrollada por Hedlund (Multiplicidad Uniforme e Indices de Welch) para atacar el problema, ya que las demostraciones de Nasu y Kari tienen mucha más influencia de la teoría de autómatas definidos desarrollada en [Perles 63] y la presentada aquí es una descripción cuantitativa del comportamiento del índice $M$.