Submitted by Rosa Assis (rosa_assis@yahoo.com.br) on 2017-04-07T12:20:06Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) CLAUDIO LUIS DE MEO MARTINS.pdf: 24081977 bytes, checksum: 7ae3e8ba72ff9af0ea1824d98d6cb531 (MD5) / Approved for entry into archive by Paola Damato (repositorio@mackenzie.br) on 2017-04-19T14:04:34Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) CLAUDIO LUIS DE MEO MARTINS.pdf: 24081977 bytes, checksum: 7ae3e8ba72ff9af0ea1824d98d6cb531 (MD5) / Made available in DSpace on 2017-04-19T14:04:34Z (GMT). No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) CLAUDIO LUIS DE MEO MARTINS.pdf: 24081977 bytes, checksum: 7ae3e8ba72ff9af0ea1824d98d6cb531 (MD5) Previous issue date: 2016-08-24 / Fundo Mackenzie de Pesquisa / The understanding of how the composition of cellular automata rules can perform prede ned computations may contribute to the general notion of emerging computation by means of locally processing components. In this context, we propose a solution to the MODn Problem, which is the determination of whether the number of 1-bits in a binary string is perfectly divisible by the positive integer n > 1. The solution is a composition of one-dimensional cellular automata rules, i.e., the application of di erent rules on a lattice with periodic boundary conditions, which are replaced after some iterations, and all of them with maximum radius equal to n 􀀀 1. In this work, the (XU; LEE; CHAU, 2003) solution for MOD3 Problem (n = 3) is extended for any value of n, and the solution is given for any lattice size N that is co-prime to n. In this generalised solution, the number of iterations depends only on N, with O(N2). This solution relies upon two essential classes of rules, that have been de ned herein: the Replacement rules, that replace a certain amount of identical end bits on the lattice with the opposite value, and the Grouping rules, that group isolated strings of identical and consecutive bits on the lattice, to larger strings of the same bit value. Furthermore, we also show how the solution can be simpli- ed in terms of a reduction on the number of required rules, by de ning some operations that involve the rules' active state transitions, i.e., those that change the value of the centre cell of the neighbourhood. To this end, we de ned the operations of Partitioning (the separation of the active transitions of a rule in di erent rules), Joining (the union of the all active transitions of di erent rules in the same rule), and Merging (the joining of all active transitions of the rules involved, but removing some of them or even adding new active transitions to get the desired adjustments. Using the same concepts and methodology, we proposed a x for the only rule that had been reported in the literature for solving the MOD2 Problem, which is known as the Parity Problem. / A compreensão de como uma composição de regras de autômatos celulares consegue realizar cálculos computacionais pré-de finidos pode contribuir para a noção geral de computação emergente por meio de processamentos locais de alguns componentes. Neste contexto, propõe-se uma solucão para o Problema MODn, que determina se o número de bits 1 em uma cadeia binária de tamanho N é perfeitamente divisível por um número inteiro positivo n > 1. A solução é uma composicão de regras de autômatos celulares unidimensionais, ou seja, a aplicacão de regras diferentes, sobre um reticulado em condição de contorno periódica, que são trocadas após algumas iteracões, sendo todas de raio máximo igual a n - 1. Neste trabalho, a solução de (XU; LEE; CHAU, 2003) para o Problema MOD3 (n = 3) é expandida para qualquer valor de n, mas observada a condição que N e n devem ser números primos entre si. Na solução generalizada obtida, a quantidade total de iterações depende somente de N com O(N2). Essa solução se fundamenta em duas classes essenciais de regras, que foram aqui de nidas: as regras de Substituição, que trocam uma determinada quantidade de bits iguais e extremos do reticulado por bits de valores opostos, e as regras de Agrupamento, que juntam cadeias isoladas de bits idênticos e consecutivos no reticulado, ás maiores cadeias do mesmo valor do bit. Além disso, também é mostrado como podemos simpli ficar esta solução, reduzindo o número de regras necessárias, através de operações que envolvem as transições de estado ativas destas regras, i.e., aquelas que alteram o valor da célula central da vizinhança. Para tanto, são de nidas as operações de Particionamento (separação de transições ativas de uma regra em regras distintas), Junção (união de transições ativas de regras distintas em uma mesma regra) e Fusão (junção de todas as transições ativas das regras envolvidas, podendo remover algumas delas ou até mesmo incluir novas transições ativas para adequações desejadas). Utilizando-se dos mesmos conceitos e metodologia, propusemos ainda uma correção para a única regra proposta na literatura para resolver o Problema MOD2, o qual é conhecido como Problema da Paridade.

