next up previous contents
Next: Concepto de Reversibilidad Up: Reversibilidad en Autómatas Celulares Previous: Resumen   Contenido

Antecedentes Históricos

Así como la teoría general de autómatas celulares se han tenido tres etapas importantes, en el caso de los reversibles, análogamente, se tienen tres épocas importantes:

La primera se presenta en los años 60's destacando en principio el trabajo de Edward F. Moore [Moore 62] y las ideas del Jardín del Edén. Desde un enfoque de dinámica simbólica y topología Gustav A. Hedlund, en 1969, contribuye a la teoría de los autómatas celulares reversibles con un estudio que ha sido piedra angular dentro del campo [Hedlund 69]. Hedlund logra un análisis muy detallado y profundo de las propiedades de los autómatas celulares reversibles destacando dos conceptos importantes; Multiplicidad Uniforme e Indices de Welch que se explicarán con detalle más adelante.

La segunda etapa importante la podemos encontrar a finales de los 70's gracias al trabajo de Serafino Amoroso y Yale N. Patt [Amoroso 72], los cuales dieron un primer algoritmo para detectar cuando un autómata celular lineal es reversible. Masakasu Nasu [Nasu 78], [Nasu 79] y [Nasu 82], retoma los resultados de Hedlund y les da un nuevo enfoque utilizando teoría de gráficas, en especial, dos herramientas: el diagrama de de Bruijn y las gráficas Bundle que aquí mencionaremos como diagramas de Welch.

La época más reciente se tiene en esta década con las contribuciones hechas por Jarkko Kari [Kari 92] y [Kari 96]. El hace uso implícito de los análisis hechos por Hedlund y Nasu ofreciendo una nueva perspectiva acerca de las causas que hacen que un autómata celular lineal sea reversible y de las propiedades que en estos se presentan.

De lo anterior podemos destacar que los autómatas celulares lineales reversibles han seguido un proceso de estudio intenso a pesar del corto tiempo de desarrollo que se tiene de esta teoría en comparación con otras. En este proceso se han retomado trabajos anteriores para enriquecerlos y darles un nuevo enfoque como sucede con Nasu y Kari, o simplemente se ha vuelto a rehacer parte del estudio como es el caso de Amoroso y Patt con respecto al trabajo de Hedlund.


next up previous contents
Next: Concepto de Reversibilidad Up: Reversibilidad en Autómatas Celulares Previous: Resumen   Contenido
ice 2001-08-31