Made available in DSpace on 2016-03-15T19:37:45Z (GMT). No. of bitstreams: 1 Wander Lairson Costa.pdf: 1957133 bytes, checksum: 6819580d97bb5eaca5ea04352fcda0b8 (MD5) Previous issue date: 2013-03-15 / Universidade Presbiteriana Mackenzie / Cellular automata are totally discrete systems that act locally in a simple and deterministic way, but whose resulting global behavior can be extremely complex. The set of possible global configurations in one finite time step for a CA can be described by a regular language, which in turn can be represented by a finite automaton, more precisely the so-called process graph, in which all states are initial and final. Here, we study the temporal evolution complexity of the elementary cellular automata (i.e., one-dimensional, binary, with radius 1), and related previous works are revisited and discussed, indicating problems and their consequences. We also start up a novel approach for the problem, substituting the process graph based representation that describes the configuration at each time step by adjacency matrices derived from them. In fact, we extend the classical adjacency matrix notation, as they cannot fully represent process graphs. With this new notation, we show that it is possible to obtain the algorithm to generate a process graph for an arbitrary finite time step for each of the rules at study. In conclusion, although advancing the limit graph problem, it still remains open, and we provide suggestions for further research. / Autômatos celulares são sistemas totalmente discretos que agem localmente de forma simples e determinística, mas cujo comportamento global resultante pode ser extremamente complexo. O conjunto de possíveis configurações globais em um passo de tempo t finito para um autômato celular pode ser descrito por uma linguagem regular, a qual por sua vez pode ser representada por meio de um autômato finito, mais precisamente, pelo chamado grafo de processo, em que todos os estados são iniciais e finais. Estuda-se aqui a complexidade da evolução temporal dos autômatos celulares elementares (i.e., unidimensionais, binários, de raio 1), e trabalhos anteriores são revisitados e discutidos, no quais apontam-se problemas e suas consequências. Também inicia-se uma nova abordagem para o problema, substituindo a representação dos grafos de processo que descrevem a configuração a cada passo de tempo por matrizes de adjacência deles derivadas. De fato, estende-se a notação clássica de matriz de adjacência, já que ela se mostra insuficiente para descrever completamente os grafos de processo em questão. Com essa nova notação, mostra-se que é possível obter o algoritmo que gere o grafo de processo de tempo t para cada uma das regras estudadas. Conclui-se que, embora houve avanços para o problema do grafo limite, este ainda permanece aberto, e sugestões para continuação da pesquisa são dadas.

In order to minimize greenhouse gas emissions and operational cost related to the ICT-infrastructure the power management method of a Radio Base Station (RBS) or Base Transceiver Station (BTS) at Ericsson is studied and modelled. The major load demand at RBS’s are due to uplink and downlink data traffic. Ericssons RBS’s contains power resources and energy storage systems that are controlled by a power controller module in order to meet load demand. Such power resources may be AC-grid, generator and photovoltaic cells etc. Using a certain power resource entails a distinct cost and emission. This thesis investigates the influence that the power controller logic has on cost and emission using two frameworks. One framework models the power resource management in the form of a hybrid dynamical system. Using this framework a new management policy is investigated and compared with the current management policy. The second framework investigates the usage of MPC for controlling the power sources during operation. Using this framework a third management policy is introduced and compared with the current implementation. The performance of the three management policies are compared by simulating a standard RBS operation scenario. The results show that during a RBS scenario where the grid will never fail the third management method using MPC outperforms the other two management policies. In the RBS scenario that the grid may fail the second management method outperforms the current implementation. The implication of these results may be that during a scenario of no grid failure it is more advantageous to decrease emission and cost by using a supervisory control method. During a scenario where grid failure may occur using the second management method, where battery is used as more than just a back-up unit, is more advantageous for decreasing emission and cost. / För att minimera utsläpp av växthusgaser och driftskostnader inom ICT-infrastrukturen studeras och modelleras effekt-hanteringen för en radiobasstation (RBS) eller Base Transceiver Stations (BTS) på Ericsson. Det stora belastningsbehovet hos en RBS beror på upplänk och nedlänksdatatrafik. Ericssons RBS innehåller kraftresurser och energi lagringssystem som styrs av en effektkontrollmodul för att möta lastbehovet. Sådana kraftresurser kan vara AC-nät, generator eller solceller etc. Användandet av en viss kraftresurs medför en distinkt driftkostnad och utsläpp. Detta examensarbete undersöker effekten som kontrollmodulens logik har på kostnad och emission genom två tillvägagångssätt. Ett tillvägagångssätt modellerar effekt-hanteringen i form av ett hybrid dynamiskt system. Med detta tillvägagångssätt utreds en ny resurs förvaltningspolicy och jämförs med den nuvarande implementerade policyn. Det andra tillvägagångssättet undersöker användningen av MPC för att styra effekt-hanteringen under drift. Detta tillvägagångssätt leder till en tredje förvaltningspolicy som jämförs med den nuvarande implementerade policyn. Prestandan av de tre förvaltningspolicyerna jämförs genom att simulera olika scenarion av RBS-drift. Resultaten visar att under ett RBS-scenario där nätet aldrig kommer att förloras överträffar den tredje förvaltningspolicyn som använder MPC, de andra två förvaltningsmetoderna. I ett RBS scenario där nätet kan förloras överträffar den andra förvaltningsmetoden den nuvarande implementeringen. Resultaten tyder på att under ett scenario utan nätfel är det mer fördelaktigt för att minska utsläpp och kostnader genom att använda den tredje förvaltningsmetoden. Under ett scenario där nätfel kan inträffa är den andra förvaltningsmetoden, där batteriet används som mer än bara en reservenhet, mer fördelaktig för att minska utsläpp och kostnader.

