next up previous contents
Next: Trabajo Futuro Up: Conclusiones Previous: Conclusiones   Contenido

Comportamiento Reversible

Una caracterización del comportamiento reversible se ha presentado en este trabajo tomando como base la teoría de sistemas dinámicos de corrimiento desarrollada por Hedlund en [Hedlund 69]. Conforme esta base hemos tomado los trabajos posteriores de Nasu en [Nasu 78],[Nasu 79] y [Nasu 82] y de Kari en [Kari 92] y [Kari 96] los cuales explican este comportamiento por medio de teoría de gráficas y utilizando permutaciones en bloque y un corrimiento.

Lo que se ha logrado en este escrito es caracterizar el funcionamiento de estas permutaciones por medio de los conceptos de Multiplicidad Uniforme e Indices de Welch. Hemos comprendido como es que la Multiplicidad Uniforme y los índices multiplicativos de Welch deben trabajar para que la información contenida en cada evolución del autómata sólo se permute, con lo cual se conserva y se puede utilizar para regresar en la evolución del autómata simplemente aplicando la permutación en sentido inverso.

Un punto importante alcanzado es hacer este concepto extensivo a cualquier tipo de autómata reversible, no importando su número de estados, su tamaño de vecindad ni el valor de sus índices de Welch.

Se observa que estas permutaciones deben tener un orden muy específico; secuencias de estados similares tendrán permutaciones similares y cada elemento que compone un extremo permutación aparece el mismo número de veces que los demás elementos especificados para ese extremo, es decir, no cualquier permutación especifica a un autómata reversible.

Distintas permutaciones pueden representar al mismo tipo de autómata reversible; esto explica que, aunque en realidad existan un número muy grande de permutaciones para un caso dado, estas sólo representan a un número mucho menor de autómatas celulares lineales reversibles diferentes.

Un problema importante que también se aborda es el de la máxima longitud de la mínima vecindad inversa. Esto es importante para tener un límite en el cálculo de autómatas celulares reversibles de un tipo dado [Gómez 96] [Kari 92] [Seck 98] y explicar la complejidad de estos sistemas [Culik 87].

Si bien el valor de $d^2$ explica satisfactoriamente esta cuestión [McIntosh 91b] [Sutner 97], la evidencia práctica indica que este valor es mucho menor [Gómez 96] [Seck 98]. El uso de la teoría de autómatas definidos [Perles 63] [Nasu 78] [Kari 92] y relaciones de equivalencia establecen este límite en $d-1$ par el caso de autómatas con un ídice de Welch igual a $1$. Aquí se ha presentado una prueba muy sencilla que usando un argumento cuantitativo, establece el mismo resultado para todo tipo de autómata.


next up previous contents
Next: Trabajo Futuro Up: Conclusiones Previous: Conclusiones   Contenido
ice 2001-08-31