Cellular Automata Innovative Modelling For Science And Engineering

Edited by Alejandro Salcido

Published by InTech
Janeza Trdine 9, 51000 Rijeka, Croatia
Copyright © 2011 InTech

Modelling and simulation are disciplines of major importance for science and engineering. There is no science without models, and simulation has nowdays become a very useful tool, sometimes unavoidable, for development of both science and engineering. The numerical solution of diff erential equations  has for many years been a paradigm of the computational approaches for simulation. Nevertheless, some conceptually different strategies for modelling and simulation of complex behaviour systems have been developed from the introduction of the innovative concept of cellular automata by Stanislaw Ulam and John Von Neumann in the early 1950s. Cellular automata are dynamical systems which consist of a fi nite-dimensional latt ice, each site of which can have a fi nite number of states, and evolves in discrete time steps obeying a set of homogeneous local rules which defi ne the system´s dynamics. These rules are defi ned in such a way that the relevant laws of the phenomena of interest are fulfi lled. Typically, only the nearest neighbours are involved in the updating of the latt ice sites.

The main att ractive feature of cellular automata is that, in spite of their conceptual simplicity which allows an easiness of implementation for computer simulation, such as a detailed and complete mathematical analysis in principle, they are able to exhibit a wide variety of amazingly complex behaviour. This feature of cellular automata has att racted the researchers’ att ention from a wide variety of divergent fi elds of the exact disciplines of science and engineering, but also of social sciences, and sometimes beyond. The collective complex behaviour of numerous systems, which emerge from the interaction of a multitude of simple individuals, is being conveniently modelled and simulated with cellular automata for very diff erent purposes.

In this book, a number of innovative applications of cellular automata models in the fi elds of Quantum Computing, Materials Science, Cryptography and Coding, and Robotics and Image Processing are presented. Brief descriptions of these outstanding contributions are provided in the next paragraphs.

Quantum Computing. Chapter 1 presents an information-theoretic framework to investigate the relationship between stochastic behaviors and achievable reliable performance in quantum cellular automata technology. The central idea is that quantum cellular automata devices can be modelled as a network of unreliable information processing channels. In Chapter 2, cellular automata with graphane structured molecules and graphane nanoribbons to propagate and process digital information are proposed. The cells that make up the architecture of the automata correspond to the molecules and to sections of the nanoribbon. It is also intended to verify theoretically that the proposed system is scalable, and binary information can be stored, propagated and processed at room temperature. Chapter 3 describes a magnetic quantum dot cellular automata approach for twisting computation and its technological implementation. The fundamental technological hypothesis (the snake-clock implementation) is explained, and an example of circuit description is given, followed by a specifi c architectural solution adopted with the low-level details. The contribution presented in Chapter 4 extends and implements several of the reversible and quantum computing concepts to the context of elementary cellular automata, and this includes a new method for modelling and processing via the reversibility property in the existence of noise. The main contribution is the creation of a new algorithm that can be used in noisy discrete systems modelling using conservative reversible elementary cellular automata and the corresponding quantum modelling of such discrete systems. This approach considers the important modelling and processing case which uses Swapbased operations to represent reversible elementary cellular automata even in the presence of noise. Chapter 5 reviews self-assembly of InAs quantum dot molecules with diff erent features fabricated by the combination of conventional Stranski-Krastanow growth mode and modifi ed molecular beam epitaxy technique using thin or partial capping as well as droplet epitaxy. InGaAs quantum rings with square shaped nanoholes are realized by droplet epitaxy, which are utilized as nano-templates for quadra quantum dot molecules where four InAs quantum dots are situated at the four corners of a square. This quadra quantum dot set is a basic quantum cellular automata cell for future quantum computation. Chapter 6 provides a brief overview of the basic properties of quantum information processing and analyzes the quantum versions of classical cellular automata models. Then it examines an application of quantum cellular automata, which uses quantum computing to realize real-life based truly random network organization. This abstract machine is called a quantum cellular machine, and it is designed for controlling a truly random biologically-inspired network, and to integrate quantum learning algorithms and quantum searching into a controlled, self-organizing system. Chapter 7 proposes a new and simple approach for designing high-performance molecular quantum cellular automata. It reviews two approaches for the theoretical study on the two-site molecular quantum cellular automata and discusses the influence of complex charge n on the signal  transmission through molecular quantum cellular automata.

