No description available.

This thesis deals with the mathematical idealization denoted cellular automata (CA) and the applicability of this method to structural mechanics. When using CA, all aspects such as space and time are discrete. This discrete nature of CA allows for ease of interaction with digital computers, while physical phenomena which are essentially discrete in nature can be simulated in a realistic way. The application of such a novel numerical method opens up new possibilities in structural analysis. In this study, the fundamentals of CA are studied to determine how the parameters of the method are to be evaluated and applied to the established field of structural analysis. Attention is given to the underlying mathematics of structural mechanics, as well as approximate methods currently used in structural analysis, e.g. the finite element method (FEM) and the boundary element method (BEM). For structural simulations performed with the CA implemented in this study, machine learning based on a genetic algorithm (GA) is used to determine optimum rules for the CA, using finite element, boundary element and analytical approximations as the basis for machine learning. Rather unconventionally, symmetric problems in structural analysis are analyzed using asymmetric rules in the machine learning process, where the symmetry of the solution found is used as a quantitative indication of the quality of the solution. It is demonstrated that the quality of the asymmetric rules is superior to the quality of symmetric rules, even for those problems that are symmetric in nature. Finally, exploiting the inherent parallelism of CA, it is shown that distributed computing can greatly improve the efficiency of the CA simulation, even though the speed-up factor is not necessarily proportional to the number of sub lattices used. The distributed computing device itself is constructed by combining 18 obsolete Pentium computers in a single cluster. In terms of CPU performance the constructed distributed computer is not state-of-art, but it is constructed with no hardware costs whatsoever. In addition, the software used in assembling the cluster is in the public domain, and is also available free of charge. Such a parallel configuration is also known as the poor man’s computer. However, faster and more modern machines can simply be added to the existing cluster as and when they become available. While CA are recent additions to the “tools” used in structural analysis, increased use of CA as distributed computing becomes more widely available is envisaged, even though the CA rules are at this stage not transferable between different problems or even between meshes of varying refinement for a given problem. / Dissertation (MEng (Mechanical Engineering))--University of Pretoria, 2006. / Mechanical and Aeronautical Engineering / unrestricted

Since the 1950s, the theory of deterministic and nondeterministic finite automata (DFAs and NFAs, respectively) has been a cornerstone of theoretical computer science. In this dissertation, our main object of study is minimal NFAs. In contrast with minimal DFAs, minimal NFAs are computationally challenging: first, there can be more than one minimal NFA recognizing a given language; second, the problem of converting an NFA to a minimal equivalent NFA is NP-hard, even for NFAs over a unary alphabet. Our study is based on the development of two main theories, inductive bases and partials, which in combination form the foundation for an incremental algorithm, ibas, to find minimal NFAs. An inductive basis is a collection of languages with the property that it can generate (through union) each of the left quotients of its elements. We prove a fundamental characterization theorem which says that a language can be recognized by an n-state NFA if and only if it can be generated by an n-element inductive basis. A partial is an incompletely-specified language. We say that an NFA recognizes a partial if its language extends the partial, meaning that the NFA's behavior is unconstrained on unspecified strings; it follows that a minimal NFA for a partial is also minimal for its language. We therefore direct our attention to minimal NFAs recognizing a given partial. Combining inductive bases and partials, we generalize our characterization theorem, showing that a partial can be recognized by an n-state NFA if and only if it can be generated by an n-element partial inductive basis. We apply our theory to develop and implement ibas, an incremental algorithm that finds minimal partial inductive bases generating a given partial. In the case of unary languages, ibas can often find minimal NFAs of up to 10 states in about an hour of computing time; with brute-force search this would require many trillions of years.

We consider a natural extension to the definition of M-automata which allows the automaton to make use of more of the structure of the monoid M, and by removing the reliance on an identity element, allows the definition of S-automata for S an arbitrary semigroup. In the case of monoids, the resulting automata are equivalent to valence automata with rational target sets which arise in the theory of regulated rewriting. We focus on the polycyclic monoids, and show that for polycyclic monoids of rank 2 or more they accept precisely the context-free languages. The case of the bicyclic monoid is also considered. In the process we prove a number of interesting results about rational subsets in polycyclic monoids; as a consequence we prove the decidability of the rational subset membership problem, and the closure of the class of rational subsets under intersection and complement. In the case of semigroups, we consider the important class of completely simple and completely 0-simple semigroups, obtaining a complete characterisation of the classes of languages corresponding to such semigroups, in terms of their maximal subgroups. In the process, we obtain a number of interesting results about rational subsets of Rees matrix semigroups.

No description available.