Submitted by Marta Toyoda (1144061@mackenzie.br) on 2018-09-03T21:53:40Z No. of bitstreams: 2 THIAGO DE MATTOS.pdf: 12639390 bytes, checksum: 3bda0715285cb44c6daf5752a11a5355 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Paola Damato (repositorio@mackenzie.br) on 2018-09-19T18:29:59Z (GMT) No. of bitstreams: 2 THIAGO DE MATTOS.pdf: 12639390 bytes, checksum: 3bda0715285cb44c6daf5752a11a5355 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2018-09-19T18:29:59Z (GMT). No. of bitstreams: 2 THIAGO DE MATTOS.pdf: 12639390 bytes, checksum: 3bda0715285cb44c6daf5752a11a5355 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2018-05-02 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Boolean networks consist of nodes that represent binary variables, which are computed as a function of the values represented by their adjacent nodes. This local processing entails global behaviors, such as the convergence to _xed points, a behavior found in the context of the density classi_cation problem, where the aim is the network's convergence to a fixed point of the prevailing node value in the initial global configuration of the network; in other words, a global decision is targeted, but according to a constrained, non-global action. In this work, we rely on evolutionary searches in order to _nd rules and network topologies with good performance in the task. All nodes' neighborhoods are assumed to be de_ned by non-regular and bidirectional links, and the Boolean function of the network initialized by the local majority rule. Firstly, is carried out a search in the space of network topologies, guided by the ω metric, related to the "small-worldness" of the networks, and then, in the space of Boolean functions, but constraining the network topologies to the best family identified in the previous experiment.. / Redes Booleanas são compostas por nós que representam variáveis binárias computadas em função dos valores representados por nós adjacentes. Esta computação local leva a comportamentos globais, como a convergência para um estado fixo da rede. Tal comportamento é utilizado na tarefa de classificação de densidade, onde procura-se a convergência dos valores de todos os nós para um ponto fixo que reflete o estado predominante presente na configuração inicial da rede, ou seja, um objetivo global restrito a ações de caráter local. Neste trabalho são efetuadas buscas evolutivas de modo a encontrar regras e topologias de redes Booleanas com boa performance na classificação de densidade. Consideram-se exclusivamente vizinhanças irregulares e bidirecionais para todos os nós, representando inicialmente a função Booleana da rede através da regra da maioria da vizinhança. Primeiramente, efetuam-se buscas evolutivas por topologias de redes guiadas pela métrica ω, esta referente à classificação de redes de mundo pequeno, e em seguida, efetuam-se buscas evolutivas no espaço de possíveis funções Booleanas utilizando as topologias de redes encontradas anteriormente.

O presente trabalho teve como foco o desenvolvimento de um software para a simulação de processos de microfabricação em substrato e de microfabricação em superfície baseado em autômatos celulares, o simMEMS. Além disso, visando a futura incorporação de ferramentas para análise das estruturas geradas pelo programa, um módulo com funcionalidades básicas para a análise mecânica de estruturas também foi desenvolvido. No que tange à microfabricação em superfície, o software desenvolvido permite simular a corrosão anisotrópica úmida do Si em KOH e deep reactive ion etching (DRIE). O simulador de corrosão úmida utiliza um autômato celular conhecido como BCA. O simulador de DRIE usa um autômato próprio. Para a simulação dos processos de microfabricação em superfície o software fornece quatro processos: deposição de filmes, corrosão de filmes, fotolitografia e planarização. Para corrosão e deposição de filmes, diversos autômatos celulares da literatura foram analisados e os resultados dessas análises é aqui apresentado. Todos os simuladores, tanto de microfabricação em superfície como em substrato, podem ser utilizados em conjunto. Isso torna o software bastante útil e capaz de simular a fabricação de um grande número de dispositivos. / The main goal of this project is the development of a software capable of simulating both surface and bulk micromachining based on a cellular automata approach. This software has been called simMEMS. In order to enable future versions of the software to also be able to analyze the structures created by the software, a module capable of running a mechanical analysis through the finite element method is also developed. simMEMS allows the user to simulate two bulk micromachining processes: wet anisotropic KOH etching and deep reactive ion etching DRIE. The wet etching simulator uses a cellular automaton known as BCA. The DRIE simulator uses an automaton developed during this project. The surface micromachining simulator allows the user to simulate four types of processes: photolithography, film deposition, film etching and substrate planarization. Several automata for the deposition and etching of films are studied and the results of this study are presented here. All processes, be they for surface or bulk micromachining, can be used on the same substrate to simulate the entire fabrication process for a large array of devices. This makes simMEMS a very useful software.

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.

