next up previous contenido
Next: Futuro de las Up: Conclusiones Previous: Conclusiones


Perspectivas para mejorar el cómputo de los Autómatas Celulares Lineales Reversibles

El trabajo desarrollado por Hedlund y Nasu nos han dado una caracterización completa acerca del comportamiento y las cualidades que debe mostrar la reglas de evolución para inducir un mapeo global reversible no importando cuantas células tenga el anillo donde se implementa el ACL, sin embargo aún quedan varias cuestiones por investigar, por ejemplo el algoritmo propuesto empieza a checar las matrices de conectividad para cadenas de longitud 1 en adelante, pero si el ACL es reversible, en que momento se manifestará el principio de combinabilidad que Nasu señala, es decir, para qué longitud de cadena las matrices de conectividad serán debilmente combinables; si tuvieramos la respuesta a esta cuestión podriamos checar solo las matrices de conectividad para las cadenas de dicha longitud y ahorrarnos las demás observaciones, con lo que el tiempo de cálculo de reversibles sería menor.

Otro aspecto a tratar es el tiempo de cálculo del cluster mínimo, esta cuestión aunque es puramente operativa en la implementación del proceso es importante ya que mientra más estados y/o más grande sea la vecindad en el ACL, más tiempo se consumirá en calcular el cluster mínimo; ya que este cálculo se basa en hacer permutaciones por renglones, columnas y estados, tenemos por ejemplo que para un (4,h) tenemos de posibilidades para estas permutaciones, para un (5,h) tenemos y así sucesivamente; por lo que se debe encontrar métodos más eficientes para agilizar el cálculo de estos clusters mínimos.

También tenemos que el proceso genera todas las posibles matrices de ciertas características y de éstas selecciona aquellas que cumplan con ser debilmente combinables, el problema con esta aproximación es que conforme aumenta el número de estados y el tamaño de vecindad, las posibles matrices a generar aumentan exponencialmente; pero por qué no inducir la generación directa de ACLR; parece ser que los ACLR(k,r) estan formados por subautomatas reversibles, es decir, que un ACLR(6,h) puede ser una extensión de un ACLR(5,h) o de un ACLR(4,h) junto con un ACLR(2,h) y así sucesivamente, si esta idea es correcta, el ACLR(2,h) podría ser la base para generar todos los demás ACLR para un mayor número de estados y de este modo no se tendrían que generar todas las posibles matrices de evolución para filtrar de éstas a los ACLR, sino que se generarían directamente matrices de evolución que fueran extensiones de un ACLR con menor número de estados, con lo que el número de matrices a generar se podría reducir dramáticamente.

Otra alternativa interesante es aplicar la teoría de matrices para la detección de ACLR, ya sea haciendo uso de eigenvalores y eigenvectores, ver como se comportan éstos en las matrices de conectividad de un ACLR así como la utilización de productos cartesianos; por otra parte el estudio aquí presentado detecta los valores de L y R, verifica si y en caso afirmativo se induce que M=1, pero por qué no plantear un proceso el cual leyera directamente el valor de M, ésto tendría la ventaja que si se cumple que M=1 para cada posible cadena de cierta longitud, se obtendría simultaneamente la regla inversa de tal ACLR; otra herramienta que sería muy útil desarrollar es un diagrama de Welch en el cual se pudiera leer directamente si existe un único estado en el cual sus valores de L y R sean los únicos ancestros para una secuencia de estados dada.

Como se observa aún queda mucho por hacer para realizar el cálculo de todas las posibles reglas reversibles para un cierto ACL(k,r) sobre todo para estudiar casos donde k y r sean mucho mayores y ofrezcan por lo tanto una gama de comportamientos más complejos e interesantes.



next up previous contenido
Next: Futuro de las Up: Conclusiones Previous: Conclusiones


Seck Tuoh Mora Juan Carlos
E-mail:seck@delta.cs.cinvestav.mx