The Software Reliability group at KTH-CSC has designed and built a novel test platform LBTest for black-box requirements testing of reactive and embedded software systems (e.g. web servers, automobile control units, etc). The main concept of LBTest is to create a large number of test cases by incorporation of an automata learning algorithm with a model checking algorithm (NuSMV). This platform aims to support different learned automata, learning algorithms and different model checking algorithms which can be combined to implement the paradigm of learning-based testing (LBT).This thesis project investigates an existing published algorithm for learning deterministic finite automata (DFA)known as Kearns algorithm. The aimof this thesis is to investigate how effective Kearns algorithm is from a software testing perspective.Angluin’s well-known L* DFA learning algorithm has a simple structure and implementation. On the other hand, Kearnsalgorithm has more complex, difficult structure and harder implementation than L* algorithm, however it is more efficient and faster. For this reason, the plan is to implement an advanced DFA learning algorithm, Kearns algorithm[4], from a description in the literature (using Java).We consider a methodology to compare Kearns algorithm with Angluin’s DFA learning algorithm based on the master thesis of Czerny[8].The comparisonsbetween the Kearns and the L* algorithmsare based on the number of membership and equivalence queriesto investigate the difficulty of learning

Writing declarative models of software designs and analyzing them to detect defects is an effective methodology for developing more dependable software systems. However, writing such models correctly can be challenging for practitioners who may not be proficient in declarative programming, and their models themselves may be buggy. We introduce the foundations of a novel test automation framework, AUnit, which we envision for testing declarative models written in Alloy -- a first-order, relational language that is supported by its SAT-based analyzer. We take inspiration from the success of the family of xUnit frameworks that are used widely in practice for test automation, albeit for imperative or object-oriented programs. The key novelty of our work is to define a basis for unit testing for Alloy, specifically, to define the concepts of test case and test coverage as well as coverage criteria for declarative models. We reduce the problems of declarative test execution and coverage computation to partial evaluation without requiring SAT solving. Our vision is to blend how developers write unit tests in commonly used programming languages with how Alloy users formulate their models in Alloy, thereby facilitating the development and testing of Alloy models for both new Alloy users as well as experts. We illustrate our ideas using a small but complex Alloy model. While we focus on Alloy, our ideas generalize to other declarative languages (such as Z, B, ASM). / text