No estudo de sistemas complexos interessa capturar a evolução do seu comportamento emergente segundo um conjunto de regras cujas soluções descrevem o seu estado ao longo do tempo. Uma classe particular de modelos matemáticos e computacionais que permite realizar essa investigação são os autômatos celulares. O comportamento global deles é definido apenas por regras locais, o que os tornam um modelo exemplar para estudos de sistemas complexos. Estamos interessados em um tipo especial de autômato celular: os classificadores de densidade unidimensionais. Este tipo de autômato celular está relacionado com o problema da maioria que consiste em fazer convergir uma cadeia de símbolos aleatoriamente distribuídos em um reticulado, para uma cadeia homogênea com um único símbolo final (consenso global), aquele de maioria inicial. Este consenso deve ser obtido exclusivamente a partir de interações locais entre os sítios sem a instância de um controle central. Nesta pesquisa, realizamos alguns experimentos para caracterizar um autômato celular classificador de quatro estados proposto em Gács, Kurdyumov e Levin (1978). Embora seja um classificador imperfeito, este autômato celular é significativamente tolerante a falhas quando o submetemos a níveis de ruídos não nulos. Os resultados corroboram com outros estudos que investigam a robustez deste tipo de autômato celular e lançam luz sobre o entendimento da origem da coordenação global de sistemas que exibem as características aqui descritas / In the study of complex systems we are interested in capturing their evolution of its emergent behavior under a set of rules whose solutions describe the state of the system over time. A particular class of mathematical and computational model to perform this kind of research is the cellular automaton (CA). Its global behavior is defined by local rules, which makes it an exemplary model to study complex systems. Here, we are interested in a particular type of CA: one-dimensional CA that classifies densities. This kind of CA is related to the problem of the majority task that consists of converging an array of symbols, initially randomly distributed, to a single symbol, the more frequent one in the initial configuration of the array (global consensus). This consensus must be obtained solely out of local interactions, without the instance of a central control. In this research, we conducted some experiments to characterize a four-state CA classifier proposed in Gács, Kurdyumov e Levin (1978). While it is an imperfect classifier, this CA is significantly fault tolerant when submitted to the levels of non-zero noise. Our results corroborate other studies that had investigated the robustness of this type of CA, and shed light on the understanding of the origin of global coordinated systems that exhibit the characteristics described here

Os Autômatos Celulares (ACs) são exemplos de sistemas discretos (variáveis, tempo e espaço) que se tornaram ferramentas importantes no estudo de Sistemas Complexos. A exemplo de outros sistemas desta classe, os ACs exibem um comportamento dinâmico complexo e imprevisível. Um aspecto bastante estudado dos Autômatos Celulares diz respeito a como eles realizam computações. Os ACs computam através de processamentos locais e intrinsecamente paralelos que interagem entre si, emergindo um comportamento global e coordenado. Outro aspecto muito estudado é a previsão do comportamento dinâmico de um AC a partir de sua definição. Já foi provado que esta previsão é um problema indecidível e vários esquemas aproximados existem na literatura. Neste trabalho, um conjunto de parâmetros de previsão de comportamento dinâmico de Autômatos Celulares unidimensionais foi proposto. Como meta para validar a eficácia destes parâmetros, eles foram utilizados para auxiliar a busca evolutiva de Autômatos Celulares específicos que executam determinadas tarefas computacionais. Tais parâmetros foram utilizados como heurísticas embutidas na avaliação de um Algoritmo Genético utilizado como ferramenta de busca dos ACs. Os resultados encontrados mostram que os parâmetros selecionados constituem ferramentas úteis na previsão do comportamento dinâmico de Autômatos Celulares unidimensionais, e podem efetivamente auxiliar na programação de um AC desse tipo para a realização de uma tarefa computacional especificada.

