This master's thesis deals with cellular automata and further deals possibility of their global control. It describes the implementation of simulator of globally controlled cellular automata. The goal is, design and test the classification of globally controlled cellular automata. Classification is based on evaluation of influence of each parameter of automata on their dynamics.

In the first part of this thesis, a Chomsky-Schützenberger characterisation and an automaton characterisation of multiple context-free grammars are proved. Furthermore, a framework for approximation of automata with storage is described. The second part develops each of the three theoretical results into a parsing algorithm.

No description available.

No description available.

Technological advancements have transformed the way people interact with the world. The Internet now forms a critical infrastructure that links different aspects of our life like personal communication, business transactions, social networking, and advertising. In order to cater to this ever increasing communication overhead there has been a fundamental shift in the network infrastructure. Modern network routers often employ software programmable network processors instead of ASIC-based technology for higher throughput performance and adaptability to changing resource requirements. This programmability makes networking infrastructure vulnerable to new class of network attacks by compromising the software on network processors. This issue has resulted in the need for security systems which can monitor the behavior of network processors at run time. This thesis describes an FPGA-based security monitoring system for multi-core network processors. The implemented security monitor improves upon previous hardware monitoring schemes. We demonstrate a state machine based hardware programmable monitor which can track program execution flow at run time. Applications are analyzed offline and a hash of the instructions is generated to form a state machine sequence. If the state machine deviates from expected behavior, an error flag is raised, forcing a network processor reset. For testing purposes, the monitoring logic along with the multi-core network processor system is implemented in FPGA logic. In this research, we modify the network processor memory architecture to improve security monitor functionality. The efficiency of this approach is validated using a diverse set of network benchmarks. Experiments are performed on the prototype system using known network attacks to test the performance of the monitoring subsystem. Experimental results demonstrate that out security monitor approach provides an efficient monitoring system in detecting and recovering from network attacks with minimum overhead while maintaining line rate packet forwarding. Additionally, our monitor is capable of defending against attacks on processor with a Harvard architecture, the dominant contemporary network processor organization. We demonstrate that our monitor architecture provides no network slowdown in the absence of an attack and provides the capability to drop packets without otherwise affecting regular network traffic when an attack occurs.

In the United States, intersections are among the most frequent locations for crashes. One of the major problems at signalized intersection is the dilemma zone, which is caused by false driver behavior during the yellow interval. This research evaluated driver behavior during the yellow interval at signalized intersections and compared different dilemma zone countermeasures. The study was conducted through four stages. First, the driver behavior during the yellow interval were collected and analyzed. Eight variables, which are related to risky situations, are considered. The impact factors of drivers' stop/go decisions and the presence of the red-light running (RLR) violations were also analyzed. Second, based on the field data, a logistic model, which is a function of speed, distance to the stop line and the lead/follow position of the vehicle, was developed to predict drivers' stop/go decisions. Meanwhile, Cellular Automata (CA) models for the movement at the signalized intersection were developed. In this study, four different simulation scenarios were established, including the typical intersection signal, signal with flashing green phases, the intersection with pavement marking upstream of the approach, and the intersection with a new countermeasure: adding an auxiliary flashing indication next to the pavement marking. When vehicles are approaching the intersection with a speed lower than the speed limit of the intersection approach, the auxiliary flashing yellow indication will begin flashing before the yellow phase. If the vehicle that has not passed the pavement marking before the onset of the auxiliary flashing yellow indication and can see the flashing indication, the driver should choose to stop during the yellow interval. Otherwise, the driver should choose to go at the yellow duration. The CA model was employed to simulate the traffic flow, and the logistic model was applied as the stop/go decision rule. Dilemma situations that lead to rear-end crash risks and potential RLR risks were used to evaluate the different scenarios. According to the simulation results, the mean and standard deviation of the speed of the traffic flow play a significant role in rear-end crash risk situations, where a lower speed and standard deviation could lead to less rear-end risk situations at the same intersection. High difference in speed are more prone to cause rear-end crashes. With Respect to the RLR violations, the RLR risk analysis showed that the mean speed of the leading vehicle has important influence on the RLR risk in the typical intersection simulation scenarios as well as intersections with the flashing green phases' simulation scenario. Moreover, the findings indicated that the flashing green could not effectively reduce the risk probabilities. The pavement marking countermeasure had positive effects on reducing the risk probabilities if a platoon's mean speed was not under the speed used for designing the pavement marking. Otherwise, the risk probabilities for the intersection would not be reduced because of the increase in the RLR rate. The simulation results showed that the scenario with the pavement marking and an auxiliary indication countermeasure, which adds a flashing indication next to the pavement marking, had less risky situations than the other scenarios with the same speed distribution. These findings suggested the effectiveness of the pavement marking and an auxiliary indication countermeasure to reduce both rear-end collisions and RLR violations than other countermeasures.