Cette thèse apporte plusieurs contributions dans le domaine des langages formels. Notre premier travail a été de montrer la pertinence des grammaires de graphes comme outil de démonstration de résultats fondamentaux sur les langages algébriques. Nous avons ainsi reformulé avec un point de vue géométrique les démonstrations du lemme des paires itérantes et du lemme de Parikh. Nous avons ensuite étendu aux graphes réguliers des algorithmes de base sur les graphes finis, notamment pour calculer des problèmes de plus court chemin. Ces extensions ont été faites par calcul de plus petits points fixes sur les grammaires de graphes. Enfin, nous avons caractérisé des familles générales de systèmes de récriture de mots dont la dérivation préserve la régularité ou l’algébricité. Ces familles ont été obtenues par décomposition de la dérivation en une substitution régulière suivie de la dérivation du système de Dyck / Pas de résumé en anglais

Ce travail étudie les déviations de sommes ergodiques pour des systèmes dynamiques substitutifs avec une matrice qui admet des valeurs propres de module supérieur à 1. Précisément, nous nous concentrons sur les substitutions telle que ces valeurs propres ne sont pas conjuguées. Dans un premier temps, on défini les lettres a-minimales et dominantes d'un mot pour étudier sa ligne brisée associé. On défini la ligne brisée normalisée et sa fonction limite. Pour l'étude des sommes ergodiques, on défini le sous-automate des lettres minimales. On donne des conditions sur une substitution de sorte qu'il y ait un nombre infini des sommes ergodiques égales à zéro pour un point x 2 X. Enfin, en utilisant un boucle dans une classe de Rauzy, on prouve l'existence d'un nombre infini d'échanges d'intervalles auto-similaires, dont la matrice de Rauzy a deux valeurs propres non conjuguées de module supérieur à 1. Et tout échange d'intervalles affine semi-conjugué à cet échange d'intervalles est aussi conjugué. / This thesis focuses on the deviation of ergodic sums for a substitution dynamical systems with a matrix that admits eigenvalues of modulus larger than 1. Specifically, we concentrate on substitutions with non-conjugated eigenvalues. At first, we define the a-minimals letters and the dominant letters of a word to study its broken associated line. We define the normalize broken line and its limit function. For the study of ergodic sums, we define the sub-automaton of minimum letters. We give conditions on a substitution so that there is infinitely many zero sums ergodic for a point x 2 X. Finally, using a loop in a class of Rauzy, we prove the existence of infinitely many interval exchange transformation self-similar, whose Rauzy matrix has two non-conjugated eigenvalues larger than 1 and every affine interval exchange transformation that is semi-conjugated, is also conjugated.

Made available in DSpace on 2015-03-04T18:50:37Z (GMT). No. of bitstreams: 1 ThesisJaquelineSilva.pdf: 11035936 bytes, checksum: 593b1276f8343f4172ebbb8e0f37d955 (MD5) Previous issue date: 2011-12-16 / Coordenacao de Aperfeicoamento de Pessoal de Nivel Superior / Most processes that affect the distribution, structure and dynamics of tree populations occur early in the plant life cycle. Hence, it is very important to study seed germination and seedling establishment processes to understand the growth and the dispersion of plant populations. In this work, we present three vegetation models to represent the tree growth process in flooded areas of the Amazon Forest that use cellular automata. We consider seed dispersion, seedling establishment, in uence of light, recruitment of individuals, as well as the ood gradient in the models.The first model represents the influence of flooding in the vegetation dynamic only through data and adequate hypotheses about the ooded regions. The second model represents the influence of ooding in the vegetation dynamic taking into account its in uence on mortalities. The third model represents the ood varying along time and includes topographic information.We analyze the in uence of each parameter on the vegetation dynamic. Furthermore, we present a statistical analysis of the results, evaluating the model behavior and the consistency and stability of the results obtained by the computational models. / Muitos dos processos que afetam a distribuição, estrutura e dinâmica de uma população arbórea vegetal podem ocorrer muito cedo na vida de uma planta. Desta forma, o estudo dos processos de germinação e estabelecimento das plantas e fundamental para entender o crescimento populacional e a dispersão de suas sementes. Neste trabalho, apresentamos modelos de vegetação que usam autômatos celulares para representar o crescimento de espécies arbóreas nas áreas alagáveis da floresta amazônica considerando a dispersão de suas sementes, o recrutamento dos indivíduos e a influência da inundação. O primeiro dos modelos representa a dinâmica de vegetaão sem considerar diretamente a influência do pulso de inundação. O segundo modelo representa a influência da inundação via a mortalidade dos indivíduos da população. O terceiro modelo acrescenta a variação no tempo da altura da inundação,adicionando informações sobre o relevo da regi ão. É feita uma análise da influência de cada parâmetro principal na dinâmica da vegetação. Além disso apresentamos uma análise dos resultados que avaliam o comportamento do modelo, bem como a consistência e a estabilidade dos resultados obtidos pelos modelos computacionais.