Apresentamos dois autômatos celulares com regras de interação locais que permitem descrever a dinâmica de população de um sistema predador-presa. Os modelos são definidos sobre uma rede regular quadrada e se diferenciam pelo caráter isotrópico ou anisotrópico da interação entre os sítios. A cada sítio é associada uma variável estocástica, que pode assumir três estados - vazio, presa ou predador. A dinâmica de competição entre espécies animais que nos interessa é a mesma descrita pelo modelo de Lotka-Volterra no qual as populações de presas e predadores oscilam temporalmente. Nosso objetivo é a análise dessas oscilações, como se comportam com o aumento da rede e se permanecem estáveis. Para a obtenção das séries temporais realizamos simulações de Monte Carlo. Para o autômato definido sobre o espaço isotrópico, também realizamos análise de campo médio dinâmico. Os resultados indicam que a oscilação é um efeito local (não sobrevive em sistemas infinitos), e é mais significativo devido à migração das espécies pelos subsistemas. O estudo da anisotropia revela alguns padrões espaciais organizados e que as oscilações são menos intensas do que no caso isotrópico e como consequência a fase ativa é mais abrangente. / We present two cellular automata with local interaction rules which allow us to describe the dynamical population of a predator-prey system. The models are defined on a regular square lattice and are distinguished by the isotropic or anisotropic character of the interaction between sites. To each site a stochastic variable is associated, which can assume three states- void, prey or predator. The competition dynamics between animal species which interest us is the same described by the Lotka-Volterra model in which the populations of preys and predators oscillate in time. Our aim is the analysis of these oscillations, how they behave with an increasing lattice and if they remain stable. In order to obtain temporal series we perform Monte Carlo simulations. For the automaton defined on isotropic space, dynamical mean field analysis was also performed. Results indicate that the oscillation is a local effect ( vanishing in infinite systems), and is more significant due to migration of species through the subsystems. The study of anisotropy reveals some organized spatial patterns and that oscillations are less intense than in the isotropic case and as a consequence the active phase is more comprehensive.

Made available in DSpace on 2017-07-21T19:25:54Z (GMT). No. of bitstreams: 1 Fernando da Silva Borges.pdf: 3003505 bytes, checksum: c77a390868c21644a0396314c4bf4e0e (MD5) Previous issue date: 2016-11-22 / Fundação Araucária de Apoio ao Desenvolvimento Científico e Tecnológico do Paraná / In this thesis, we use mathematical models to study the dynamic range of neural networks. The dynamic range is the difference between maximum and minimum levels of sensation produced by known stimuli. Using cellular automata to model neuronal dynamics and different network topologies with different types of synapses, we investigate for which conditions the dynamic range is enhanced. In a network where local connections represent the electrical synapses and nonlocal connections the chemical synapses, we analyze the dynamic range in function of the number of nonlocal connections and time delay between these connections. We find that the dynamic range is enhanced for neural networks with low time delay when the number of nonlocal connections increases. Furthermore, we propose a neural network model separated into two layers, where one layer corresponds to inhibitory and the other to excitatory neurons. We randomly distribute electrical and chemical synapses in the network in order to analyse the effects on the dynamic range. In our proposed model, the chemical synapses, that are directed, can be excitatory or inhibitory, while the electrical synapses are bidirectional. Through the mean-field approximation, we analytically calculate the dynamic range as a function of the model parameters. The values that we find are very close to the results obtained from simulations. We verify that electrical synapses have a complementary effect on the enhancement of the dynamic range. Finally, we found that electrical synapses on excitatory layer are responsible for this complementary effect, while the electrical synapses in inhibitory layer promote a small increase in the dynamic range value. / Nesta tese usamos modelos matemáticos para estudar a faixa dinâmica de redes neuronais. A faixa dinâmica é a diferença entre a resposta máxima e mínima produzida por um determinado estímulo. Utilizando autômatos celulares para modelar a dinamica neuronal e diversas topologias de redes com diferentes tipos de sinapses, investigamos para quais configurações a faixa dinamica ´e maximizada. Em uma rede onde conexões locais representam sinapses elétricas e conexões não locais as sinapses químicas, analisamos o que ocorre com a faixa dinamica quando varia-se a quantidade de conexões não locais ou um tempo de atraso entre essas conexões é considerado. Neste caso, verificamos que a faixa dinamica é maior para redes neuronais com valores baixos de atraso e aumenta com o acréscimo de conexões não locais. Além disso, propomos um modelo de rede de neurônios dispostos em duas camadas, uma excitatória e outra inibitótira, com sinapses química e elétricas distribuidas aleatoriamente. Neste modelo, as sinapses quimicas são direcionadas e podem ser excitatorias ou inibitórias, enquanto as sinapses elétricas são bidirecionais e apresentam apenas carater excitatorio. Fazendo aproximações de campo médio, calculamos analiticamente a faixa dinamica em função dos parametros do modelo. Os valores encontrados estão muito próximos dos obtidos por simulações e mostram que a faixa dinãmica é maximizada em pontos que dependem complementarmente das sinapses quimicas e elétricas. Finalmente, verificamos que as sinapses eletricas na camada excitatória sao responsaveis por esse efeito complementar, enquanto as sinapses elétricas na camada inibitoria promovem um pequeno acrescimo no valor da faixa dinamica.

