Nondeterministic finite automaton is an important tool, which is used to process strings in many different areas of programming. It is important to try to reduce its size for increasing programs' effectiveness. However, this problem is computationally hard, so we need to search for new techniques. Basics of finite automata are described in this work. Some methods for their reduction are then introduced. Usable reduction algorithms are described in greater detail. Then they are implemented and tested. The test results are finally evaluated.

In this Doktorarbeit the Lattice Boltzmann scheme, a heuristic method for the simulation of flows in complicated boundaries, is investigated. Its theory is renewed by emphasizing the entropy maximization principle, and new means for the modelling of geometries (including moving boundaries) and the visual representation of evoluting flows are presented. An object oriented implemen- tation is given with communication between objects realized by an interpreter object and communication from outside realized via interprocess communica- tion. Within the new theoretical apprach the applicability of existing Lattice Boltzmann schemes to model thermal flows for arbitrary temperatures is reex- amined. / In dieser Doktorarbeit wird das Gitter-Boltzmann-Schema, eine heuristische Methode fuer die Simulation von Stroemungen innerhalb komplexer Raender, untersucht. Die zugrundeliegende Theorie wird unter neuen Gesichtspunkten, insbesondere dem Prinzip der Entropiemaximierung, betrachtet. Des weiteren werden neuartige Methoden fuer die Modellierung der Geometrie (einschl. beweglicher Raender) und der visuellen Darstellung aufgezeigt. Eine objektorientierte Implementierung wird vorgestellt, wobei die Kommunikation zwischen den Objekten über Interpreter-Objekte und die Kommunikation mit der Aussenwelt ueber Interprozess-Kommunikation gehandhabt wird. Mit dem neuen theoretischen Ansatz wird die Gueltigkeit bestehender Gitter-Boltzmann-Schemata fuer die Anwendung auf Stroemungen mit nicht konstanter Temperatur untersucht.

In this thesis we focus on new methods for probabilistic model checking (PMC) with linear temporal logic (LTL). The standard approach translates an LTL formula into a deterministic ω-automaton with a double-exponential blow up. There are approaches for Markov chain analysis against LTL with exponential runtime, which motivates the search for non-deterministic automata with restricted forms of non-determinism that make them suitable for PMC. For MDPs, the approach via deterministic automata matches the double-exponential lower bound, but a practical application might benefit from approaches via non-deterministic automata. We first investigate good-for-games (GFG) automata. In GFG automata one can resolve the non-determinism for a finite prefix without knowing the infinite suffix and still obtain an accepting run for an accepted word. We explain that GFG automata are well-suited for MDP analysis on a theoretic level, but our experiments show that GFG automata cannot compete with deterministic automata. We have also researched another form of pseudo-determinism, namely unambiguity, where for every accepted word there is exactly one accepting run. We present a polynomial-time approach for PMC of Markov chains against specifications given by an unambiguous Büchi automaton (UBA). Its two key elements are the identification whether the induced probability is positive, and if so, the identification of a state set inducing probability 1. Additionally, we examine the new symbolic Muller acceptance described in the Hanoi Omega Automata Format, which we call Emerson-Lei acceptance. It is a positive Boolean formula over unconditional fairness constraints. We present a construction of small deterministic automata using Emerson-Lei acceptance. Deciding, whether an MDP has a positive maximal probability to satisfy an Emerson-Lei acceptance, is NP-complete. This fact has triggered a DPLL-based algorithm for deciding positiveness.

Here, we investigate different cell density-dependent migration strategies. In particular, we consider strategies which differ in the precise regulation of transitions between resting and motile phenotypes. We develop a lattice-gas cellular automaton (LGCA) model for each migration strategy. Using a mean-field approximation we quantify the corresponding spreading dynamics at the cell population level. Our results allow for the prediction of cell population spreading based on experimentally accessible single cell migration parameters.

