Investigador:
Dr. Harold V. McIntosh
e-mail:mcintosh@servidor.dgsca.unam.mx
Departamento de Aplicación de Microcomputadoras
Instituto de Ciencias, Universidad Autónoma de Puebla
Puebla, Puebla
Alumnos:
Juárez Martínez Genaro
e-mail:genaro@sparcomp.cs.cinvestav.mx
Seck Tuoh Mora Juan Carlos
e-mail:seck@delta.cs.cinvestav.mx
Lic. Matemáticas Aplicadas y Computación
Universidad Nacional Autónoma de México
Campus Acatlán
"Por mi raza hablará el espíritu"
Agosto 16, 1996
Resumen
Los Autómatas Celulares Lineales (ACL) son un arreglo de elementos (denominados células)
que toman valores de un conjunto finito de estados individuales; tales elementos
evolucionan a través de un tiempo discreto debido a una condición dada tomando valores
del mismo conjunto finito de estados. Esta teoría matemática ha encontrado aplicaciones
en varios campos de estudio tales como: criptología, simulación de epidemias,
simulación de reacciones químicas, computación en paralelo, entre otras. Existen ACL en
los cuales su condición de evolución es invertible, es decir, estos pueden evolucionar
tanto adelante como hacia atrás a través del tiempo, a tales ACL se les denomina Reversibles.
La representación gráfica y matricial utilizadas en los ACL son un poderoso medio para
el estudio de las características de los ACL-Reversibles.
Introducción El presente reporte muestra una introducción sobre el estudio de
los Autómatas Celulares Reversibles, haciendo hincapié en diferentes herramientas
básicas (diagrama de de Bruijn, diagrama de Subconjuntos y el diagrama de Parejas, así
como sus representaciones matriciales respectivamente), ya que facilitan el análisis de
estos autómatas.
Otra herramienta útil para ejemplificar e ilustrar los autómatas y sus tipos de
diagramas fue el uso del software NXLCAU, este paquete ha sido programado bajo el sistema
operativo NeXTSTEP (existe también versión para MS-DOS, LCAU), desarrollado por Harold
V. McIntosh en el Instituto de Ciencias, Universidad Autónoma de Puebla.
La primera sección aborda los conceptos básicos de los Autómatas Celulares Lineales;
las secciones dos, tres y cuatro muestran como se construyen y representan los diagramas
de de Bruijn, Subconjuntos y Parejas respectivamente, la quinta sección introduce la idea
básica de los Autómatas-Reversibles en una dimensión, las secciones seis y siete
presentan métodos para poder obtener el modelo inverso de un Autómata-Reversible,
las secciones ocho y nueve se enfocan en la
búsqueda de estos autómatas y la sección diez muestra un caso "especial" de
producto cartesiano y reversibilidad.
Seck Tuoh Mora Juan Carlos
E-mail:seck@delta.cs.cinvestav.mx