Departamento de Computación

Esta tesis tiene por objetivo principal presentar una caracterización topológica al comportamiento dinámico de los autómatas celulares reversibles en una dimensión. Para dicha caracterización se consideran dos propiedades fundamentales que son la multiplicidad uniforme de los ancestros y los índices de Welch. Se demuestra que los autómatas celulares unidimensionales reversibles son un subconjunto de las secuencias límite inversas definidas en el espacio de configuraciones de los autómatas celulares unidimensionales. En particular, se demuestra que los autómatas celulares unidimensionales reversibles cumplen con tener una distancia máxima de 1/2 entre ancestros. Utilizando los anteriores resultados teóricos y la caracterización combinatoria de los autómatas celulares reversibles en una dimensión por medio de permutaciones en bloque; se presenta un método matricial para detectar comportamientos periódicos. En base al comportamiento periódico, se establece una clasificación de los autómatas celulares reversibles en una dimensión por medio de relaciones de equivalencia y se demuestra que esta clasificación define una equivalencia fuerte con respecto al corrimiento entre los autómatas celulares unidimensionales reversibles.

Abstract

The main goal of this thesis is to present a topological characterization of the dynamical behavior of reversible one-dimensional cellular automata. For this reason, two important properties of these systems are considered: the uniform multiplicity of ancestors and Welch indices. It is proved that reversible one-dimensional cellular automata are a subset of the set of inverse limit sequences defined in the configuration space of one-dimensional cellular au- tomata. In particular, for reversible one-dimensional cellular automata it is proved that the maximum distance between ancestors is 1/2. Using the previous theoretical results and the combinatorial characterization by means of block permutations of reversible one-dimensional cellular automata, a matrix method is presented for detecting periodical behaviors. Based on this behavior, a classification of reversible one-dimensional cellular automata is established by means of equivalence relations, and we prove that such a classification defines a strong shift equivalence between reversible one-dimensional cellular automata.