Phase change devices in both optical and electrical formats have been subject of intense research since their discovery by Ovshinsky in the early 1960’s. They have revolutionized the technology of optical data storage and have very recently been adopted for non-volatile semiconductor memories. Their great success relies on their remarkable properties enabling high-speed, low power consumption and stable retention. Nevertheless, their full potential is still yet to be realized. Operations in electrical phase change devices rely on the large resistivity contrast between the crystalline (low resistance) and amorphous (high resistance) structures. The underlying mechanisms of phase transformations and the relation between structural and electrical properties in phase change materials are quite complex and need to be understood more deeply. For this purpose, we compare different approaches to mathematical modelling that have been suggested to realistically simulate the crystallization and amorphization of phase change materials. In this thesis the recently introduced Gillespie Cellular Automata (GCA) approach is used to obtain direct simulation of the structural phases and the electrical states of phase change materials and devices. The GCA approach is a powerful technique to understand the nanostructure evolution during the crystallization (SET) and amorphization (RESET) processes in phase change devices over very wide length scales. Using this approach, a detailed study of the electrical properties and nanostructure dynamics during SET and RESET processes in a PCRAM cell is presented. Besides the possibility of binary storage in phase change memory devices, there is a wider and far-reaching potential for using them as the basis for new forms of arithmetic and cognitive computing. The origin of such potential lies in a previously under-explored property, namely accumulation which has the potential to implement basic arithmetic computations. We exploit and explore this accumulative property in films and devices. Furthermore, we also show that the same accumulation property can be used to mimic a simple integrate and fire neuron. Thus by combining both a phase change cell operating in the accumulative regime for the neural body and a phase change cell in the multilevel regime for the synaptic weighting an artificial neuromorphic system can be obtained. This may open a new route for the realization of phase change based cognitive computers. This thesis also examines the relaxation oscillations observed under suitable bias conditions in phase change devices. The results presented are performed through a circuit analysis in addition with a generation and recombination mechanism driven by the electric field and carrier densities. To correctly model the oscillations we show that it is necessary to include a parasitic inductance. Related to the electrical states of phase change materials and devices is the threshold switching of the amorphous phase at high electric fields and recent work has suggested that such threshold switching is the result of field-induced nucleation. An electric field induced nucleation mechanism is incorporated into the GCA approach by adding electric field dependence to the free energy of the system. Using results for a continuous phase change thin films and PCRAM devices we show that a purely electronic explanation of threshold switching, rather than field-induced nucleation, provides threshold fields closer to experimentally measured values.

Pitting corrosion is a form of highly localized corrosion that can lead to crack and failure of a structure. Study on pitting corrosion is necessary in order to predict and prevent the risk of failure of structure susceptible to corrosion. In this thesis, a combination of Cellular Automata (CA) and Boundary Element Method (BEM) was developed to simulate pitting corrosion growth under certain environment. It is assumed that pitting corrosion can be simplified to electrochemical corrosion cell. The distribution of potential around this corrosion cell can then be simulated by BEM. This distribution potential represents cathodic and anodic reactions around the corrosion cell. A CA model was developed that uses transition rules reflecting mechanism of pitting corrosion. The CA model has two types of cell states, one reflecting BEM simulation results and the other reflecting the status of corrosion cell (anode, cathode, and passive metal’s surface). For every CA iteration, the CA decides the state of the corrosion cells (the location and size of anode, cathode) while BEM simulate the level of electrochemical activity at discrete location on the surface (represented by potential distribution). In order to demonstrate the methodology, a simple case of rectangular corrosion cell with varied dimensions and under different polarization functions is considered. Results show certain shapes tend to grow at certain type environment and these pits are comparable to commonly observed pit shapes. In addition, stress analysis was carried out to investigate the severity of corrosion pits of varying shapes and sizes. Results show that certain pits induced highly varying stress concentration as it grows over time, while others have more steady increase of stress concentration.

Biological systems exhibit complex behaviors through coordinated responses of individual biological components. With the advent of genome-scale techniques, one focus has been to develop methods to model interactions between components to accurately describe intact system function. Mathematical modeling techniques such as constraint-based modeling, agent-based modeling, cellular automata (CA) modeling and differential equation modeling are employed as computational tools to study biological phenomenon. We have shown that cellular automata simulations can be used as a computational tool for 12 predicting the dynamics of biological systems with stochastic behavior. The basic premise for the research was the observations made during a study of biologically important feed-forward motifs where CA simulations were compared with differential equation simulations. It was shown for classes of structural motifs with feed-forward architecture that network topology affects the overall rate of a process in a quantitatively predictable manner. The study which comprised of CA simulations compared with differential equation modeling show reasonable agreement in the predictability of system dynamics, which provided enough support to model biological systems at cellular level to observe dynamic system evolution. The great promise shown by CA simulations to model biochemical systems was then employed to elucidate evolutionary clues as to why biological networks show preference for certain types of motifs and preserve them with higher frequency during evolution. It was followed by modeling apoptotic networks to shed light on the efficacy of inhibitors and to model cellulose hydrolysis to evaluate efficiency of different enzyme systems used by cellulytic bacteria.

