Cellular
Automata
India

This is the second year of internship program on Cellular Automata: Theory and Applications for the undergraduate students. This year the internship is more rigorously project based and the theory relevant to the projects will
be discussed in class. **Mode of Internship:** Hybrid.

**Duration: ** 23^{rd} May 2022 - 22^{nd} July 2022

**Registration Last Date:** 15^{th} May 2022**Link: **
Plan for Internship on Cellular Automata Theory and Application.

Registration closed for this year

This is the second year of internship program on Cellular Automata: Theory and Applications for the undergraduate students. This year the internship is more rigorously project based and the theory relevant to the projects will be discussed in class. The mode of internship is hybrid.

**Mode of Internship:** Hybrid.

**Registration Last Date:** 15^{th} May 2022

**Duration: ** 23^{rd}May 2022 - 22^{nd} July 2022

After conducting some theory classes on cellular automata, students will be assigned projects in group. The projects will be given from four major areas - reversibility, conververgence, modelling and technology.

** Reversibility:**

Reversibility refers to a characteristic of a system that allows the system, for each transition from an initial configuration to a final configuration, to come back to the initial configuration. Many physical systems,
including microscopic systems, are reversible. In mathematics, if a function is bijective, then we can get its inverse. So, for a system, if we can see the transition from one configuration to another as a function, then we can say that
the system is reversible if and only if the transition function is bijective. A cellular automaton can also be seen in terms of (global) transition function. Now it is interesting and challenging to decide if a given cellular automaton
is reversible or not. It is particularly interesting from a modelling point of view, if we want to model a reversible system by a cellular automaton, and an application point of view, if the application demands loss of information during
execution.

**Convergence:**

Convergence is an opposite phenomenon of reversibility, where a system cannot come back to its initial configuration after moving out of the configuration. Rather the system, in course of its evolution, settles down
to a configuration (convergence point) or to a small set of configurations. A range of physical systems show this convergence phenomenon. Like reversibility, it is challenging and interesting to decide if a given cellular automaton converges
to a fixed point from any initial configuration. The cellular automata that show convergence behavior have a range of applications in many fields, including Machine Learning.

**Modelling:**

Cellular automata have been historically used as a method for modelling biological and physical systems, and utilized to theoretically study such systems. Now-a-days, cellular automata based simulations are widely used
in a great variety of domains, from statistical physics to social science. Following are some examples where cellular automata have been used for modelling.

- Complex Rioting phenomenon
- Traffic Modelling
- COVID 19 propagation phenomenon
- Modelling of Distributed System problems
- Modelling of Artificial Life dynamics

The students can also revisit the modelling capability of cellular automata for the above problems. In fact, any phenomenon related to various disciplines such as Physics, Chemistry, Computer Science, Civil Engineering, Material Science and Engineering, Mining Engineering, Mechanical Engineering, Social Science, etc. can be modelled by cellular automata. For example, following modelling problems can be considered.

- Modelling Migration Phenomenon
- Mapping crystal structure onto Cellular Automata
- Modelling of various aspects of Thermodynamics

**Technology:**

Technology refers to the collection of techniques, methods or processes used to provide some services or solutions to problems, or in the accomplishment of an objective, such as scientific invigilation. Since the
late 1980s, cellular automata have been used as solutions to many real-life technological problems. In the light of recent developments in the theory of cellular automata, this area of projects attempts to explore the new generation technological
possibilities of cellular automata. In particular, technological problems under the following domains are to be considered here.

- Pattern classification and recognition
- Clustering
- Machine Learning
- Image processing
- Pseudo Random Number Generation
- Cryptography
- Hardware design

01

