Traditional parallel methods for structural design do not scale well. This thesis discusses the application of massively scalable cellular automata (CA) techniques to structural design. There are two sets of CA rules, one used to propagate stresses and strains, and one to perform design analysis. These rules can be applied serially, periodically, or concurrently, and Jacobi or Gauss-Seidel style updating can be done. These options are compared with respect to convergence, speed, and stability. / Master of Science

Because of perceived deficiencies in the state of the practice of designing escalators and moving walkways, a microsimulation-based model of pedestrian behavior in these moving belt systems was created. In addition to implementing walking and stair climbing capabilities from existing pedestrian flow literature, the model utilized following behavior and lane change decision logic taken form studies performed in the field of automotive traffic flow theory. By combining research from these two normally independent fields with moving belt operational characteristics, a solid framework for the simulation was created. The model was then validated by comparing its operation to real world behaviors and performance metrics found in the literature in order to verify that the simulation matched the choices made by actual pedestrians. Once this crucial function had been completed, the model could finally be used in its original purpose of determining the capacity of a belt under region-specific input parameters. This paper also discusses other applications for which the model is suitable, including performing sensitivity analysis of both existing and proposed belt systems, analyzing the impacts of operational rule sets on the performance of escalators and moving walkways, and analyzing the effect of queue growth on the storage area needed for pedestrians in an ambulatory facility. Through the use of this model and the logic contained within it, engineers and planners will be able to gain a more accurate understanding of pedestrian flow on moving belts. The result of this increased understanding will be more effective and more efficient transportation systems. / Master of Science

Every year three million deaths are attributed to malaria, of which one-third are of children. Malaria is a vector-borne disease, where a mosquito acts as the vector that transmits the disease. In the last few years, computer simulation based models have been used effectively to study the vector population dynamics and control strategies of vector-borne diseases. Typically, these models use ordinary differential equations to simulate the spread of malaria. Although these models provide a powerful mechanism to study the spread of malaria, they have several shortcomings. The research in this thesis focuses on creating a simulation model based on the framework of cellular automata, which addresses many shortcomings of previous models. Cellular automata are dynamical systems, which are discrete in time and space. The implementation of the model proposed can easily be integrated with EpiSims/TRANSIMS. EpiSims is an epidemiological modeling tool for studying the spread of infectious diseases; it uses social contact network from TRANSIMS (A Transport Analysis and Simulation System). Simulation results from the prototype implementation showed qualitatively correct results for vector densities, diffusion and epidemiological curves. / Master of Science

Structural analysis and design optimization is important to a wide variety of disciplines. The current methods for these tasks require significant time and computing resources. Reconfigurable computers have shown the ability to speed up many applications, but are unable to handle efficiently the precision requirements for traditional analysis and optimization techniques. Cellular automata theory provides a method to model these problems in a format conducive to representation on a reconfigurable computer. The calculations do not need to be executed with high precision and can be performed in parallel. By implementing cellular automata simulations on a reconfigurable computer, structural analysis and design optimization can be performed significantly faster than conventional methods. / Master of Science