Many complex systems in nature are governed by simple local interactions, although a number are also described by global interactions. For example, within the field of hydraulics the Navier-Stokes equations describe free-surface water flow, through means of the global preservation of water volume, momentum and energy. However, solving such partial differential equations (PDEs) is computationally expensive when applied to large 2D flow problems. An alternative which reduces the computational complexity, is to use a local derivative to approximate the PDEs, such as finite difference methods, or Cellular Automata (CA). The high speed processing of such simulations is important to modern scientific investigation especially within urban flood modelling, as urban expansion continues to increase the number of impervious areas that need to be modelled. Large numbers of model runs or large spatial or temporal resolution simulations are required in order to investigate, for example, climate change, early warning systems, and sewer design optimisation. The recent introduction of the Graphics Processor Unit (GPU) as a general purpose computing device (General Purpose Graphical Processor Unit, GPGPU) allows this hardware to be used for the accelerated processing of such locally driven simulations. A novel CA transformation for use with GPUs is proposed here to make maximum use of the GPU hardware. CA models are defined by the local state transition rules, which are used in every cell in parallel, and provide an excellent platform for a comparative study of possible alternative state transition rules. Writing local state transition rules for CA systems is a difficult task for humans due to the number and complexity of possible interactions, and is known as the ‘inverse problem’ for CA. Therefore, the use of Genetic Programming (GP) algorithms for the automatic development of state transition rules from example data is also investigated in this thesis. GP is investigated as it is capable of searching the intractably large areas of possible state transition rules, and producing near optimal solutions. However, such population-based optimisation algorithms are limited by the cost of many repeated evaluations of the fitness function, which in this case requires the comparison of a CA simulation to given target data. Therefore, the use of GPGPU hardware for the accelerated learning of local rules is also developed. Speed-up factors of up to 50 times over serial Central Processing Unit (CPU) processing are achieved on simple CA, up to 5-10 times speedup over the fully parallel CPU for the learning of urban flood modelling rules. Furthermore, it is shown GP can generate rules which perform competitively when compared with human formulated rules. This is achieved with generalisation to unseen terrains using similar input conditions and different spatial/temporal resolutions in this important application domain.

Today, there is a substantial number of software and research groups that focus on the development of image processing software to extract useful information from medical images, in order to assist and improve patient diagnosis. The work presented in this thesis is centred on processing of images of blood and bone marrow smears of patients suffering from leukaemia, a common type of cancer. In general, cancer is due to aberrant gene expression, which is caused by either mutations or epigenetic changes in DNA. Poor diet and unhealthy lifestyle may trigger or contribute to these changes, although the underlying mechanism is often unknown. Importantly, many cancer types including leukaemia are curable and patient survival and treatment can be improved, subject to prompt diagnosis. In particular, this study focuses on Acute Myeloid Leukaemia (AML), which can be of eight distinct types (M0 to M7), with the main objective to develop a methodology to automatically detect and classify leukaemia cells into one of the above types. The data was collected from the Department of Haematology, Universiti Sains Malaysia, in Malaysia. Three main methods, namely Cellular Automata, Heuristic Search and classification using Neural Networks are facilitated. In the case of Cellular Automata, an improved method based on the 8-neighbourhood and rules were developed to remove noise from images and estimate the radius of the potential blast cells contained in them. The proposed methodology selects the starting points, corresponding to potential blast cells, for the subsequent seeded heuristic search. The Seeded Heuristic employs a new fitness function for blast cell detection. Furthermore, the WEKA software is utilised for classification of blast cells and hence images, into AML subtypes. As a result accuracy of 97.22% was achieved in the classification of blasts into M3 and other AML subtypes. Finally, these algorithms are integrated into an automated system for image processing. In brief, the research presented in this thesis involves the use of advanced computational techniques for processing and classification of medical images, that is, images of blood samples from patients suffering from leukaemia.