The target of this project is to study the reversibility and convergence of finite 1D non-uniform cellular automata (CAs) under different open boundary conditions. Reversibility and convergence of the finite CAs are generally studied under null and periodic
boundary conditions. Apart from null boundary condition, which is a type of open boundary condition, there are few more types of open boundary conditions, such as adiabatic boundary condition, reflexive boundary condition,
intermediate boundary condition, etc. It has already been shown that the Reachability tree can successfully characterize the CAs under null and periodic boundary condition. Recently Reachability trees for adiabatic
and reflexive boundary conditions have been developed. It has been observed that the basic properties of reachability trees remain the same. Hence, the properties of null boundary CA can easily be extended to CAs under
other (open) boundary conditions.

Project objective:

- Define reachability trees under various boundary conditions.
- Propose a generalized scheme to synthesize CAs that converge to a fixed point.
- Propose a generalized scheme to synthesize reversible CAs.
- Study the effect of boundary conditions on the reversibility and convergence of CAs.

02

The target of this project is to find a rule for image segmentation in microscopic gray-scale image. A gray-scale image can be considered as a configuration of a 2D cellular automaton (CA) with 256 states per cell. The
target of the project is to find a rule for image segmentation in microscopic images. The researcher already used various CA rule for segmentation. For example, An approach proposed by Wongthanavasu and Sadananda was
based on a conditional rule for updating the state of cellular as:

V_{C}^{new}=V_{c} if V_{c}
<=V_{max} -V_{min} :

otherwise, V_{C}^{new}=V_{c}=V_{max} -V_{min} (1)

where, vmin and vmax are the minimum and maximum states (gray scale value of the image),
The von nuemann neighbourhood concept was considered.The central cell Vc was changing using the equation 1.. By changing the threshold function as a transition function, various CA rule can be used for segmentation
and edge detection can be performed. Instead of taking one seed point per image (Vc), we can use multiple seed points. In microscopic images, there are repeated patterns so it may be useful.

03

Even though basic physics laws are simple, how does our world become so complex? How does complexity arise from simple laws? A striking example of such emergent complexity is life itself. How does a single fertilized egg
develop into a multicellular organism with highly complex internal structures?

As a computer scientist our interest is formation of complex patterns from simple local rules. Moreover, we want to understand the mathematics behind the formation of such complex patterns.

04

Informally, pattern classification is a sub-topic of machine learning. It is concerned with the automatic discovery of regularities in data through the use of learning algorithms.

On the other hand, a cellular automaton is a mechanism for modelling systems with local interactions. A cellular automaton is defined over a regular grid, each cell of which consists of a finite automaton that
interacts with its neighbours to go to its next state. Like other synchronous systems, the cellular automata assumes a global clock that forces the cells to get updated simultaneously. However, in an asynchronous model
of cellular automaton, cells are independent and are, therefore, updated independently during the evolution of the system.

The target of this project is to design an efficient multi-class pattern classifier utilizing an asynchronous model of cellular automata.

05

This project will study the reversibility of α-asynchronous cellular automata, and finds its application in cryptography.

06

We have already introduced first degree 1-dimensional cellular automata rules which can be represented in a simple equation with degree one, or more specifically by just specifying the value of six constants. Now, can these simple looking rules calculate something when working parallelly? In this project, we want to introspect this aspect of the CAs and look into their functional capabilities. We may consider the either nearest neighbor decimal CAs or elementary CAs for simplicity.

07

Curtis - Hedlund - Lyndon Theorem shows that a cellular automata is reversible if and only if it is a bijective map. For a reversible cellular automata, the inverse function is also a cellular automata. We can decide whether a CA is reversible or not from its local rule (and CA size for finite cases). However, till date there is no efficient way to find out what is exactly the inverse CA for this reversible CA defined in terms of its local rule. This project aims to put some light on it.

08

