Departamento de Computación

Los autómatas celulares son la representación matemática más simple de los sistemas complejos; además, han mostrado ser extremadamente útiles en la idealización de comportamientos dinámicos gracias a su simplicidad. Por si fuera poco, son motores conceptuales con los que se estudia la formación general de patrones. Una de las herramientas que ha probado ser útil para el análisis de la dinámica global y la interacción local de los autómatas celulares son los diagramas de de Bruijn. Estos diagramas son un tipo especial de grafos dirigidos, resultado de una serie de trabajos enfocados al estudio del corrimiento de secuencias de símbolos para codificar información. Los diagramas de de Bruijn han sido explotados en el análisis de la dinámica de los autómatas celulares unidimensionales para buscar configuraciones partıculares, tales como ancestros, Jardines del Edén y autómatas reversibles; sin embargo, este mismo análisis para autómatas celulares en dos dimensiones ha sido escaso. En esta tesis se ofrece una forma de explorar sistemáticamente configuraciones específicas por medio de los diagramas de de Bruijn, desde una configuración inicial en dos dimensiones. Dicho análisis se centra en dos reglas de interés debido a su comportamiento, por un lado, una regla de comportamiento complejo: el Juego de la Vida y por otro, una regla de comportamiento caótico: la Regla de Difusión.

Abstract

Cellular automata are the simplest mathematical representations for many classes of complex systems; also cellular automata have proven to be extremely useful in order to idealize the dynamical behaviour of many real complex systems. As result of their underlying simplicity, cellular automata are also powerful conceptual engines for studing general patterns formation. De Bruijn diagrams have been a useful tools in order to perform a systematic analysis of cellular automata. In this way, de Bruijn diagrams are a special kind of directed graphs, known originally as shift register sequences. These diagrams arise due to a series of works focused to study shift register sequences of symbols for the encoding of information. They have been used to compute particular kind of configurations, such as ancestors,complex patterns, cycles, Garden of Eden configurations and formal languages, specially in one dimensional cellular automata. However, there do not exist too many research for analyzing two dimensional cellular automata. Thus, this thesis offers a way to explore systematically specific configurations by de Bruijn diagrams from initial configurations in two dimensional cellular automata. Such analysis in concentrated mainly in Game of Life and Diffusion Rule.