Thesis (MSC (Mathematical Sciences. Computer Science))--Stellenbosch University, 2008. / This thesis describes the design and implementation of an application names GrailKnights that allows for the mass manipulation of automata, with added visual pattern analysis features. It comprises a database-driven backend for automata storage, and a graphical user interface that allows for filtering the automata selected from the database with visual interpretation of visible patterns over the resulting automata.

Investigações da dinâmica crítica em modelos de magnetismo, para tempos curtos, têm aparecido com grande freqüência na literatura. Essa técnica foi descoberta por Li, Schülke e Zheng que, inspirados em trabalhos anteriores de Huse e Janssen et al., mostraram que generalizações de grandezas como a magnetização e o cumulante de Binder exibem comportamento universal já no início da simulação. O estudo da criticalidade em tempos curtos proporciona um caminho alternativo para a estimativa do expoente z, além de permitir o cálculo de um novo expoente dinâmico θ, associado ao comportamento anômalo da magnetização. Da mesma forma, simulações dependentes do tempo tornaram-se ferramenta útil para estudar transições de fase em autômatos celulares e modelos de spin. Em particular, as melhores estimativas para o expoente z do Ising bidimensional foram obtidas por meio da técnica de propagação de danos, introduzida por Kauffman no estudo de autômatos e mais tarde generalizada para modelos de spin. Na primeira parte deste trabalho utilizamos o método Monte Carlo em tempos curtos para investigar o modelo de Baxter-Wu, definido em uma rede bidimensional triangular com variáveis do tipo Ising, acopladas por interações de três corpos. Obtivemos os expoentes críticos dinâmicos z e θ além dos índices críticos estáticos ß e Nû. Os resultados não corroboram aqueles recentemente obtidos por Santos e Figueiredo para o expoente z. Na segunda parte do trabalho, investigamos a propagação de danos no modelo de Ising unidimensional submetido a duas dinâmicas propostas por Hinrichsen e Domany (HD). Em particular, nós estudamos o efeito da atualização síncrona (paralela) e assíncrona (dinâmica contínua) sobre o espalhamento do dano. Mostramos que o dano não se propaga quando a segunda dinâmica é implementada de forma assíncrona. Também mostramos que as regras para atualização do dano produzidas por essa dinâmica, quando a temperatura vai a infinito e um certo parâmetro Lambda é igual a zero, são equivalentes àquelas do bem conhecido autômato celular (modelo A) de Grassberger. / Short-time simulations have been used with great frequency in the literature. That technique was discovered by Li, Shülke and Zheng that, inspired in previous works by Huse and Janssen et al., showed that generalizations of quantities like magnetization and the Binder´s cumulant exhibit universal behavior in the beginning of the simulation (early time behavior). The study of criticality in short-times provides an alternative way to estimate the dynamic critical exponent z, besides allowing the calculation of a new dynamic exponent θ, associated to the anomalous behavior of the magnetization. In the same way, time-dependent simulations became a useful tool to study phase transitions in cellular automata and also for spin models. In fact, the best estimates for the exponent z of the two-dimensional Ising model were obtained through the technique of damage spreading, introduced by Kauffman in the study of cellular automata, later widespread for spin models. In the first part of this work we used short-time Monte Carlo simulations to investigate the Baxter-Wu model, defined in a triangular lattice whose variables are Ising-like coupled by triplet interactions. We have obtained estimates for the dynamic critical exponents z and θ besides static exponents ß e Nû. Our results do not corroborate recent estimates by Santos and Figueiredo for the critical exponent z. In the second part of this work, we investigated the damage spreading in the one-dimensional Ising model under two dynamics introduced by Hinrichsen and Domany (HD). In particular, we study the effects of synchronous (parallel) and asynchronous (continuous dynamics) updating on the spreading properties. We showed that the damage does not spread when the second dynamic is implemented in an asynchronous way. We found that the rules for updating the damage produced by this dynamic, as the temperature goes to infinity and a certain parameter Lambda is zero, are equivalent to those of Grassberger’s well-known model A cellular automaton.

