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.
**Link: **
Indian Summer School 2022 Project Reports

Proceedings of ASCAT 2023 is now available online. Please have a look

Registration closed for this year

Indian Summer School on Cellular Automata 2022 has finished the following projects. Indian Summer School 2022 Project Reports

**Abstract.** This project demonstrated the grouping of the ECA Rules using information theoretic measures in light of Wolfram's classification of ECA, with 88 rule
equivalence classes. This study used the concept of BiEntropy to compute the
approximate information content of a binary string while quantifying the evolution of the macroscopic behavior in space-time diagrams for different rules.
The amount of information processed by a CA rule in a space-time patch was
captured through four proposed measures, i.e., DiffEntropy (DE), SimConfig Ordered (SCO), SimConfigImmediate (SCI), and SimConfigFluctuation (SCF).
Based on the information-theoretic analysis, which was followed by the clustering of entropy values of different configurations through dynamic time warping
(DTW), a Genealogy Interceded Phenotypic Analysis (GIPA) of 88 ECA rules
was proposed.

**Abstract.** In this project we were interested in the use of 2 dimension cellular
automata in social sciences , we were very flexible in the last point as we
also inculed models in urban modeling.We also did not restict ourselevs to
the formal definition of cellular automata as we considered also interesting
models that may be considered close to cellular automata.
We realised programs for all models.

**Abstract.** This project focuses on developing a model that can accurately simulate
COVID-19's global dissemination patterns. We utilize cellular automaton (CA) to build
such a model. In this project, a new variant of CA called Temporary Stochastic Cellular
Automata (TSCA) is used, where two rules is being utilized, one of which serves as
a default rule and the other of which is a probabilistic rule that is applied with some
probability. To consider the mutation of the COVID-19 rule, we employ a set of TSCAs.
Each TSCA is considered as (f, g)[τ] and at a time the applied TSCA is chosen from
the set. The model evolves using two TSCA rules f and g, where f is represented as
the propagation of the virus, g is represented as recovery function and g is applied with
probability τ . The model is validated on the basis of a real-time dataset of spreading
Coronavirus (SARS-COVID-19) over the world. This proposed model depicts the
spreading scenario of the novel Coronavirus which has caused a global pandemic.

**Abstract.** Reversible computation has garnered a lot of attention over the
years,Though studied extensively in a great variety of synchronous
computation models, it is virtually unexplored in an asynchronous framework.
While discussing asynchronous frameworks, alpha asynchronous
cellular automata is a niche topic in the discussion of reversibility. Alpha
Asynchronous cellular automata update their cells according to the value
of alpha, since most of the updation process is based on probability, the
experiments to be done to decide on the reversibility was done over a
range of CA sizes. Further 88 rules were identified which depicted the
characteristics of the 255 rules , and a sample of 10 probabilities were
taken and experiments were conducted for all initial configurations for a
given CA size and given value of alpha.

**Abstract.** In this work, it has been tried to showcase the Dynamics of the Stock Market
with the help of a 2D Cellular Automata. The Active Traders are characterised by the states +1(Buying Stocks) and
-1(Selling Stocks). The Inactive Traders are characterised by 0 State.
Some Simulation Rules(For changing the State of the Traders from Active to
Inactive and Vice Versa) are applied and the simulation is done.
Based on that Simulation, some Graphs are plotted.
After that, Simulation rules are Tweaked.
Instead of checking the Neighbours and keeping the condition on the basis of at
least 1 Neighbour in the Simulation Rules, 'K' and 'l' Neighbours are
respectively checked for the Rule(1) and Rule(2) of Simulation where 'K' and
'l' are taken from the Set {1,2,3,4}.
Graphs are obtained and along with that some Drastic Changes are also
observed in the Dynamics of the Market.
We witness the Strictly Increasing Graphs of the Simulation to become
sometimes Strictly Decreasing when the 'K' and 'l' values are Increased.
In the later part of the analysis, we take The Global Neighbourhood
Condition for the Simulation to resemble the Real Life Stock Market.
These Neighbours are Fully Random in nature.

**Abstract.** 1-dimensional three-neighborhood binary irreversible cellular automata
(also called elementary reversible cellular automata or ECA) is a well explored field both with respect to theory and applications. The irreversible
behavior of such CA, convergence property for point attractors has been
studied in detail for null boundary CA, as well as periodic boundary conditions. The feature set of this cellular automata consists of only binary
numbers 0, 1. As a result, we may believe that this may lead to some
restrictions of such a pattern classifier in its ability, accuracy, capacity
and range of classification. Also, when compared to the real world data,
a 2-feature CA really falls short as most data has the number of features
spread across the discrete number space.

**Abstract.** Reversibility is one of the important chacteristic in the domain of cellular automata since it
gives the notion of preserving the information during the evolution. This property leads to give
wide aspect of applications in many real life scenarios. The main objective of this project work is
to analyse the bijectivity property of the reversible CA with the help of state transition diagram
(STD). This report also describes the modelilng approach by mapping of bits of transition states
with the rule minterm (RMT) sequences to obtain the inverse function for the reversible and
semi-reversible CAs.

**Abstract.** The model takes an input of the desired number of nuclei, which are
then distributed at random throughout the domain. For this system,
we are considering 18 different grain orientations associated with their
own unique colours. Conventionally, cellular automata are associated
with square discretization but here we have implemented hexagonal discretization and attempt to undertake a qualitative comparison between
them.

**Abstract.** This paper contains the keen observations and research on factors of convergence, converging rules and
attractors of Alpha-Asynchronous Cellular automata. Our experimentation will be on elementary cellular automata
from alpha values 0.1 to 1.0 for a set of 88 minimal rules.
In this process our main focus is to track converging rules and record them. To get this information we
developed a program that takes alpha values and rules as input and returns above mentioned information as output.
Our second focus will be on recording the attractors.

**Abstract.** In this project we studied the behavior of 2D linear Automaton generated
by linear rule under the null boundary condition over the field ℤ^{2} transition matrix or rule matrix of this cellular Automata by represent each cell
of block into linear form 1, 0 according to dependency and independency
of each cell respectively determined by applied rule.

**Abstract.** This work focuses on the isomorphism of cellular automata (CAs). Two
cellular automata are said to be isomorphic if their configurations evolve
in the similar way. As a model, here we use non-uniform elementary cellular automata under null boundary and discover few inherent properties
of CAs to decide whether the given cellular automata are isomorphic.

**Abstract.** Image segmentation is one of the most important image processing techniques for biological images. Till now, various Cellular Automata(CA)
rules have been used for segmentation. For updation of states of the cell,
conditional rules using Von Neumann neighbourhood and Moore neighbourhood were used. In this work, instead of taking one seed point per
image, multiple seed points are used for segmentation. A dataset of microscopic images has been taken and various segementation rules have
been used for analysis.

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.