Materials Science. Chapter 8 of this section discusses a combined approach of a threedimensional frontal cellular automata model with a fi nite element model which has been developed for modelling the macrostructure formation during the solidifi cation in the continuous casting line. This joint has allowed improving accuracy of modelling. Calculated distribution of the temperature gives a basis for the simulation of macrostructure formation close to the real one. In Chapter 9, a novel point automata method is developed and applied to model the dendritic growth process. The main advantages of this method are: no need for mesh  generation or polygonisation; the governing equations are solved with respect to the location of points (not polygons) on the computational domain; it allows rotating dendrites in any direction since it has a limited anisotropy of the node arrangements; it off ers a simple and powerful approach of cellular automata type simulations; it off ers straightforward node refi nement possibility, and straightforward extension to 3D. Chapter 10 proposes a model based upon the coupling of a modifi ed cellular automaton model with the growth calculation of a nucleus in a given nucleation cell, to simulate the evolution of the dendritic structure in solidifi cation of alloys. For a free dendritic growth in the undercooled melt, it is found that the proposed model can quantitatively describe the evolution of dendritic growth features, including the growing and coarsening of the primary trunks, the branching of the secondary and tertiary dendrite arms, as well as the solute segregation patt erns. Moreover, the directional solidifi cation with the columnar and equiaxed grains is simulated by the proposed method and the evolution from nucleation to impingement between grains is observed. Chapter 11 underlines that modelling at a mesoscopic scale using cellular automata appears as an interesting tool to understand general properties of corrosion processes. One part of the chapter focuses on the diff usion and the feedback eff ect of the layer on the corrosion rate, but no explicit reactions are taken into account. The model developed gives a simple description of a phenomenon of passivation. In other part the models are improved by introducing more explicitly some basic chemical and electrochemical processes. This was illustrated by considering a heterogeneous process in which a metal recovered by an insulating fi lm is put in contact with an aggressive medium due to a local rupture in the fi lm. Cryptography and Coding. Chapter 12 describes the variable-length encryption method. It is a cryptographic model based on the backward interaction of cellular automata toggle rules. This method alternates during the ciphering process the employment of the original reverse algorithm with a variation inspired in Gutowitz’s model, which adds extra bits when a preimage is calculated. Using the variable-length encryption method it is guaranteed that ciphering is possible even if an unexpected Gardenof Eden state occurs. A short length ciphertext depends, however, on the secret key specification. The proper specification of the rules/key was deeply investigated in this chapter. In Chapter 13, as an application of quantum cellular automata technology, the Serpent block cipher (a fi nalist candidate of Advanced Encryption Standard) was implemented. This cryptographic algorithm has 32 rounds with a 128-bit block size and a 256-bit key size, and it consists of an initial permutation, 32 rounds, and a fi nal permutation. Each round involves a key mixing operation, a pass through S-boxes, and a linear transformation. In the last round, the linear transformation is replaced by an additional key mixing operation. Simulation results were obtained from QCADesigner
v2.0.3 soft ware. Chapter 14 proposes a multi-dimensional and multi-rank pseudorandom generator for applied cryptography, which combines the 3D cellular automata algorithm and the linear feedback shift register architecture. The feasibility and effi ciency of the algorithm were studied by using several tests. The fi nal result showed they also can provide bett er pseudorandom key stream and pass the FIPS 140-1 standard tests. In Chapter 15, an effi cient pseudorandom number generator based on hybrid between one-dimension and two-dimension cellular automata is proposed. The proposed algorithm is compared with previous works to check the quality of randomness. It could generate a good quality of randomness and pass by the ENT Walker and DIEHARD Marsaglia test suite. In Chapter 16, from a series of definitions, propositions and theorems, a solid foundation of variant logic framework has been constructed. Under selected sample images and operational matrices, a set of typical results is illustrated. This construction can be observed from diff erent view-points under locally and
globally symmetric considerations, in addition to detect emerging patt erns from each recursively operations and a functional space viewpoint, further global transforming patt erns can be identified. The mechanism can be developed further to establish foundations for logical construction of applications for computational models and structural optimisation requirements.

This entry was posted in Articles and tagged , , . Bookmark the permalink.

2 Responses to Cellular Automata Innovative Modelling For Science And Engineering

  1. Chair Review says:

    Great! thanks for the share!

  2. I simply appreciate this brief article a good deal, hope you might develop much more about it.