La validation des systèmes critiques réalistes nécessite d'être capable de modéliser et de vérifier formellement des données complexes, du parallélisme asynchrone, et du temps-réel simultanément. Des langages de haut-niveau, comme ceux qui héritent des fondations théoriques des algèbres de processus, ont une syntaxe concise et une grande expressivité pour représenter ces aspects. Cependant, ils disposent de peu d'outils logiciels permettant d'appliquer des algorithmes efficaces du model-checking. Néanmoins, de tels outils existent pour des modèles graphiques, de niveau plus bas, tels que les automates temporisés (par exemple UPPAAL) et les réseaux de Petri temporisés (par exemple TINA). Les modèles intermédiaires sont un moyen pour combler le fossé qui sépare les langages des modèles graphiques. Par exemple, NTIF (New Technology Intermediate Format) a été proposé pour représenter des processus séquentiels non temporisés qui manipulent des données complexes. Dans cette thèse, nous proposons un nouveau modèle nommé ATLANTIF, qui enrichit NTIF de constructions temps-réel et de compositions parallèles de processus séquentiels. Leur synchronisation est exprimée d'une manière simple et intuitive par la nouvelle notion de synchroniseur. Nous montrons qu'ATLANTIF est capable d'exprimer les constructions principales des langages de haut niveau. Nous présentons aussi des traducteurs d'ATLANTIF vers des automates temporisés (pour la vérification avec UPPAAL) et vers des réseaux de Petri temporisés (pour la vérification avec TINA). Ainsi, ATLANTIF étend la classe des systèmes qui peuvent en pratique être vérifiés formellement, ce que nous illustrons par un exemple.

One of the basic problems which have to be solved by Unmanned Automated Vehicles (UAV) involves the computation of a motion plan that would enable the system to reach a target given a set of initial conditions in presence of uncertainties on the vehicle dynamics and in the environment. Recent research efforts in this area have relied on deterministic models. To address the problem of inevitable uncertainties, a low-level control layer is typically used to ensure proper robust trajectory tracking. Such decision-tracking algorithms correct model disturbances a posteriori, while the whole movement planning is done in a purely deterministic fashion. We argue that the decision making process that takes place during movement planning, as performed by experienced human pilots, is not a purely deterministic operation, but is heavily influenced by the presence of uncertainties and reflects a risk-management policy. This research aims at addressing these uncertainties and developing an optimal control strategy that would account for the presence of system uncertainties. The underlying description of UAV trajectories will be based on a modeling language, the Maneuver Automaton, that takes into full account the vehicle dynamics, and hence guarantees flyable and trackable paths and results in a discretized solution space. Two optimal control problems, a nominal problem omitting uncertainties and a robust problem addressing the presence of uncertainties, will be defined and compared throughout this work. The incorporation of uncertainties, will ensure that the generated motion planning policies will maximize the probability to meet mission goals, weighing risks against performance.

Modeling of flow in porous and fractured media is a very important problem in reservoir engineering. As for numerical simulations conventional Navier-Stokes codes are applied to flow in both porous and fractured media. But they have long computation times, poor convergence and problems of numerical instabilities. Therefore, it is desired to develop another computational method that is more efficient and use simple rules to represent the flow in fractured media rather than partial differential equations. In this thesis Lattice Boltzmann Automaton Model will be used to represent the single phase fluid flow in two dimensional synthetic fractures and the simulation results obtained from this model are used to train Artificial Neural Networks. It has been found that as the mean aperture-fractal dimension ratio increases permeability increases. Moreover as the anisotropy factor increases permeability decreases with a second order polynomial relationship.