Cellular automata (CA) are fully discrete dynamical systems. Space is represented by a regular lattice while time proceeds in finite steps. Each cell of the lattice is assigned a state, chosen from a finite set of "values". The states of the cells are updated synchronously according to a local interaction rule, whereby each cell obeys the same rule. Formal definitions of deterministic, probabilistic and lattice-gas CA are presented. With the so-called mean-field approximation any CA model can be transformed into a deterministic model with continuous state space. CA rules, which characterise movement, single-component growth and many-component interactions are designed and explored. It is demonstrated that lattice-gas CA offer a suitable tool for modelling such processes and for analysing them by means of the corresponding mean-field approximation. In particular two types of many-component interactions in lattice-gas CA models are introduced and studied. The first CA captures in abstract form the essential ideas of activator-inhibitor interactions of biological systems. Despite of the automaton´s simplicity, self-organised formation of stationary spatial patterns emerging from a randomly perturbed uniform state is observed (Turing pattern). In the second CA, rules are designed to mimick the dynamics of excitable systems. Spatial patterns produced by this automaton are the self-organised formation of spiral waves and target patterns. Properties of both pattern formation processes can be well captured by a linear stability analysis of the corresponding nonlinear mean-field (Boltzmann) equations.

This work deals with syntax analysis problems based on multi-generation. The basic idea is to create computer program, which transforms one input string to n -1 output strings. An Input of this program is some plain text file created by user, which contains n grammar rules. Just one grammar from the input file is marked as an input grammar and others n -1 grammars are output grammars. This program creates list of used input grammar rules for an input string and uses corresponding output grammar rules for the creation of n -1 output strings. The program is written in C++ and Bison

This work deals with Systems that combine automata and grammars. We investigate their properties compared with grammar systems and automaton systems. Work is focused on systems, which components are finite state automata, right linear grammars, pushdown automata or context free grammars. We also investigate usage of these systems in compilers.

This work suggests and solves the implementation of the transformation of context-free grammars and the conversions between context-free grammars and pushdown automata. It makes acquainted with the models used in modern theory of formal languages. In the work are indicated all algorithms necessary for transformations and mutual conversions between context-free grammars and pushdown automata. Proposed is an object representing the grammar and the automaton in the programme. Described is the assigning of definitions of grammar and of the automaton, the solution of drawing the automaton on the screen and the creation of graphical user interface of the application. The resulting programme is developed as Jawa applet which is available on public internet pages www.convertcfg.php5.cz.

<div>Topology Optimization is an optimization technique used to synthesize models without any preconceived shape. These structures are synthesized keeping in mind the minimum compliance problems. With the rapid improvement in advanced manufacturing technology and increased need for lightweight high strength designs topology optimization is being used more than ever.</div><div>There exist a number of commercially available software's that can be used for optimizing a product. These software have a robust Finite Element Solver and can produce good results. However, these software offers little to no choice to the user when it comes to selecting the type of optimization method used.</div><div>It is possible to use a programming language like MATLAB to develop algorithms that use a specific type of optimization method but the user himself will be responsible for writing the FEA algorithms too. This leads to a situation where the flexibility over the optimization method is achieved but the robust FEA of the commercial FEA tool is lost.</div><div>There have been works done in the past that links ABAQUS with MATLAB but they are primarily used as a tool for finite element post-processing. Through this thesis, the aim is to develop an interface that can be used for solving optimization problems using different methods like hard-kill as well as the material penalization (SIMP) method. By doing so it's possible to harness the potential of a commercial FEA software and gives the user the requires flexibility to write or modify the codes to have an optimization method of his or her choice. Also, by implementing this interface, it can also be potentially used to unlock the capabilities of other Dassault Systèmes software's as the firm is implementing a tighter integration between all its products using the 3DExperience platform.</div><div>This thesis as described uses this interface to implement BESO and HCA based topology optimization. Since hybrid cellular atomata is the only other method other than equivalent static load method that can be used for crashworthiness optimization this work suits well for the role when extended into a non-linear region.</div>