Em condições acentuadas de restrições de recursos para a construção e manutenção de infra-estruturas urbanas, torna-se importante caracterizar e localizar espacialmente sua demanda para auxiliar os planejadores no processo decisório que envolve sua implementação, ampliação e manutenção, de forma que os usuários sejam atendidos da melhor maneira possível e dentro das possibilidades financeiras das prefeituras. Este foi o ponto de partida para este trabalho, cujos objetivos são modelar a dinâmica populacional intra-urbana de uma cidade de médio porte brasileira através da combinação de modelos com cellular automata e avaliação multicritério e, a partir daí, a distribuição de viagens para uma infra-estrutura pontual específica, as Escolas Municipais de Educação Infantil (EMEIs). Na aplicação prática da pesquisa inicialmente modela-se a dinâmica populacional intra-urbana na cidade de São Carlos como um todo com um modelo de cellular automata e um modelo demográfico de extrapolação de tendências. Baseando-se em valores de densidade populacional obtidos com dados dos censos do IBGE referentes aos anos de 1980, 1991 e 2000, obteve-se o cenário referente ao ano de 2010. O modelo urbano de cellular automata utilizado foi construído em três fases: quantificação da dispersão (cálculo da área total que deveria ser incorporada à mancha urbana), localização da dispersão (definição da localização das áreas que deveriam ser incorporadas à mancha urbana) e diferenciação da dispersão (cálculo das densidades demográficas na mancha urbana prevista). O modelo conseguiu apresentar bons resultados tanto na localização quanto na diferenciação da dispersão. Para caracterizar a demanda por EMEIs neste caso estabeleceu-se uma relação matemática entre a população total e a população na faixa etária que utiliza o serviço das EMEIs (4 a 6 anos). No caso do modelo demográfico, no qual a densidade populacional foi calculada a partir de uma curva de tendência linear, notou-se que devido à restrição da mancha urbana à área previamente ocupada, surgem valores de densidade populacional acima da faixa observada na série histórica. A demanda por EMEIs neste modelo também foi obtida através de uma curva de tendência linear, utilizando dados específicos da faixa etária de 4 a 6 anos. Após a caracterização da demanda por EMEIs foram criados cenários de distribuição de viagens para as mesmas nos anos de 2000 e 2010. Observou-se que os modelos apresentaram comportamentos distintos na caracterização da demanda, que foi expressivamente maior no modelo de cellular automata mas quando tiveram a demanda adaptada à oferta existente, através da multiplicação por uma taxa de atendimento, apresentaram resultados bastante semelhantes. No entanto, considerando um cenário muito provável de aumento da oferta, seja em escolas novas ou nas já existentes, o impacto sobre os transportes seria muito melhor caracterizado no caso dos modelos de CA, não só porque as estimativas de demanda foram significativamente maiores, mas também porque incorporaram a possibilidade de ocupação de novas áreas urbanas / In conditions of extreme restrictions of resources for construction and maintainance of public facilities, the correct demand alocation is essential not only for the decision-making process, which involves their implementation and rational use, but also for reaching a significant share of the demand with a reasonable level of service and within the budget limits. That was the starting point for the definition of the objectives of this work, which are to model the population dynamics in a medium-sized city by using a cellular automata approach and multicriteria evaluation techniques and to simulate trip distribution patterns to a particular public facility, the EMEIs, i.e., schools for children between 4 and 6 years-old. The study starts with an application of two urban dynamics models in the city of São Carlos: a cellular automata model and a demographic model based on linear regression. A scenario of the year 2010 was built based on 1980, 1991, and 2000 census data. The cellular automata model was constructed in three fases: quantification of sprawl (definition of the total area added to the existing urban area), location of sprawl (alocation of areas of expansion), and differentiation of sprawl (definition of the population density in each cell of the new urban area). The model captured reasonably well the urban dynamics process in both location and differentiation of sprawl. The demand for EMEIs was then defined through the definition of a mathematical relationship between the total population and the target population. The population density predicted by the demographic model was calculated through a linear trend applied to historical data. It was significant in this case the occurrence of estimated values higher than the actual values mainly due to the restrictions of the urban area to its previous boundaries. The demand for EMEIs was also obtained using a linear trend, this time using specific data of the target population. Scenarios of trip distribution in the years 2000 and 2010 were created after the demand was modeled. The predictions of the models were very different, and the total demand estimation of the cellular automata model was higher than that obtained with the demographic model. When adjusting the demand to the existing supply in the year 2000, the trip distribution results were quite similar, although resulting in extremely different service rates. However, in a very likely scenario of supply growth, either through new or existing schools, the impacts on transportation would be better identified in the case of CA models, not only because they have produced higher demand estimates, but also because they have considered the inclusion of new areas into the modeled space