Matrix algebra is a very useful way to characterize the behavior of linear 1-D CAs. For 1-D CAs, the T matrix corresponding to the CA rule is a 2-D one, that is order is increased by 1. For 2-D CAs, however, we don't have any such efficient characterization tool. One approach is representing 2-D linear CAs as 1-D and then applying Matrix algebra. Now, what if, instead of this, we increase the order of the array by 1 again, take 3-D array and analyze the behavior of CA by applying some algebraic operations over this 3-D array. Can we characterize the linear 2-D CAs in this way? This project is to investigate this issue. Target of this project will be to define a new operator for operating between 2-D configuration array and the 3-D rule array and finally come up with a new algebra that uses this operator.

09

Cellular Automata can be an excellent way to model the spread of epidemics like Covid-19. In a CA, time and space both are discrete, and the cells are updated in parallel. There are in fact a number of similarities of COVID-19 spread with CAs. Like the neighborhood of CAs, this virus also spreads through direct contact with the infected persons. Further, this spreading has occurred through human chains. So, if we model this spreading over the demography as a CA, we can consider COVID-19 as a CA rule which transmits its information (infection here) through local interconnections. However, due to domestic and international flight connection among several cities, COVID-19 of one geographical area has infected a distant geographical area. This non-local behavior of COVID-19 spread can also be handled if we allow the cells to have some distant neighbors. This project targets to build a simulator which can reflect the real-life data of COVID-19 spread as well as model the mutations of the virus and the measures taken by humans.

10

With the effect of Moore's law hitting the limit, there has been an increased demand for going towards non-binary multi-valued logic. Among all multi-valued logics, ternary logic is the most optimized logic in terms of number of operations required. This project wants to explore the possibility of designing a complete Arithmetic Logic Unit using (balanced) ternary logic based on 1-dimensional ternary cellular automata.

11

During the evolution of a finite cellular automaton, every configuration is attracted to a distinct cycle (a cycle is formed by one or more than one configuration(s)). The collection of cycles along with their lengths is called the cycle structure of that CA. If two cellular automata are given, they are called isomorphic if both the cellular automata have the same cycle structure. Our objective is to design an algorithm which decides whether the given CAs of the same size are isomorphic or not.

12

One-dimensional three-neighborhood binary reversible cellular automata (also called elementary reversible cellular automata) is a well explored field both in respect of theory and applications. The cyclic behaviour of such cellular automata has been studied in detail for null boundary cellular automata. The reversible cellular automata can be used as natural clusters and it has already been shown that this category of cellular automata can be used in designing effective clustering techniques. By extensive experiments (using real datasets), it has been established that our algorithm is as effective as hierarchical clustering technique. These properties of elementary reversible cellular automata instigates us to synthesize reversible three-neighborhood 3-state cellular automata and role of such cellular automata as clustering tool.

13

1-dimensional three neighborhood binary irreversible cellular automata (also called elementary reversible cellular automata) is a well explored field both in respect of theory and applications. The irreversible behaviour
of such CA, moreover Convergence property for point attractor has been studied in detail for null boundary CA, as well as periodic boundary condition.. It has already been observed that a set of elementary non-uniform
non-linear MACA with only point attractor is a natural pattern classifier. Using various real-life data set CA based pattern classifier prove its efficiency. However, one the restriction of such pattern classifier
is, it deal with binary features. In this project, we want to use 3- state 1-dimensional CA (uniform and nonuniform) for pattern classification.

Project objective:

- Identify set of rules that always converges to point state attractor
- Using those rules implement pattern classifier
- Compare the performance of elementary CA as pattern classifier and 3-state 1D CA as pattern classifier.

14

Target of this project is to devise and implement appropriate rules for modelling nucleation associated with dynamic recrystallisation. In a polycrystalline system, instead random nucleation, this study would allow quantitative positioning of the recrystallising nuclei.

15

This work aims to quantitatively model the growth of cracks along the grain boundaries in polycrystalline systems.

16

Target of this project is modelling transition that apparently indicates the spatial re-distribution of the initial states. This re-distribution ultimately translates to the accumulation and growth of a 'phase' in a system. Conservative CAs will be utilized for this study.