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

<p align="justify">Computer Science is currently facing a grand challenge : finding good design practices for embedded systems. Embedded systems are essentially computers interacting with some physical process. You could find one in a braking systems or in a nuclear power plant for example. They present several design difficulties : first they are reactive systems, interacting indefinitely with their environment. Second,they must satisfy real-time constraints specifying when they should respond, and not only how. Finally, their environment is often deeply continuous, presenting complex dynamics. The formal models of choice for specifying such systems are timed and hybrid automata for which model checking is pretty well studied.</p> <p align="justify">In a first part of this thesis, we study a complete design approach, including verification and code generation, for timed automata. We have to define a new semantics for timed automata, the AASAP semantics, that preserves the decidability properties for model checking and at the same time is implementable. Our notion of implementability is completely novel, and relies on the simulation of a semantics that is obviously implementable on a real platform. We wrote tools for the analysis and code generation and exemplify them on a case study about the well known Philips Audio Control Protocol.</p> <p align="justify">In a second part of this thesis, we study the problem of controller synthesis for an environment specified as a hybrid automaton. We give a new solution for discrete controllers having only an imperfect information about the state of the system. In the process, we defined a new algorithm, based on the monotonicity of the controllable predecessors operator, for efficiently finding a controller and we show some promising applications on a classical problem : the universality test for finite automata.

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

<p>This thesis is a survey of the field of languages over infinite sequences. There is active research going on in this field, during the last year several new results where published. </p><p>We investigate the language containment problem for infinite sequences, with focus on complementation of Büchi automata. Our main focus is on the approach with alternating automata by Kupferman&Vardi. The language containment problem has been proved to be in EXPSPACE. We identify some cases when we can avoid the exponential blow-up by taking advantage of properties of the input automaton. </p><p>Some of the algorithms we explain are also implemented in a Sicstus Prolog library.</p>

This dissertation is devoted to various aspects of groups generated by automata. We study particular classes and examples of such groups from different points of view. It consists of four main parts. In the first part we study Sushchansky p-groups introduced in 1979 by Sushchansky in "Periodic permutation p-groups and the unrestricted Burnside problem". These groups represent one of the earliest examples of Burnside groups and, at the same time, show the potential of the class of groups generated by automata to contain groups with extraordinary properties. The original definition is translated into the language of automata. The original actions of Sushchansky groups on p- ary tree are not level-transitive and we describe their orbit trees. This allows us to simplify the definition and prove that these groups admit faithful level-transitive actions on the same tree. Certain branch structures in their self-similar closures are established. We provide the connection with so-called G groups introduced by Bartholdi, Grigorchuk and Suninc in "Branch groups" that shows that all Sushchansky groups have intermediate growth and allows us to obtain an upper bound on their period growth functions. The second part is devoted to the opposite question of realization of known groups as groups generated by automata. We construct a family of automata with n states, n greater than or equal to 4, acting on a rooted binary tree and generating the free products of cyclic groups of order 2. The iterated monodromy group IMG(z2+i) of the self-map of the complex plain z -> z2 + i is the central object of the third part of dissertation. This group acts faithfully on the binary rooted tree and is generated by 4-state automaton. We provide a self-similar measure for this group giving alternative proof of its amenability. We also compute an L-presentation for IMG(z2+i) and provide calculations related to the spectrum of the Markov operator on the Schreier graph of the action of IMG(z2 + i) on the orbit of a point on the boundary of the binary rooted tree. Finally, the last part is discussing the package AutomGrp for GAP system developed jointly by the author and Yevgen Muntyan. This is a very useful tool for studying the groups generated by automata from the computational point of view. Main functionality and applications are provided.

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.