No estudo de sistemas complexos interessa capturar a evolução do seu comportamento emergente segundo um conjunto de regras cujas soluções descrevem o seu estado ao longo do tempo. Uma classe particular de modelos matemáticos e computacionais que permite realizar essa investigação são os autômatos celulares. O comportamento global deles é definido apenas por regras locais, o que os tornam um modelo exemplar para estudos de sistemas complexos. Estamos interessados em um tipo especial de autômato celular: os classificadores de densidade unidimensionais. Este tipo de autômato celular está relacionado com o problema da maioria que consiste em fazer convergir uma cadeia de símbolos aleatoriamente distribuídos em um reticulado, para uma cadeia homogênea com um único símbolo final (consenso global), aquele de maioria inicial. Este consenso deve ser obtido exclusivamente a partir de interações locais entre os sítios sem a instância de um controle central. Nesta pesquisa, realizamos alguns experimentos para caracterizar um autômato celular classificador de quatro estados proposto em Gács, Kurdyumov e Levin (1978). Embora seja um classificador imperfeito, este autômato celular é significativamente tolerante a falhas quando o submetemos a níveis de ruídos não nulos. Os resultados corroboram com outros estudos que investigam a robustez deste tipo de autômato celular e lançam luz sobre o entendimento da origem da coordenação global de sistemas que exibem as características aqui descritas / In the study of complex systems we are interested in capturing their evolution of its emergent behavior under a set of rules whose solutions describe the state of the system over time. A particular class of mathematical and computational model to perform this kind of research is the cellular automaton (CA). Its global behavior is defined by local rules, which makes it an exemplary model to study complex systems. Here, we are interested in a particular type of CA: one-dimensional CA that classifies densities. This kind of CA is related to the problem of the majority task that consists of converging an array of symbols, initially randomly distributed, to a single symbol, the more frequent one in the initial configuration of the array (global consensus). This consensus must be obtained solely out of local interactions, without the instance of a central control. In this research, we conducted some experiments to characterize a four-state CA classifier proposed in Gács, Kurdyumov e Levin (1978). While it is an imperfect classifier, this CA is significantly fault tolerant when submitted to the levels of non-zero noise. Our results corroborate other studies that had investigated the robustness of this type of CA, and shed light on the understanding of the origin of global coordinated systems that exhibit the characteristics described here

Apresentamos dois autômatos celulares com regras de interação locais que permitem descrever a dinâmica de população de um sistema predador-presa. Os modelos são definidos sobre uma rede regular quadrada e se diferenciam pelo caráter isotrópico ou anisotrópico da interação entre os sítios. A cada sítio é associada uma variável estocástica, que pode assumir três estados - vazio, presa ou predador. A dinâmica de competição entre espécies animais que nos interessa é a mesma descrita pelo modelo de Lotka-Volterra no qual as populações de presas e predadores oscilam temporalmente. Nosso objetivo é a análise dessas oscilações, como se comportam com o aumento da rede e se permanecem estáveis. Para a obtenção das séries temporais realizamos simulações de Monte Carlo. Para o autômato definido sobre o espaço isotrópico, também realizamos análise de campo médio dinâmico. Os resultados indicam que a oscilação é um efeito local (não sobrevive em sistemas infinitos), e é mais significativo devido à migração das espécies pelos subsistemas. O estudo da anisotropia revela alguns padrões espaciais organizados e que as oscilações são menos intensas do que no caso isotrópico e como consequência a fase ativa é mais abrangente. / We present two cellular automata with local interaction rules which allow us to describe the dynamical population of a predator-prey system. The models are defined on a regular square lattice and are distinguished by the isotropic or anisotropic character of the interaction between sites. To each site a stochastic variable is associated, which can assume three states- void, prey or predator. The competition dynamics between animal species which interest us is the same described by the Lotka-Volterra model in which the populations of preys and predators oscillate in time. Our aim is the analysis of these oscillations, how they behave with an increasing lattice and if they remain stable. In order to obtain temporal series we perform Monte Carlo simulations. For the automaton defined on isotropic space, dynamical mean field analysis was also performed. Results indicate that the oscillation is a local effect ( vanishing in infinite systems), and is more significant due to migration of species through the subsystems. The study of anisotropy reveals some organized spatial patterns and that oscillations are less intense than in the isotropic case and as a consequence the active phase is more comprehensive.