Em condições acentuadas de restrições de recursos para a construção e manutenção de infra-estruturas urbanas, torna-se importante caracterizar e localizar espacialmente sua demanda para auxiliar os planejadores no processo decisório que envolve sua implementação, ampliação e manutenção, de forma que os usuários sejam atendidos da melhor maneira possível e dentro das possibilidades financeiras das prefeituras. Este foi o ponto de partida para este trabalho, cujos objetivos são modelar a dinâmica populacional intra-urbana de uma cidade de médio porte brasileira através da combinação de modelos com cellular automata e avaliação multicritério e, a partir daí, a distribuição de viagens para uma infra-estrutura pontual específica, as Escolas Municipais de Educação Infantil (EMEIs). Na aplicação prática da pesquisa inicialmente modela-se a dinâmica populacional intra-urbana na cidade de São Carlos como um todo com um modelo de cellular automata e um modelo demográfico de extrapolação de tendências. Baseando-se em valores de densidade populacional obtidos com dados dos censos do IBGE referentes aos anos de 1980, 1991 e 2000, obteve-se o cenário referente ao ano de 2010. O modelo urbano de cellular automata utilizado foi construído em três fases: quantificação da dispersão (cálculo da área total que deveria ser incorporada à mancha urbana), localização da dispersão (definição da localização das áreas que deveriam ser incorporadas à mancha urbana) e diferenciação da dispersão (cálculo das densidades demográficas na mancha urbana prevista). O modelo conseguiu apresentar bons resultados tanto na localização quanto na diferenciação da dispersão. Para caracterizar a demanda por EMEIs neste caso estabeleceu-se uma relação matemática entre a população total e a população na faixa etária que utiliza o serviço das EMEIs (4 a 6 anos). No caso do modelo demográfico, no qual a densidade populacional foi calculada a partir de uma curva de tendência linear, notou-se que devido à restrição da mancha urbana à área previamente ocupada, surgem valores de densidade populacional acima da faixa observada na série histórica. A demanda por EMEIs neste modelo também foi obtida através de uma curva de tendência linear, utilizando dados específicos da faixa etária de 4 a 6 anos. Após a caracterização da demanda por EMEIs foram criados cenários de distribuição de viagens para as mesmas nos anos de 2000 e 2010. Observou-se que os modelos apresentaram comportamentos distintos na caracterização da demanda, que foi expressivamente maior no modelo de cellular automata mas quando tiveram a demanda adaptada à oferta existente, através da multiplicação por uma taxa de atendimento, apresentaram resultados bastante semelhantes. No entanto, considerando um cenário muito provável de aumento da oferta, seja em escolas novas ou nas já existentes, o impacto sobre os transportes seria muito melhor caracterizado no caso dos modelos de CA, não só porque as estimativas de demanda foram significativamente maiores, mas também porque incorporaram a possibilidade de ocupação de novas áreas urbanas / In conditions of extreme restrictions of resources for construction and maintainance of public facilities, the correct demand alocation is essential not only for the decision-making process, which involves their implementation and rational use, but also for reaching a significant share of the demand with a reasonable level of service and within the budget limits. That was the starting point for the definition of the objectives of this work, which are to model the population dynamics in a medium-sized city by using a cellular automata approach and multicriteria evaluation techniques and to simulate trip distribution patterns to a particular public facility, the EMEIs, i.e., schools for children between 4 and 6 years-old. The study starts with an application of two urban dynamics models in the city of São Carlos: a cellular automata model and a demographic model based on linear regression. A scenario of the year 2010 was built based on 1980, 1991, and 2000 census data. The cellular automata model was constructed in three fases: quantification of sprawl (definition of the total area added to the existing urban area), location of sprawl (alocation of areas of expansion), and differentiation of sprawl (definition of the population density in each cell of the new urban area). The model captured reasonably well the urban dynamics process in both location and differentiation of sprawl. The demand for EMEIs was then defined through the definition of a mathematical relationship between the total population and the target population. The population density predicted by the demographic model was calculated through a linear trend applied to historical data. It was significant in this case the occurrence of estimated values higher than the actual values mainly due to the restrictions of the urban area to its previous boundaries. The demand for EMEIs was also obtained using a linear trend, this time using specific data of the target population. Scenarios of trip distribution in the years 2000 and 2010 were created after the demand was modeled. The predictions of the models were very different, and the total demand estimation of the cellular automata model was higher than that obtained with the demographic model. When adjusting the demand to the existing supply in the year 2000, the trip distribution results were quite similar, although resulting in extremely different service rates. However, in a very likely scenario of supply growth, either through new or existing schools, the impacts on transportation would be better identified in the case of CA models, not only because they have produced higher demand estimates, but also because they have considered the inclusion of new areas into the modeled space