Made available in DSpace on 2016-03-15T19:38:04Z (GMT). No. of bitstreams: 1 ANA LEDA SILVA MORAES.pdf: 1708515 bytes, checksum: 8e07dd190f9a5fd165c14e35c2c626b0 (MD5) Previous issue date: 2016-02-01 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Epidemiology is the science that studies the occurrence of diseases in a population. The results of these studies allow a comprehension of a disease propagation and enable actions in order to control epidemics. There are many mathematical models used in epidemiological studies; in which SIR-like models are the most used. In this model, the population is divided into three groups: S - susceptible individuals to infection, I - infected individuals, and R - recovered individuals. The proposal of this thesis is, based on a new SIR model, taking into consideration the effect of recovered individuals on the propagation of contagious diseases and on the recovery of sick individuals. This can be relevant to the study of propagation of typical diseases in children, since immune individuals can catalyze the encounters among susceptible children and infected children, as well as to contribute to the recovery of sick individuals. The predictive ability of the proposed model is evaluated from the records refering to the incidence of chickenpox in Belgium, Germany and Italy, in a pre-vaccination era. / Epidemiologia é a ciência que estuda as ocorrências de doenças numa população. Os resultados desses estudos permitem uma compreensão do comportamento da incidência da doença e possibilita ações a fim de controlar epidemias. Há vários modelos matemáticos que são utilizados para estudos epidemiológicos, sendo modelos do tipo SIR os mais empregados. Nesse modelo, divide-se a população em três classes: 𝑆 - indivíduos suscetíveis à infecção, 𝐼 - indivíduos infectados, e 𝑅 - indivíduos recuperados. A proposta desta dissertação é, a partir de um novo modelo SIR, levar em consideração o efeito de indivíduos recuperados na propagação de doenças contagiosas e na recuperação de indivíduos doentes. Isso pode ser relevante no estudo da propagação de infecções típicas de crianças, já que indivíduos imunes podem servir como catalisador de encontros entre crianças suscetíveis e crianças infectadas, bem como contribuir para a recuperação de indivíduos doentes. A capacidade preditiva do modelo proposto é avaliada a partir dos registros referentes à incidência de varicela na Alemanha, Bélgica e Itália, numa era pré-vacinação.

