Made available in DSpace on 2016-04-18T21:39:48Z (GMT). No. of bitstreams: 2 Angelo Schranko de Oliveira1.pdf: 925871 bytes, checksum: 812a592f67dbda8b36f5168fbd5f2598 (MD5) Angelo Schranko de Oliveira2.pdf: 2918106 bytes, checksum: 0969a0bf28b426ce84fe4595d80a73c2 (MD5) Previous issue date: 2009-01-28 / Wolfram Research, Inc. / Cellular automata (CAs) can be defined as discrete dynamical systems over n-dimensional networks of locally connected components, whose evolution occur in a discrete, synchronous and homogeneous fashion. Among their several applications, they have been used as a tool for complex systems modeling governed by fundamental laws of conservation (number-conserving cellular automata) or reversibility (reversible cellular automata). Another fundamental property that can be observed in CAs is regarding to their linearity (linear cellular automata) or nonlinearity. Usually, linear phenomena present low dynamic complexity, however, nonlinear phenoma can present complex behaviours like sensitive dependence on initial conditions and routes to chaos. This work focuses on investigating properties of cellular automata belonging to the intersection of those four classes, namely, reversible, number-conserving, and linear or nonlinear cellular automata. After presenting basic definitions, the notions of number-conserving cellular automata, conservation degree and reversibility are reviewed. Following, a dynamical characterisation parameter which relates the reversibility property of a onedimensional cellular automaton and the pre-images of their basic blocks is introduced, and some proofs of its general properties are given. Empirical observations herein suggest that a cellular automaton is reversible and number-conserving if, and only if, its local transition function is a composition of the local transition functions of the reversible, number-conserving cellular automata with neighbourhood size n=2; such an observation was drawn for neighbourhood sizes n∈{2, 3, 4, 5, 6} and number of states q=2; n∈{2, 3} and q=3; n∈{2, 3} and q=4. A proof for such a conjecture would allow the enumeration between neighbourhood lengths and the quantity of reversible, numberconserving cellular automata in the corresponding space, which can be easily identified by working out the compositions of the local transition functions with n=2. Finally, some relationships between reversible, number-conserving, linear and nonlinear CA rules, their spatio-temporal diagrams and basin of attraction fields are presented. / Autômatos celulares (ACs) podem ser definidos como sistemas dinâmicos sobre redes ndimensionais de componentes localmente conectados, cuja evolução ocorre de forma discreta, síncrona e homogênea. Dentre suas diversas aplicações, têm sido utilizados como ferramenta para modelagem de sistemas complexos regidos por leis fundamentais de conservação (autômatos celulares conservativos) ou reversibilidade (autômatos celulares reversíveis). Outra propriedade fundamental que pode ser observada nos ACs diz respeito à sua linearidade (autômatos celulares lineares) ou nãolinearidade. Fenômenos lineares normalmente apresentam menor complexidade dinâmica, enquanto fenômenos não-lineares podem apresentar propriedades tais como sensibilidade às condições iniciais e rotas para caos. O presente trabalho concentra-se na investigação de propriedades de autômatos celulares unidimensionais pertencentes à interseção dessas quatro classes, isto é, autômatos celulares unidimensionais conservativos, reversíveis, e lineares ou não-lineares. Após definições básicas, são revisitados os conceitos de conservabilidade e reversibilidade. Em seguida, introduz-se um parâmetro de caracterização dinâmica que relaciona a distribuição do número de pré-imagens dos blocos básicos à reversibilidade de autômatos celulares unidimensionais e apresentam-se algumas demonstrações decsuas propriedades gerais. Observações empíricas aqui realizadas sugerem que um autômato celular unidimensional é conservativo e reversível se, e somente se, sua função local de transição de estados é uma composição das funções locais de transição de estado dos autômatos celulares conservativos e reversíveis de vizinhança de comprimento n=2; tal observação foi constatada para vizinhanças de comprimento n∈{2, 3, 4, 5, 6} e quantidade de estados q=2; n∈{2, 3} e q=3; n∈{2, 3} e q=4. Uma demonstração para tal conjectura permitiria estabelecer uma enumeração entre os comprimentos das vizinhanças e a quantidade de autômatos celulares unidimensionais conservativos e reversíveis no espaço correspondente, os quais podem ser facilmente identificados através do cálculo das composições das funções locais de transição de estados com n=2. Por fim, apresentam-se relações entre as classes dos ACs conservativos, reversíveis, lineares e não-lineares, suas dinâmicas espaçotemporais e campos de bacias de atração.

Made available in DSpace on 2016-03-15T19:37:54Z (GMT). No. of bitstreams: 1 MAURICIO VERARDO DA COSTA.pdf: 829862 bytes, checksum: 7cb233efb8692b0820e30cf2bdbf4a76 (MD5) Previous issue date: 2015-02-10 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / The notion of a template for representing cellular automata (CA) rules is introduced. This enhances the standard representation based on a rule table, in that it refers to families of cellular automata, instead of a rule alone. Operations applicable to the templates are defined herein, and their use is exemplified in the context of finding representations for rule sets that share properties. Wolfram Mathematica's functional nature and built-in equation-solving capabilities are central to develop these algorithms. The perspectives for using templates in further contexts are also discussed, along with possible extensions to the present work. As a support to the template concept, a Wolfram Mathematica package called CATemplates is presented, shared with the community using a public repository. / A noção de representação de autômatos celulares (ACs) por meio de templates é aqui introduzida. Ela consiste em uma generalização da tabela de transições de estado clássica, permitindo a representação de subespaços de autômatos celulares, ao invés de apenas indivíduos isolados. São definidas operações aplicáveis aos templates, e seu uso é exemplificado por meio da obtenção de algoritmos que encontram subespaços de regras que apresentam propriedades em comum. Para o desenvolvimento destes algoritmos, a utilização do software Wolfram Mathematica é central, dada sua capacidade de resolução automática de sistemas de equações, além da natureza funcional e simbólica da Wolfram Language, linguagem de programação a ele associada. Também são discutidas as vantagens e desvantagens da utilização deste tipo de representação em outros contextos, e possiblidades de extensão para o trabalho. Como apoio ao conceito dos templates, é apresentada a biblioteca para o Wolfram Mathematica chamada CATemplates, disponibilizada em um repositório público.