Les automates cellulaires sont un modèle de calcul massivement parallèle introduit dans les années 50. De nombreuses variantes peuvent être considérées par exemple en faisant varier la dimension de l’espace de calcul, ou les possibilités de communication entre les différentes cellules. En effet, chaque cellule ne peut communiquer qu’avec un nombre fini d’autres cellules que l’on appelle son voisinage. Mes travaux s’intéressent principalement à l’impact du choix du voisinage sur les capacités algorithmiques de ce modèle. Cet impact étant bien compris en une dimension, mes travaux portent majoritairement sur les automates cellulaires bidimensionnels. J’ai tout d’abord essayé de généraliser des propriétés classiques de certaines classes de complexité au plus de voisinages possibles. On arrive notamment à un théorème d’accélération linéaire valable pour tous les voisinages. J’ai ensuite étudié les différences entre les classes de faibles complexités en fonction du voisinage choisi. Ces travaux ont permis d’exhiber des voisinages définissant des classes incomparables, ainsi que des ensembles de voisinages définissant exactement les mêmes classes de complexité. Enfin, je présente aussi des travaux sur les différences de puissance de calcul entre les automates de dimensions différentes. / Cellular automata were introduced in the 50s by J. von Neumann and S. Ulamas an efficient way of modeling massively parallel computation. Many variations of the model can be considered such as varying the dimension of the computation space or the communication capabilities of the computing cells. In a cellular automaton each cell can communicate only with a finite number of other cells called its neighbors. My work focuses on the impact of the choice of the neighbors on the algorithmic properties of the model. My first goal was to generalize some classical properties of computation models to the widest possible class of neighborhoods, in particular I prove a linear speedup theorem for any two dimensional neighborhood. I then study the difference between the complexity classes defined by different neighborhoods, show the existence of neighborhoods defining incomparable classes, and some sets of neighborhoods defining identical classes. Finally, I also discuss the impact of the dimension of the automata on their computational power.

Maximum linear feedback shift registers (LFSRs) based on primitive polynomials are commonly used to generate maximum length sequences (m-sequences). An m-sequence is a pseudorandom sequence that exhibits ideal randomness properties like balance, run and autocorrelation but has low linear complexity. One-dimensional Cellular Automata (1D CA) have been used to generate m-sequences and pseudorandom sequences that have high linear complexity and good randomness. This thesis considers the use of two-dimensional Cellular Automata (2D CA) to generate m-sequences and psuedorandom sequences that have high linear complexity and good randomness. The properties of these sequences are compared with those of the corresponding m-sequences and the best sequences generated by 1D CAs. / Graduate

Some people believe that IC densities are approaching the fundamental limits inherent to semiconductor technologies. One alternative to semiconductors is Quantum-dot Cellular Automata (QCA); QCA is a nanotechnology that offers the potential to build denser IC's that switch at higher frequencies and run on lower power. QCA's most basic building block, the QCA cell, is inherently binary; digital circuits are implemented by arranging these QCA cells in pre-defined configurations on a two dimensional plane. This paper proposes a logic formulation that describes arranging QCA cells on a two dimensional plane; it is presented as a set of rules that can be implemented with basic Boolean variables and operators. This Boolean formulation is general and can be applied to any given specification. In addition, an optimization constraint is defined so that the logic formulation will only validate the most efficient QCA cell arrangements. The correctness of the logic formulation has been empirically verified by testing it with a SAT solver. The effectiveness of the minimization constraint in conjunction with the logic formulation has been tested with a Pseudo-Boolean ILP solver.

Innovation has long been considered crucial for companies to gain a competitive edge in the global marketplace. Unfortunately, a solid understanding of the system of innovation does not exist. The literature lacks formal definitions and methodologies for the system of innovation. Many surrogates for innovation metrics have been posited in past research but none have solidified the overall concept of an innovation system or science. It has been speculated that innovation as a system is complex. Additionally, some researchers have suggested that this innovation system is adaptive. In these instances, of the literature, surrogates were again utilized in place of solid modeling and hypothesis that is benchmarked against real world case studies. Surrogates, such as patent citation, do serve a useful purpose to assist in the understanding of the historic nature of the innovation system but they fall short of defining the system completely. This paper seeks to aid in the solidification of a hypothesis of the system of innovation as a complex adaptive system. Initial consideration is directed towards the historic interactions that have taken place in the system of innovation. These interactions are viewed through the surrogate of patent citation as there is little other record of innovation. The novelty of this paper is that patent citations form not the core but rather a starting point for the definition of innovation as a complex adaptive system. Various models are built using techniques of cellular automata as well as agent-based modeling to assist in the understanding of the principles at work in the innovation system. These models present startling evidence that there exists an upper bound on the number of interactions any one invention should utilize in its course towards being deemed an innovation. Additionally, the models describe the benefits of partnership between innovating entities in a rapidly changing marketplace such as the current technological markets. This paper asserts specific conclusions, from the models, that assist in understanding that the system of innovation is truly a complex adaptive system. The models are further supported through real world examples.

Marroquin and Ramirez (1990) have recently discovered a class of discrete stochastic cellular automata with Gibbsian invariant measures that have a non-reversible dynamic behavior. Practical applications include more powerful algorithms than the Metropolis algorithm to compute MRF models. In this paper we describe a large class of stochastic dynamical systems that has a Gibbs asymptotic distribution but does not satisfy reversibility. We characterize sufficient properties of a sub-class of stochastic differential equations in terms of the associated Fokker-Planck equation for the existence of an asymptotic probability distribution in the system of coordinates which is given. Practical implications include VLSI analog circuits to compute coupled MRF models.