No description available.

No description available.

Weighted automata can be seen as a natural generalization of finite state automata to more complex algebraic structures. The standard reasoning tasks for unweighted automata can also be generalized to the weighted setting. In this report we study the problems of intersection, complementation and inclusion for weighted automata on infinite trees and show that they are not harder than reasoning with unweighted automata. We also present explicit methods for solving these problems optimally.

La recherche de solutions analytiques pour l’évaluation de la fiabilité en contexte dynamique n’est pas résolue dans le cas général. Un état de l’art présenté dans le chapitre 1 montre que des approches partielles relatives à des hypothèses particulières existent. La simulation de Monte Carlo serait le seul recours, mais il n’existait pas d’outils performants permettant la simulation simultanée de l’évolution discrète du système et de son évolution continue prenant en compte les aspects probabilistes. Dans ce contexte, dans le chapitre 2, nous introduisons le concept d’automate stochastique hybride capable de prendre en compte tous les problèmes posés par la fiabilité dynamique et d’accéder à l’évaluation des grandeurs de la sûreté de fonctionnement par une simulation de Monte Carlo implémentée dans l’environnement Scilab-Scicos. Dans le chapitre 3, nous montrons l’efficacité de notre approche de simulation pour l’évaluation de la sûreté de fonctionnement en contexte dynamique sur deux cas test dont un est un benchmark de la communauté de la Sûreté de Fonctionnement. Notre approche permet de répondre aux problèmes posés, notamment celui de la prise en compte de l’influence de l’état discret, de l’état continu et de leur interaction dans l’évaluation probabiliste des performances d’un système dans lequel en outre, les caractéristiques fiabilistes des composants dépendent eux-mêmes des états continu et discret. Dans le chapitre 4, nous donnons une idée de l’intérêt du contrôle par supervision comme moyen de la sûreté de fonctionnement. Les concepts d’automate observateur et de contrôleur ont été introduits et illustrés sur notre cas test afin de montrer leur potentialité / The research of analytical solutions for reliability assessment in dynamic context is not solved in the general case. A state of the art presented in chapter 1 shows that partial approaches exist in the case of particular hypothesis. The Monte Carlo simulation would be the only recourse, but there were no tools allowing the simultaneous simulation of the discrete evolution of the system and its continuous evolution taking into account the probabilistic aspects. In this context, in chapter 2, we introduce the concept of hybrid stochastic automaton capable of taking into account all the problems posed by dynamic reliability and to accede to the assessment of dependability parameters by a Monte Carlo simulation implemented in Scicos-Scilab environment. In chapter 3, we show the effectiveness of our approach of simulation for dependability assessment in dynamic context through two test cases of which case one is a benchmark of dependability community. Our approach responds to the posed problems, notably the consideration of the influence of the discrete state, of the continuous state and their interaction, in the probabilistic assessment of the performances of a system in which besides, the reliability characteristics of components depend themselves of the continuous and discrete states. In chapter 4, we give an idea of the interest of control by supervision as a means of dependability. The concepts of observer automaton and of controller have been introduced and illustrated on our test case in order to show their potential