Made available in DSpace on 2016-03-15T19:38:51Z (GMT). No. of bitstreams: 1 Pericles do Prado Turnes Junior.pdf: 1375255 bytes, checksum: 24dc630ef135368b840995d533e161e8 (MD5) Previous issue date: 2014-07-29 / Instituto Presbiteriano Mackenzie / There are many epidemiological models written in terms of ordinary differential equations (ODE). This approach is based on the homogeneous mixing assumption; that is, the topological structure of the network of social contacts, established by the individuals in the population, is not relevant to forecast the propagation of the studied pathogen. In this work, an epidemiological model formulated in terms of ODE and probabilistic cellular automata (PCA) is proposed to study the spread of contagious diseases that do not conferimmunity. The state variables of this model are the percentages of susceptible individuals, infected individuals and empty space. It is shown that this dynamical system can experience Hopf and transcritical bifurcations. Then, this model is used to evaluate the validity of the homogeneous mixing assumption, by using real data related to the transmission of gonorrhea, hepatitis C virus, human immunodeficiency virus and obesity. / Muitos modelos epidemiológicos são escritos em termos de equações diferenciais ordinárias (EDO). Essa abordagem baseia-se no pressuposto de mistura homogênea; ou seja, a estrutura topológica da rede de contatos sociais, estabelecida pelos indivíduos da população, não é relevante para prever o avanço do patógeno em estudo. Neste trabalho, é proposto um modelo epidemiológico formulado em termos de EDO e de autômato celular probabilista (ACP) para estudar a propagação de doenças contagiosas que não conferem imunidade. As variáveis de estado desse modelo são as porcentagens de indivíduos suscetíveis, de indivíduos infectados e de espaço vazio. Mostra-se que esse sistema dinâmico pode apresentar bifurcações de Hopf e transcrítica. O modelo é , então, usado para avaliar a validade da hipótese de mistura homogênea, usando dados relacionados à transmissão de gonorreia, vírus da hepatite C, vírus da imunodeficiência humana e obesidade.

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.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-04-25T11:55:26Z No. of bitstreams: 1 wolmararaujoneto.pdf: 9045744 bytes, checksum: 685167b5aabc68d680681643c44b7a4e (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-04-25T12:12:34Z (GMT) No. of bitstreams: 1 wolmararaujoneto.pdf: 9045744 bytes, checksum: 685167b5aabc68d680681643c44b7a4e (MD5) / Made available in DSpace on 2017-04-25T12:12:34Z (GMT). No. of bitstreams: 1 wolmararaujoneto.pdf: 9045744 bytes, checksum: 685167b5aabc68d680681643c44b7a4e (MD5) Previous issue date: 2014-08-25 / CNPq - Conselho Nacional de Desenvolvimento Científico e Tecnológico / A presente dissertação tem como objetivo principal desenvolver uma metodologia capaz de auxiliar no projeto e implementação de controles para sistemas a eventos discretos (SED) de forma a otimizar a modelagem, documentação e implantação da planta estudada. Para tanto a definição tradicional de autômato foi alterado para incluir um novo subconjunto de estados obrigatórios, isto é, estados que o sistema deve passar antes de chegar a um estado marcado. Seguindo a modelagem tradicional, cada subsistema é modelado através desta nova abordagem. Em uma segunda etapa, uma nova iteração de análise de cada subsistema é realizada para restringir situações indesejadas do sistema. Com esta fase finalizada os subsistemas são mesclados através de uma técnica tradicional de autômatos em paralelo. O sistema final resultante é apresentado a um otimizador, baseado em PROLOG, que busca a melhor sequência de eventos obedecendo a todas as restrições modeladas e termine no estado marcado informado pelo projeto. Este resultado fornece a Rede de Petri ideal do sistema e sua programação em GRAFCET. Tais métodos serão testados em componentes de um sistema de manufatura flexível real. / The present master thesis has as its main goal to develop a methodology able to assist in design and implementation of discrete event system (DES) controllers in order to optimize the modeling, documentation and deployment of plant in study. To do so the automaton traditional concept was changed to include a new subset of mandatory states, i.e. states that the system should pass before reach a marked state. Following the traditional modeling, each subsystem is modeled using this new approach. In a second step, a new iteration of analysis of each subsystem is performed to restrain system’s unwanted situations. At the end of this step the subsystems are composed by a traditional parallel automatons technique. The resulting system is presented to an optimizer, based in PROLOG, which searches the best event sequence obeying to all modeled restrictions and ends in the marked state defined in design. This result provides the ideal Petri Net of the system and its GRAFCET programming. Such methods will be tested in a flexible real manufacturing system.

Cette thèse a pour objectif de proposer des solutions aux problématiques de la narration interactive. Nous souhaitons ainsi proposer une méthode de conception pour les auteurs, ainsi qu’une logique d’exécution utilisant ce modèle pour contrôler la construction d’un récit. Nous appliquons nos travaux au contexte des jeux vidéo, mais souhaitons adresser la narration interactive dans une dimension plus large. Nous abordons la narration interactive comme une déstructuration de la narration classique. Le processus de création du récit n’est ainsi plus à la seule charge de l’auteur, mais implique également le public. Au travers d’une revue de la narration classique, nous souhaitons donc, dans un premier temps, formaliser le récit et ses enjeux. Nous utilisons ensuite le concept d’œuvre en mouvement pour identifier les processus et acteurs mis en jeu dans la coproduction d’une œuvre, et ainsi définir les enjeux de nos travaux. Pour adresser ces problématiques, nous proposons un modèle de la narration interactive à base d’automates. Celui-ci permet un contrôle et une vérification des récits possibles, tant lors de la conception, que dynamiquement à l’exécution. Cependant ce formalisme peut être complexe à prendre en main pour des auteurs non-initiés. Ainsi, nous formulons un modèle de haut-niveau, basé sur les concepts de la narratologie, permettant à ces derniers de créer un modèle de narration interactive en manipulant des concepts qu’ils maitrisent. Ce modèle est alors converti vers notre modèle à base d’automates. Ce dernier sert alors de référent pour le contrôle dynamique de la narration interactive par un superviseur multi-agents. Celui-ci, par observation des évènements produits dans le jeu vidéo, est alors en mesure de contrôler le récit en cours de production pour garantir les critères de qualités spécifiés par l’auteur. Nous proposons une implémentation de notre approche sous la forme d’un framework, comprenant notamment des outils auteurs d’édition des modèles que nous définissons, mais également les algorithmes de supervision nécessaires à l’asservissement de l’univers virtuel du jeu vidéo. / This PhD thesis has for objective to propose solutions to interactive storytelling problems. We aim to propose a design method for the authors, as well as a logic of execution using this model to control the narrative unfolding. We apply our works in the video games context, but wish to address interactive storytelling in a wider dimension. We so approach the interactive story as a breakdown of the classic storytelling. Indeed, interactive storytelling creation process is not any more only under the author responsability, but also involves spectators. Through a review of the classic storytelling, we thus wish, at first, to formalize storytelling and its stakes. We use then the concept of ”œuvre en mouvement” to identify processes and actors involved in this creation process of a work, and thus to define the stakes in our research works. We propose an interactive storytelling mode base on automata. This one allows a controland a check on possible narratives, during design as well as dynamically while producing the story. However this formalism is complex to handle by authors. So, we formulate a top-level model, based on storytelling concepts, allowing authors to create an interactive story model using concepts they know. This model is then converted into our automaton based model. The latter serves then as referent for the dynamic control of the interactive storytelling, done by a supervisor multi-agents. This one, by observing produced events in the video game, is then able of controlling and guarantee the quality criteria specified by authors. We propose an implementation of our approach in a framework, including authoring tools to edite our models. We also implements automata check and supervision algorithms necessary to control video game virtual universe.

Nous montrons qu’un modèle pour une théorie des champs à base d’automate cellulaire quantique est compatible avec une relativité restreinte déformée. En asso- ciant les lois de la physique à la règle d’évolution de l’automate, nous obtenons une version du principe de relativité où les états évoluant sur la grille de l’automate sont sujets à des transformations de Lorentz modifiées. Nous montrons ensuite que les déformations non-linéaires à l’espace des impulsions et des énergies mèneraient à une relativité de la localité et, dans des condition appropriées, produiraient un renversement de l’effet relativiste de contraction des longueurs. Nous considérons également les simulations de la physique sur calcul quantique d’un point de vue philosophique, demandant si notre monde pourrait faire partie d’une telle simulation et voyant comment des observations provenant de l’extérieur pourraient agir sur la simulation. / We show that a quantum field model based on a quantum cellular automaton requires a deformed special relativity. By associating the laws of physics with the automaton evolution rule, we obtain a version of the relativity principle where states evolving on the automaton must transform according to modified Lorentz transforma- tions. We then show that a non-linear momentum and energy space gives rise to the phenomenon of relative locality and that, under appropriate conditions, the relativistic length contraction effect must be reversed. We also consider simulations of physics on a philosphical level, asking if we might live inside such a simulation and seeing how observers from outside might interact if they attempt to observe us in such a context.

In this work, we propose a specialization of the inductive incremental coverability algorithm that solves alternating finite automata emptiness problem. We experiment with various design decisions, analyze them and prove their correctness. Even though the problem itself is PSpace-complete, we are focusing on making the decision of emptiness computationally feasible for some practical classes of applications. We have obtained interesting comparative results against state-of-the-art algorithms, especially in comparison with antichain-based algorithms.

This thesis deals with formal and syntax directed translation. This thesis contains theoretical part, which defines regular, context free, context sensitive and recursively enumerable languages a grammar. There are given examples of grammars which are able to generate languages that are not context free. Covered by this thesis are matrix grammars, random context grammars and programed grammars. Researched are also finite, pushdown, deep and regular automata, transducers and their part within format syntax directed translation. This project also defines regular transducers based as regulated automata. Thesis defines regulated methods of syntax analysis based on predictive parsers. These methods cover analysis of studied regulated grammars. The final part of this thesis describes new language capable of effective description of these grammars and compiler producing parser code for these grammars written in this new language and their graphical analyzer.