Diagrama de Parejas

El diagrama de parejas del autómata $(4,1/2)$ regla $1B2D1E2D$ es:

Figura 6.3: Diagrama de parejas del autómata celular lineal reversible $(4,1/2)$ regla $1B2D1E2D$

Para saber si un autómata es reversible por medio del diagrama de parejas basta con observar si no existen ciclos fuera de la diagonal principal. Una observación importante es que este diagrama nos da una solución a nuestro problema, con sólo observar que tan larga podemos hacer una ruta de tal forma que no existan ciclos, esto lo podemos hacer a lo más tomando una ruta tan larga como nodos exitan en el diagrama; ya que hay tantos nodos como pares ordenados de los nodos del diagram de de Bruijn, este valos es $d^2$, en otras palabras, la mínima vecindad inversa no puede exceder más allá de tener $d^2$ elementos.

Si tenemos esta cota, ¿por qué seguir investigando?. La experiencia práctica ( [Gómez 96], [Seck 98] ) al calcular autómatas reversibles indica que esta cota es mucho menor, pues no se ha encontrado un autómata cuya mínima vecindad inversa sea tan grande. Esta misma evidencia no señala a $d^2$ como la cota máxima sino a $d$, por lo que la cuestión es ahora si es posible formalizar este resultado.