Transit system have a large importance in modern urban cities, with urban rail often acting as the central system with it efficient travel time and great capacity. As cities grow in population, so to does the usage of urban rail resulting in increased crowding on the platform and in the trains. Since crowding level is directly correlated to the experience of travel as well as a safety issue, much research has been done to improve it. Currently its common to utilise transit assignment models (TAM) to evaluate and research transit system but for them to work optimally requires weight parameters connected to perceived time spent on the journey. To get the weight parameters for a system requires surveys to be preformed which is costly and not always possible. Therefor its attractive to find these weights through optimisation using available data. Most transit system uses automated fare collection (AFC), which can be used to create origin-destination (OD) data, and automated vehicle location (AVL) together with link-load data. This project aims to develop a simulation-based optimisation (SBO) that automatically finds the weights for a frequency-based assignment model using OD and link-load as input arguments. The SBO will evaluate five different algorithm, genetic algorithm (GA), simulated annealing (SA), Nelder-Mead method (NM), simultaneous perturbation stochastic approximation (SPSA), and Bayesian optimisation (BO), using a fitness model based on KolmogorovSmirnov test. Synthetic data was implemented to evaluate the algorithms where result needed to be within a margin of error of the set weight. No algorithm was however able to converge during the simulation, therefor not optimising the weights to within the margin of error. A longer simulation was evaluated to see if the length needed to reach convergence was to short but achieved the same results. While the cause was not found, the standard deviation of the TAM could be the problem since the deviation was larger than the change of weight parameters achieved. Even if this project could not achieve its objective of developing a SBO method, it can be used for future research and work as a guide on further development on TAM research. / Transportsystem har en stor påverkan i moderna städer, specifikt tunnelbanan som ofta agerar som det centrala systemet med dess snabba transport samt stora kapacitet. Alltmedan städer växer i befolkning så ökar användandet av tunnelbanan vilket resulterar till trängsel både på plattformen och på tåget. Trängsel är väl studerat inom forskningen då den direkt påverkar den upplevda trivseln samt säkerheten på plattformen. Nuförtiden är det vanligt att använda sig av transport modeller för att undersöka och forska om transportsystemet men modellerna kräver viktparametrar kopplade till den uppfattade tiden man har för att fungera. Vanligtvis behöver man utföra undersökningar för att ta reda på vad viktparametrarna är men det är både dyrt och komplicerat. Därför vill man kunna få fram dessa vikter genom att optimera kända data. De flesta transportsystem använder sig av automatiska biljettsystem (AFC), vilket kan användas för att skapa start-stop (OD) data, och automatisk fordonslokalisering (AVL) tillsammans med länk-belastningsdata. Detta projekts syfte är att utveckla en simuleringsbaserad optimering (SBO) som automatiskt hittar vikterna för en frekvensbaserad transportmodell genom att använda OD- och länk-belastningsdata som argument. SBO kommer att undersöka fem olika algoritmer, genetic algorithm (GA), simulated annealing (SA), Nelder-Mead method (NM), simultaneous perturbation stochastic approximation (SPSA), and Bayesian optimisation (BO), tillsammans med en objektfunktion baserad på Kolmogorov-Smirnov testet. Syntetiskt data användes för att utvärdera algoritmerna, där resultatet behövde vara inom en viss marginal av de satta vikterna. Inga algoritmer konvergerade vilket resulterade att deras resultat inte var inom marginalen. Ett längre test var utfört då konvergensen kunde ha skett senare men det blev samma resultat som tidigare. Anledningen kunde inte finnas men sannolikt var det TAM standardavvikelse som var del av felet då den var större än en förändring av viktparametrarna skapade. Även om detta projekt inte kunde uppnå sitt mål kan den användas för fortsatt arbete inom området och vara som guide för framtida utvecklingar.