The following dissertation addresses the study of nano-magnetic devices configured to produce logic machines through magnetostatic coupling interactions. The ability for single domain magnets to reliably couple through magnetostatic interactions is essential to the proper functionality of Magnetic Cellular Automata (MCA) devices (p. 36). It was significant to explore how fabrication defects affected the coupling reliability of MCA architectures. Both ferromagnetic and anti-ferromagnetic coupling architectures were found to be robust to common fabrication defects. Experiments also verified the functionality of the previously reported MCA majority gate [1] and a novel implementation of a ferromagnetic MCA majority gate is reported. From these results, the study of clocking Magnetic Cellular Automata (MCA) interconnect architectures was investigated (p. 54). The wire architectures were saturated under distinct directions of an external magnetic field. The experimental results suggested ferromagnetic coupled wires were able to mitigate magnetic frustrations better than anti-ferromagnetic coupled wires. Simulations were also implemented supporting the experimental results. Ferromagnetic wires were found to operate more reliably and will likely be the primary interconnects for MCA. The first design and implementation of a coplanar cross wire system for MCA was constructed which consisted of orthogonal ferromagnetic coupled wires (p. 68). Simulations were implemented of a simple crossing wire junction to analyze micro-magnetic dynamics, data propagation, and associated energy states. Furthermore, two systems were physically realized; the first system consisted of two coplanar crossing wires and the second was a more complex system consisting of over 120 nano-magnetic cells. By demonstrating the combination of all the possible logic states of the first system and the low ground state achieved by the second system, the data suggested coplanar cross wire systems would indeed be a viable architecture in MCA technology. Finally, ongoing research of an unconventional method for image processing using nano-magnetic field-based computation is presented (p. 79). In magnetic field-based computing (MFC), nano-disks were mapped to low level segments of an image, and the magnetostatic coupling of magnetic dipole moments was directly related to the saliency of a low level segment for grouping. A proof of concept model for two MFC systems was implemented. Details such as the importance of fabricating circular nano-magnetic cells to mitigate shape anisotropy, experimental coupling analysis via Magnetic Force Microscopy, and current results from a complex MFC system is outlined.

Manual design of levels can be an expensive and time consuming process. Procedural content generation (PCG) entails methods to algorithmically generate game content such as levels. One such way is by using cellular automata (CA), and in particular evolved cellular automata. Existing research primarily considers specifically determined starting states, as opposed to randomly initialized ones. In this paper we investigate the current state of the art regarding using CA’s that have been evolved with a genetic algorithm (GA) for level generation purposes. Additionally, we create a level generator that uses a GA in order to evolve CA rules for the creation of maze-like 2d levels which can be used in video games. Specifically, we investigate if it is possible to evolve CA rules that, when applied to a set of random starting states, could transform these into game levels with long solution paths and a large number of dead ends. We generate 60 levels over 6 experiments, rendering 58 playable levels. Our analysis of the levels show some flaws in certain levels, such as large numbers of unreachable cells. Additionally, the results indicate that the designed GA can be further improved upon. Finally, we conclude that it is possible to evolve CA rules that can transform a set of random starting states into game levels.

The goal of this master thesis is to examine possibilities of realizing comptutational structures in cellular automata. The work describes the fundamental principles of cellular automata and summarizes some ways of how to achive the specified goal. An overview of Turing-complete and other specialized computational tasks is proposed considering both 1D and 2D cellular automata. It is shown that different computational scenarios in cellular automata can be considered with various setups of the input and output arrangements. With regard to showed inputs and outputs arrangement, sets of tests is designed to find solutions of choosen computational structures on cellular automata with use of choosen evolutionary algorithm. Found solutions are compared by computational resources consumption and difficulty of discovery later.

A problem in computer security is identification of attack signatures in network packets. An attack signature is a pattern of bits that characterizes a particular attack. Because there are many kinds of attacks, there are potentially many attack signatures. Furthermore, attackers may seek to avoid detection by altering the attack mechanism so that the bit pattern presented differs from the known signature. Thus, recognizing attack signatures is a problem in approximate string matching. The time to perform an approximate string match depends upon the length of the string and the number of patterns. For constant string length, the time to matchnpatterns is approximatelyO(n); the time increases approximately linearly as the number of patterns increases. A binary cellular automaton is a discrete, deterministic system of cells in which each cell can have one of two values. Cellular automata have the property that the next state of each cell can be evaluated independently of the others. If there is a processing element for each cell, the next states of all cells in a cellular automaton can be computed simultaneously. Because there is no programming paradigm for cellular automata, cellular automata to perform specific functions are createdad hocby hand or discovered using search methods such as genetic algorithms. This research has identified, through evolution by genetic algorithm, cellular automata that can perform approximate string matching for more than one pattern while operating in constant time with respect to the number of patterns, and in the presence of noise. Patterns were recognized by using the bits of a network packet payload as the initial state of a cellular automaton. After a predetermined number of cycles, the ones density of the cellular automaton was computed. Packets for which the ones density was below an experimentally determined threshold were identified as target packets. Six different cellular automaton rules were tested against a corpus of 7.2 million TCP packets in the IDEval data set. No rule produced false negative results, and false positive results were acceptably low.