Multigrid acceleration is typically used for the iterative solution of partial differential equations in physics and engineering. A typical multigrid implementation uses a base discretization method, such as finite elements or finite differences, and a set of successively coarser grids that is used for accelerating the convergence of the iterative solution on the base grid. The presented thesis extends the use of multigrid acceleration to the design optimization of a sample structural system and demonstrates it within the context of the recently introduced Cellular Automata paradigm for design optimization. Within the design context, the multigrid scheme is not only used for accelerating the analysis iterations, but is also used to help refine the design across multiple grid levels to accelerate the design convergence. A comparison of computational efficiencies achieved by different multigrid implementations, including the multigrid accelerated nested design iteration scheme, is presented. The method is described in its generic form which can be applicable not only to the Cellular Automata paradigm but also to more general finite element analysis based design schemes as well. / Master of Science

The purpose of this study was to estimate the drivers' travel time with the occurrence of an incident on freeway. Three approaches, which were shock wave analysis, queuing theory and cellular automata models, were initially considered, however, the first two macroscopic models were indicated to underestimate travel time by previous literature. A microscopic simulation model based on cellular automata was developed to attain the goal. The model incorporated driving behaviors on the freeway with the presence of on-ramps, off-ramps, shoulder lanes, bottlenecks and incidents. The study area was a 16 mile eastbound section of I-66 between US-29 and I-495 in northern Virginia. The data for this study included loop detector data and incident data for the road segment for the year 2007. Flow and speed data from the detectors were used for calibration using quantitative and qualitative techniques. The cellular automata model properly reproduced the traffic flow under normal conditions and incidents. The travel time information was easily obtained from the model. The system is promising for travel time estimation in near real time. / Master of Science

No description available.

This dissertation is an attempt of expanding the domain of game theory into the sphere of evolving, potentially non-equilibrium systems. We especially focus our attention on studying the effects of local interactions, using automata networks as a modelling tool. The Chapters 2 and 3 of this dissertation concentrate on applications of the local nature of interactions and rely on automata networks as an investigating and modelling tool for game theory. Chapter 2 is devoted to cooperation and to a smaller extent to the endogenous formation of links between the agents. Chapter 3 is investigating the deterministic and stochastic best response play when interactions are local. / Ph. D.

Büchi, Elgot and Trakhtenbrot provided a seminal connection between monadic second-order logic and finite automata for both finite and infinite words. This BET- Theorem has been extended by Lautemann, Schwentick and Thérien to context-free languages by introducing a monadic second-order logic with an additional existentially quantified second-order variable. This new variable models the stack of pushdown au- tomata. A fundamental study by Cohen and Gold extended the context-free languages to infinite words. Our first main result is a second-order logic in the sense of Lautemann, Schwentick and Thérien with the same expressive power as ω-context-free languages. For our argument, we investigate Greibach normal forms of ω-context-free grammars as well as a new type of Büchi pushdown automata, the simple pushdown automata. Simple pushdown automata do not use e-transitions and can change the stack only by at most one symbol. We show that simple pushdown automata of infinite words suffice to accept all ω-context-free languages. This enables us to use Büchi-type results recently developed for infinite nested words. In weighted automata theory, many classical results on formal languages have been extended into a quantitative setting. Weighted context-free languages of finite words trace back already to Chomsky and Schützenberger. Their work has been extended to infinite words by Ésik and Kuich. As in the theory of formal grammars, these weighted ω-context-free languages, or ω-algebraic series, can be represented as solutions of mixed ω-algebraic systems of equations and by weighted ω-pushdown automata. In our second main result, we show that (mixed) ω-algebraic systems can be trans- formed into Greibach normal form. We then investigate simple pushdown automata in the weighted setting. Here, we give our third main result. We prove that weighted simple pushdown automata of finite words recognize all weighted context-free languages, i.e., generate all algebraic series. Then, we show that weighted simple ω-pushdown automata generate all ω-algebraic series. This latter result uses the former result together with the Greibach normal form that we developed for ω-algebraic systems. As a fourth main result, we prove that for weighted simple ω-pushdown automata, Büchi-acceptance and Muller-acceptance are expressively equivalent. In our fifth main result, we derive a Nivat-like theorem for weighted simple ω- pushdown automata. This theorem states that the behaviors of our automata are precisely the projections of very simple ω-series restricted to ω-context-free languages. The last result, our sixth main result, is a weighted logic with the same expressive power as weighted simple ω-pushdown automata. To prove the equivalence, we use a similar result for weighted nested ω-word automata and apply our present result of expressive equivalence of Muller and Büchi acceptance.