Cellular Automata-Basics: Applications in Problem Solving

Cellular Automata-Basics: Applications in Problem Solving

Simanti Bhattacharya (University of Kalyani, India) and Angshuman Bagchi (University of Kalyani, India)
DOI: 10.4018/978-1-5225-0058-2.ch025
OnDemand PDF Download:


Cellular Automata (CAs) are spatially arranged systems, composed of units or cells having distinct information and all are under uniform condition. This system gradually progresses with time evolution based on the local information following a specific rule and achieves a configuration that reflects the global scenario. It very efficiently mimics large complex system, segmented into local units and hence makes the calculations easy. The local changes are integrated in a synchronized manner to give the final outcome with the essence of robustness associated with simple and uniform functions applied throughout. This has made CA to be successfully applied in various fields of scientific researches. This book chapter describes the fundamental properties of CA and its structures. Then it advances to the simple rule construction and local to global configuration. Finally it discusses the vast applicability of CA in different segments of science, specifically in the field of biological researches.
Chapter Preview


Computer programs and their applicability have evolved for the betterment of studying science with detail visualization and deeper understanding. An advanced technique, of late, called Cellular Automaton (plural cellular automata; CAs), has provided the scientific study a new direction (Kari, 2005). In principle, CAs are discrete dynamical body or concise cells with potent information whose behavior is directed by its interaction with adjacent or neighboring cells. Several real life phenomena happening in this world carry unique properties and large assembled bodies. These properties give the system its identity with which it can be described easily. In this CA technique, the complex behavior of a system, to work with, is reduced in such a way that the system can be represented as single unit with specified or marker properties. In other words, the complex world is simplified with simple mathematical formula and local information. In the present world, various computer aided mathematical approaches have been used in several aspects of scientific researches. But with simple mathematical constructs and distinguished features, CA has become a powerful tool to model and to simulate real world complex scenario to be analyzed simply (Schiff, 2007). The history behind CA’s build up, discussed later in this chapter, was associated with its dynamical behavior where it could represent a self replicating and continuously changing live event. Almost every event, from any field of science, has this replicating property which is also dependent on the behavior of the neighboring element adjacent to it.

In this context, it is worthy to mention that the intrusion of computational applications in biology has developed a huge database of information regarding different aspects of life and cells. And biological cells truly stand for very good examples of self duplicating and continuously growing system that needs information exchange from its neighboring cells as well as environment. But the reactions that range from micro to nano magnitude and their web of interdependence have made the study of cellular events very complex and cumbersome. There was and is always a need to model the biological system to understand the phenomena occurring in the system. Several models and applications have evolved to solve the issue but with the application of CA, biological research has achieved a new and better dimension. And other side of the coin reflects that CA has also got its true object to be applied in(Schiff, 2007).

Since the first proposal of CA’s concept in 1940’s, CA has emerged to touch the new heights with up-gradations and has stepped into almost every field of science as well as social sciences. The simpler form of CA has gradually evolved with time to make it suitable for multidirectional studies. The different forms of CA have enriched the researcher to gain the précised overview of a dynamical organization in different ways, although it also experiences limitations in certain cases. Present day research does not need a new introduction for CA and its forms and applications since over the years experts have surveyed as well as have come up with newer idea to make the system better (Mitchell, 1996). This chapter gives a simplified overview of CA, its basic structures. The mathematical rules that govern CA systems have been discussed here. This chapter has tried to focus at the evolution of CA from local to global properties and how these properties are applied to construct a CA. This also gives a brief overview of the vast field where CA is majorly applied. Specifically it has explored the area of biology research. Our main theme for this chapter is to identify the spread of CA’s application in the field of biological research. We also have tried to drag out the fields deprived of CA’s touch. This overview therefore will help biology researchers to address their problems with simpler application of CA.

Key Terms in this Chapter

Dimension: A scale to decide the spread or range of the neighborhood of CA grid.

Phase Space: A space that reflects the state or phase of a module of CA at a given time frame.

Attractor: A fixed point or a set of data around which the system tries to evolve with time.

Transition Factor: A factor that governs or decides the progress of a system following certain deterministic rules.

Generation: The outcome with the integration of changes from the initial state with the advancement in time.

Configuration: Arrangement of parts or units of elements in a pattern whose co-ordinates can be addressed.

Self Replicating: A unit or system whose components replicate or reproduce themselves in an indistinguishable configuration with the change in time frame.

Periodic: A phenomena that exhibits repeat appearance after definite time interval.

Neighborhood: The adjoined cells that affects the state of a particular cell in CA.

Quiescent State: A state at a specified time point, when all cells with similar properties show same physical state (dormant) in a CA system.

Self Organizing: The point when a system, started with initial chaos, evolves into a fixed configuration with all cells behaves or changes at a synchronized manner.

Fractal Pattern: A pattern, as per mathematical modeling, that exhibits organized repetition of same pattern after definite time interval.

Decision Tree: A graphical representation or plot that reflects the initial states, evolution and possible outcome of a CA that is guided by specified rules.

Module/Cantor: The localized unit of a system/CA which mimics the global system in a miniature fashion but possesses required information and evolves with time.

Evolution: The process that declares the final outcome or configuration which is achieved integrating small local changes in the units of a system with the change in time. This phase can be stable, periodic or may end up in total chaotic situation.

Chaos: A state of disorder where each unit of a system behaves independently from each other at the same point of time.

Complete Chapter List

Search this Book: