Welcome to Indian Summer School on Cellular Automata 2022

# Hello Students, this is Cellular Automata India

Duration: 2 months

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: 23rd May 2022 - 22nd July 2022
Registration Last Date: 15th May 2022
Link: Plan for Internship on Cellular Automata Theory and Application.
Registration closed for this year ## This Year's Instructors

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.

1. Complex Rioting phenomenon
2. Traffic Modelling
3. COVID 19 propagation phenomenon
4. Modelling of Distributed System problems
5. 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.

1. Modelling Migration Phenomenon
2. Mapping crystal structure onto Cellular Automata
3. 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.

1. Pattern classification and recognition
2. Clustering
3. Machine Learning
4. Image processing
5. Pseudo Random Number Generation
6. Cryptography
7. Hardware design

## Tentative Projects:

01

### Reversibility and Convergence of 1D Non-uniform CAs under open boundary conditions

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:

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

02

### Multi-seed image segmentation for the microscopic image.

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:
VCnew=Vc if Vc <=Vmax -Vmin :
otherwise, VCnew=Vc=Vmax -Vmin (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

### Pattern formation and self organized criticality

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

### Convergence in α-asynchronous Cellular Automata and Pattern classification

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

### Reversibility in α-asynchronous Cellular Automata and Cryptography

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

06

### Does first degree 1-D cellular automata have any functional capabilities?

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

### Finding the inverse cellular automata of a given 1-D reversible CA

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

### Characterization of 2-D linear cellular Automata using Linear Algebra

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

### Modelling the Spread of Covid-19 with 2-D Cellular Automata

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

### Designing Arithmetic Logic Unit by 3-state cellular automata

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

### Isomorphism in Cellular Automata

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

### Reversibility in 3-state Non-uniform Cellular Automata and Clustering.

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

### Convergence in 3-state Non-uniform Cellular Automata and Pattern Classification

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:

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

14

### Quantitative Nucleation Criterion

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

### Intergranular cracking

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

16

### Cooperative growth

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.

### Say hello to

cellularautomataindia@gmail.com