Submitted by Rosa Assis (rosa_assis@yahoo.com.br) on 2017-03-22T12:33:01Z No. of bitstreams: 2 EURICO LUIZ PROSPERO RUIVO.pdf: 3912806 bytes, checksum: ee84d2f571b4e34203c8e6f37dede9b3 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Paola Damato (repositorio@mackenzie.br) on 2017-03-22T15:40:45Z (GMT) No. of bitstreams: 2 EURICO LUIZ PROSPERO RUIVO.pdf: 3912806 bytes, checksum: ee84d2f571b4e34203c8e6f37dede9b3 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-03-22T15:40:45Z (GMT). No. of bitstreams: 2 EURICO LUIZ PROSPERO RUIVO.pdf: 3912806 bytes, checksum: ee84d2f571b4e34203c8e6f37dede9b3 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2016-09-28 / Fundo Mackenzie de Pesquisa / Cellular automata are locally de ned dynamical systems which are discrete in space, time and in the state variables, and capable of presenting arbitrarily complex global emergent behaviour. One core question in the study of cellular automata refers to their limit behaviour, that is, to the global dynamical features in a in nite time evolution. Previous works have shown that for nite time evolutions, one-dimensional cellular automata present dynamics which can be described by regular languages and, therefore, by nite automata. Also, such studies have shown the existence of growth patterns in the evolution of such nite automata for some cellular automata rules; however these results were obtained manually by directly inspecting the structures that arise during the time evolution. In this work we present the formalisation of an automatic method to compute such structures. Based on this, the rules of the elementary cellular automata rule space were classi ed according to the existence of a growth pattern in their nite automata. Also, we present new methods to infer the limit graph of some elementary cellular automata rules by analysing the regular expressions describing their behaviour in nite-time and the attractors of each rule, as well as an application of these graphs in computing the Fourier spectra of the rules. / Autômatos celulares são sistemas dinâmicos localmente definidos, discretos no espaço, no tempo e nas variáveis de estado, e capazes de apresentar comportamento emergente global arbitrariamente complexo. Uma das questões centrais no estudo de autômatos celulares refere-se ao comportamento limite, isto e, ás características da dinâmica global, ao considerar-se o limite de uma evolucão temporal infinita. Trabalhos anteriores mostraram que para evoluções temporais nitas de autômatos celulares unidimensionais, suas dinâmicas podem ser sempre descritas por linguagens regulares e, portanto, por autômatos finitos. Além disso, esses estudos indicaram a existência de padrões para a evolução desses autômatos finitos para algumas regras; entretanto tais resultados foram obtidos manualmente através da inspeção direta das estruturas que neles surgem ao longo do tempo. Neste trabalho apresenta-se a formalização de um método automático para o cálculo de tais estruturas. Com base nisso, as regras do espaço de autômatos celulares elementares são classificadas de acordo com a existência de um padrão de crescimento de seus autômatos finitos. Além disso, este trabalho apresenta novos métodos para a inferência do grafo-limite de alguns autômatos celulares elementares, por meio da análise das expressões regulares que descrevem seus comportamentos em tempo finito e do estudo da evolução dos atratores de cada regra, bem como uma aplicação desses grafos-limite para o cálculo de espectros de Fourier das regras.

Made available in DSpace on 2016-03-15T19:37:42Z (GMT). No. of bitstreams: 1 Eurico Luiz Prospero Ruivo.pdf: 15234351 bytes, checksum: 5a581041d50f5cbd30ccc684b8112487 (MD5) Previous issue date: 2012-12-11 / Universidade Presbiteriana Mackenzie / The Fourier spectra of cellular automata rules give a characterisation of the limit configurations generated by them at the end of their time evolution. In the present work, the Fourier spectra of each rule of the elementary cellular automata rule space are computed, under periodic and non-periodic boundary conditions, and the space is then partitioned according to the similarity among these computed spectra, what gives the notion of spectral classes in such space. For the partition obtained under periodic boundary condition, each spectral class is analysed in terms of the behaviour of each of its rules and how this behaviour affects the correspondent spectrum. Finally, the spectral classes are related in terms of the similarity among them, for both boundary conditions, what results in graphs depicting the proximity among the spectral classes. / Os espectros de Fourier de regras de autômatos celulares fornecem uma caracterização da configuração limite gerada por elas ao fim de suas evoluções temporais. Neste trabalho, são calculados os espectros de Fourier de todas as regras do espaço dos autômatos celulares elementares, sob condições de contorno periódica e não-periódicas, e o espaço é então particionado de acordo com a similaridade entre os espectros calculados, dando origem à noção de classes espectrais no espaço em questão. Para a participação gerada sob condição de contorno periódica, cada classe espectral é analisada de acordo com o comportamento de cada regra e a implicação deste no espectro obtido. A seguir é analisada a relação de similaridade entre as classes espectrais geradas em cada tipo de condição de contorno, o que d´a origem a grafos representando a proximidade entre as classes espectrais.