Models based on various types of automata are ubiquitous in modern science. These models allow reasoning about deep theoretical questions and provide a basis for the development of efficient algorithms to solve related computational problems. This work discusses several types of automata used in such models, including cellular automata and mandatory results automata. The first part of this work is dedicated to cellular automata. These automata form an important class of discrete dynamical systems widely used to model physical, biological, and chemical processes. Here we discuss a way to study the dynamics of one-dimensional cellular automata through the theory of two-dimensional picture languages. The connection between cellular automata and picture languages stems from the fact that the set of all space-time diagrams of a cellular automaton defines a picture language. We will discuss a hierarchy of cellular automata based on the complexity of the picture languages that they define. In addition to this, we present a characterization of cellular automata that can be described by finite-state transducers. The second part of this work presents a theory of runtime enforcement based on mech- anism models called Mandatory Results Automata (MRAs). MRAs can monitor and trans- form security-relevant actions and their results. Because previous work could not model general security monitors transforming results, MRAs capture realistic behaviors outside the scope of previous models. MRAs also have a simple but realistic operational seman- tics that makes it straightforward to define concrete MRAs. Moreover, the definitions of policies and enforcement with MRAs are significantly simpler and more expressive than those of previous models. Putting all these features together, we argue that MRAs make good general models of (synchronous) runtime mechanisms, upon which a theory of run- time enforcement can be based. We develop some enforceability theory by characterizing the policies deterministic and nondeterministic MRAs enforce.

Finite automata appear in almost every branch of computer science, for example in model checking, in natural language processing and in database theory. In many applications where finite automata occur, it is highly desirable to deal with automata that are as small as possible, in order to save memory as well as excecution time. Deterministic finite automata (DFAs) can be minimized efficiently, i.e., a DFA can be converted to an equivalent DFA that has a minimal number of states. This is not the case for non-deterministic finite automata (NFAs). To minimize an NFA we need to compute the corresponding DFA using subset construction and minimize the resulting automaton. However, subset construction may lead to an exponential blow-up in the size of the automaton and therefore even if the minimal DFA may be small, it might not be feasible to compute it in practice since we need to perform the expensive subset construction. To aviod subset construction we can reduce the size of an NFA using heuristic methods. This can be done by identifying and collapsing states that are equal with respect to some suitable equivalence relation that preserves the language of the automaton. The choice of an equivalence relation is a trade-off between the desired amount of reduction and the computation time since the coarser a relation is, the more expensive it is to compute. This way we obtain a reduction method for NFAs that is useful in practice. In this thesis we address the problem of reducing the size of non-deterministic automata. We consider two different computation models: finite tree automata and finite automata. Finite automata can be seen as a special case of finite tree automata and all of the previously mentioned results concerning finite automata are applicable to tree automata as well. For non-deterministic bottom-up tree automata, we present a broad spectrum of different relations that can be used to reduce their size. The relations differ in their computational complexity and reduction capabilities. We also provide efficient algorithms to compute the relations where we translate the problem of computing a given relation on a tree automaton to the problem of computing the relation on a finite automaton. For finite automata, we have extended and re-formulated two algorithms for computing bisimulation and simulation on transition systems to operate on finite automata with alphabets. In particular, we consider a model of automata where the labels are encoded symbolically and we provide an algorithm for computing bisimulation on this partial symbolic encoding.

Most of the cryptosystems currently used are based on number theoretic problems. We focus on cryptosystems based on finite automata (FA) which are lightweight in nature and have relatively small key sizes. The security of these systems relies on the difficulties in inverting non-linear finite automata and factoring matrix polynomials. In symmetric or single key encryption, the secret key consists of two finite automata and their inverses. By applying the inverses of the automata to the cipher text, the plain text can be effectively calculated. In case of asymmetric or public key encryption, the public key consists of another automaton, which is the combination of the two finite automata while the private key consists of the inverse of the two individual automata. It is hard to invert the combined automaton without the knowledge of the private key automata. We propose a third variant which is based on a 128-bit key and uses a DES-based key generation algorithm. We implement and test all three cryptosystems - the standard single key and public key cryptosystems as well as our novel DES-based FA cryptosystem. We also extensively test the finite automata cryptosystems on a standard desktop machine as well as the Nokia N900 smartphone. All statistical tests carried out on the ciphertext are satisfactory. / Graduate