# Towards Optimal Path Allocation for Unreliable Reconfigurable Intelligent
Surfaces

Mounir Bensalem∗, Anna Engelmann∗ and Admela Jukan∗<EMAIL_ADDRESS>∗Technische Universität Braunschweig, Germany; {mounir.bensalem, a.jukan}@tu-
bs.de

###### Abstract

Terahertz (THz) communications and reconfigurable intelligent surfaces (RISs)
have been recently proposed to enable various powerful indoor applications,
such as wireless virtual reality (VR). For an efficient servicing of VR users,
an efficient THz path allocation solution becomes a necessity. Assuming the
RIS component is the most critical one in enabling the service, we investigate
the impact of RIS hardware failure on path allocation performance. To this
end, we study a THz network that employs THz operated RISs acting as base
stations, serving VR users. We propose a Semi-Markov decision Process
(SMDP)-based path allocation model to ensure the reliability of THz
connection, while maximizing the total long-term expected system reward,
considering the system gains, costs of link utilization, and the penalty of
RIS failure. The SMDP-based model of the RIS system is formulated by defining
the state space, action space, reward model, and transition probability
distribution. We propose an optimal iterative algorithm for path allocation
that decides the next action at each system state. The results show the
average reward and VR service blocking probability under different scenarios
and with various VR service arrivals and RIS failure rates, as first step
towards feasible VR services over unreliable THz RIS.

###### Index Terms:

SMDP, path allocation, virtual reality , reconfigurable intelligent surfaces,
reliability.

##  I Introduction

Virtual Reality (VR) applications are envisioned as one of the key
technologies that will advance the human to machine interactions where a user
is present and acts in a virtual world [1]. In order to satisfy the high
demand of data rates that VR applications require, the THz frequency band is
currently one of the most promising communications technology to provide a
high quality VR experience. As THz communication is characterized by
directional and sensitive to attenuation beams, a new technology called
Reconfigurable Intelligent Surfaces (RIS) is used to enhance the performance
of THz wireless communications [2]. In an indoor setting, the usage of RIS in
THz communications is rather critical, since by controlling the reflective
properties of the underlying channels, we can mitigate various THz
transmission impairments [3].

It is known that RIS elements, also called unit cells or meta-atoms, are
vulnerable to failures, which can cause deterioration of the antenna radiation
pattern, and in severe cases, the RIS failures can affect the functioning of
RIS meta-surface elements [4]. In addition,THz links between users and RISs
can be blocked, due to various obstacles. In order to design reliable RIS
based networks in practical environments, it is becoming essential to develop
path allocation schemes that are aware of RIS meta-surface failures, as well
as link failure between RISs and users. The path allocation problem in RIS
networks is indeed one of the key problems to solve for any efficient RIS
design, where several sub-problems can be investigated, including channel
allocation, power allocation, RIS-to-user assignment, and phase shifts design.
Few works studied resource allocation problems, but no work to date considered
the problem of path allocation under faulty RIS scenarios. To the best of our
knowledge, path allocation of VR over THz RIS, considering the unreliability
of RIS devices has not yet been investigated.

In this paper, we consider path allocation in the VR applications over RIS
network with controlled access of VR users request by Semi-Markov decision
Process (SMDP). We introduce an optimal path allocation scheme to ensure the
reliability and maximize the system reward in a set of RISs, whereby a RIS
device consists of blocks of meta-surfaces which are vulnerable to failures.
We formulate the problem of RIS-unreliability-aware path allocation as an SMDP
model considering multiple RIS devices in an indoor environment used to
allocate THz meta-surfaces blocks to VR users. Following the definition of
SMDP [5], the decision is taken at the event occurrence, while an iterative
algorithm proposed maximizes the total long-term reward of the VR over RIS
system, considering the factors of user’s income of the accepted services, the
costs for occupying paths, and penalty of RIS and meta-surface failures. We
make realistic assumptions on the reference THz network model, where a set of
backup RIS devices are used to ensure the reliability of the system. When a
RIS or a meta-surface fails, other blocks of meta-surfaces in the same RIS or
in the corresponding backup RIS are allocated to transfer the existing
services, which allows the RIS network to operate in a reliable fashion.
Numerical results show the average reward and blocking probability with
various service arrival and RIS failure rates, and under different network
configurations. We show that our scheme improves the QoS of THz communication
with regard to the arrival rate of service requests and RIS meta-surfaces
availability. The results show that increasing the number of RISs and meta-
surfaces does not always improve the performance in terms of long-term reward
and service blocking for service arrival rates below a certain threshold.
Hence, our model can help dimensioning RIS THz networks in terms of costs and
performance based on the expected service rate.

The rest of this paper is organized as follows. Section II discusses the
related work. Section III presents the SMDP based path allocation model in
indoor THz network, with unreliable RIS. Section IV describes the proposed
optimal iterative-based solution. Section V evaluates the performance. We
conclude the paper in Section VI.

##  II Related Work

VR communication has been recently investigated in several seminal works [6,
7], focusing on studying the VR Quality of Service (QoS). In [6], a VR model
was studied that detect the tracking and delay components of VR QoS. In [7]
the downlink of VR requests over RISs network, operating over the terahertz
(THz) frequency bands, was considered, and a solution was proposed to the
problem of associating RISs to virtual reality users.

Due to the importance of hardware failures, the baseband complex received
signal from a RIS element has been modeled in [8], considering faulty
reflecting elements of RIS. Thus, in order to design reliable RIS based
networks in practical environments, it is essential to develop resource
allocation schemes aware of RIS array failures. The optimal number of
reflecting elements in a RIS has been studied theoretically in [9] to maximize
the transmission rate in a point-to-point link. Motivated by this work, which
concluded that new, sophisticated resource allocation schemes are needed, we
use a model of a VR over THz RIS network under the similar failure assumptions
to solving path allocation problem. Recent works studied the resource
allocation problem in THz RIS networks specifically. Paper [10] studied
different types of active RISs (active and passive), considering their
hardware architectures, operation modes, and applications in communications,
and also highlighted the need of developing efficient resource allocation
solutions, which is still an open challenge. In [7], a virtual reality network
was considered and a solution was proposed to the problem of associating RISs
to virtual reality users operating over the terahertz frequency bands. In
particular, the paper formulates a risk-based framework based on the entropic
value-at-risk and optimize the transmission rate and reliability. A single RIS
device was considered and the formulated problem aims at achieving higher
order statistics of the queue length, in order to guaranteeing continuous
reliability. We adopt a similar VR over RIS model as in [7], however our focus
is not on optimizing the transmission rate by adjusting the queue length.
Instead, we assume the existence of multiple RISs that can provide the same
set of VR users, as well as the possibility to allocate multiple paths for the
same VR user request, while considering the failure possibility of RISs and
meta-surfaces.

It should be noted that path allocation problem has been well investigated in
other contexts such as in vehicular networks. In [11], an SMDP-based path
allocation scheme was proposed in vehicular ad-hoc networks to maximize the
overall system rewards, while servicing user requests through roadside units.
The paper concluded that due to the high mobility of users, an SMDP policy for
the path allocation problem can improve the QoS. Motivated by this work, we
could see the VR over RIS network as a cognitive-enabled vehicular ad hoc
networks, where VR users can be mapped to vehicle users, RISs could replace
the roadside units (RSUs), and the allocation of meta-surface blocks can be
seen as path allocation, which is our approach in this paper. SMDP-model was
also proposed in [12] to solve path allocation problem in order to maximizing
throughput in the context of vehicular networks. The related work is primarily
based on linear programming which is known to be an NP hard problem, and that
it works for off-line processing, whereas our proposed model works for online
channel assignment to users using an iterative solution, that assumes the
knowledge about some system statistics, such as the RIS failure, service
arrival, and service departure. Moreover, our approach assumes that the system
statistics are known, and that the RIS configuration such as phase shift and
power control are managed by other algorithms independently. Thus, our
approach is focused on path allocation only, as a function of VR user’s THz
channel request behavior. We also do not consider the dependency between RIS
failures, which is a limitation, as is the intrinsic limitation of SMDP to
scale to larger systems.

##  III SMDP based Channel Allocation of VR over THz RIS

In this section, we model a RIS-based wireless reference THz network in an
indoor area, provide the channel model, analyze the channel states and
actions, transmission probabilities, as well as rewards analysis.

Figure 1: The reference indoor THz RIS network.

###  III-A The reference network and assumptions

The reference THz network is illustrated in Fig. 1. The THz network consists
of a set of RISs, small base station (SBS) operating over THz frequency, RIS
controller, and VR users distributed in an indoor environment. RISs are placed
in an indoor environment where they can be reached by users in certain areas
based on the distance, direction and the existence of obstacles. The users are
assumed to be mobile and can have different locations in the indoor
environment. The VR user’s end-devices can send several service requests
through the RIS network. Each mobile wireless VR user is serviced by a main
RIS, using a certain allocated blocks of meta-surfaces. We assume that the
block of meta-surfaces can be non-functional due to hardware problems, e.g.,
due to dirty surfaces or failure. Thus, the RIS controller allows to re-
allocate service request to another available meta-surfaces of the same RIS,
or meta-surfaces of a backup RIS. The SBS is responsible for receiving
requests from VR users and service them via RIS components. The uplink of VR
service requests is adopting an ultra reliable low latency communications
(URLLC) scheme, similar to [7]. In this study, we consider the downlink of the
RIS-based network only, where each RIS is covering a part of the indoor
environment and can provide THz communication channel to VR users. The end-
devices of VR users can send several service requests through the RIS network.
Each RIS can reflect the beams received from a main THz SBS, which generally
uses a MIMO system. A RIS contains a very large number of passive reflective
elements called meta-surfaces, capable of reconfiguring properties of
electromagnetic (EM) waves impinging upon them. We assume that all RISs are
connected to the RIS Controller responsible for channel tuning by changing the
phase of the reflected signal [13]. We assume that a RIS contains several
blocks of meta-surfaces, configured to create a path from the SBS to a user.
These blocks can be allocated based on the system availability. In order to
ensure the reliability of the system, we pre-reserve a backup RIS to each
operating RIS. We assume that services can be transferred from the operating
RIS to the backup RIS when operating RIS or a single block of meta-surfaces or
a THz connection to a RIS fails. Figure 1 illustrates three failure scenarios.
First, when a block of meta-surfaces fails, we assume the failure of the block
will affect at most one user, while all other RIS blocks remain unaffected. To
insure the reliability, we first check whether the main operating RIS has
available meta-surfaces for re-allocation, otherwise connection from the main
RIS is transferred to an available backup RIS. When an entire RIS fails, all
connections will be affected and transferred to a backup RIS. The same
recovery strategy is applied, is a THz connection between RIS and VR users
fails, as shown in Fig. 1.

Without loss of generality, we assume that the RIS network can include
heterogeneous RIS devices, of various sizes and containing different number of
blocks of meta-surfaces, and thus servicing different number of user through
multiple paths. When a VR service requested by VR user is detected, the RIS
controller accepts or rejects it based on the availability of paths, i.e the
RIS resources. In this paper, we assume that the THz link between the VR user
and the RIS can be blocked and fail with a certain probability, and the link
between RIS and the THz SBS is reliable and cannot be disrupted by obstacles.
A VR user-RIS failure caused by an obstacle will result in a failure of the
THz connection and creates a delay, which affects the QoS. We assume that a
RIS and a meta-surface can face a hardware failure, and propose as next a
novel path allocation scheme.

###  III-B Channel Model

This model focuses on the THz link between VR users and the RIS, where the VR
user is mobile. The user movements can cause signal blocking due to self
blocking, or due to other mobile or fixed obstacle in the indoor environment,
as described in [7]. We assume the time slots indexed by $t$ have a period
duration $\tau_{0}$. We denote by $L_{r,n,u,t}$ a binary random variable,
which is equal to $1$ when the Line-of-Sight (LoS) link between the meta-
surface $n$ of the RIS $r$ and the user $u$ at time slot $t$ is available and
0 otherwise. The corresponding random channel gain is defined as in [7] as:

$h_{r,n,u,t}\\!\\!=\\!\\!\begin{cases}\left(\frac{c}{4\pi
fd_{r,u,t}}\right)^{2}e^{-k(f)d_{r,u,t}},&\text{if }P(L_{r,n,u,t}=1),\\\
0,&\text{if }P(L_{r,n,u,t}=0).\end{cases}$ (1)

where $c$ is the speed of light in the vacuum, $d_{r,u,t}$ is the distance
between RIS $r$ and the VR user at time slot $t$, $f$ is the operating
frequency, $k(f)$ is the overall molecular absorption coefficients of the
medium at THz band, available from HITRAN database [14].
The transmission rate between RIS $r$ and the VR user $u$ at time slot $t$ is
given by:

$\begin{split}c_{r,u,t}&=W\cdot\log_{2}\\\
&\left(1+\frac{P_{RIS}h_{r,n,u,t}\sum_{n=1}^{N}|e^{j(\phi_{r,n,u,t}-\psi_{r,n,u,t})}|^{2}L_{r,n,u,t}}{\mathcal{N}(d_{r,u,t},p,f)}\right)\\\
\end{split}$ (2)

where $N$ is the number of meta-surface blocks in a RIS, $W$ is the total
bandwidth, $P_{RIS}$ is the transmit power related to each RIS,
$\psi_{r,n,u,t}$ is the phase shift of meta-surface element $n$ of RIS $r$
with respect to user $u$ at time slot $t$, $\phi_{r,n,u,t}$ is the phase shift
of the channel between meta-surface element $n$ of RIS $r$ with respect to
user $u$ at time slot $t$,
$\mathcal{N}(d_{r,u,t},p,f)=N_{0}+\sum_{r=1}^{R}P_{RIS}A_{0}d_{r,u,t}^{-2}(1-e^{-K(f)d_{r,u,t}})$,
$N_{0}=\frac{W\lambda^{2}}{4\pi}k_{B}T_{0}$, $T_{0}$ is the temperature
(Kelvin), $k_{B}$ is the Bolzmann constant,
$A_{0}=\frac{c^{2}}{16\pi^{2}f^{2}}$ [15].

The obtained transmission rate can be used to calculate the service rate of a
specific VR service $s$, given by:

$C_{r,u,t,s}=\frac{c_{r,u,t}\tau_{0}}{O_{s}}$ (3)

where $\tau_{0}$ is the duration between two discrete time slots, $O_{s}$ is
the size of the object related to the service $s$, such as the size of a VR
image.

###  III-C Problem Formulation

We consider a RIS-based THz network including a set of RISs, i.e., a set of
operating RISs $\mathbf{R}=\\{r_{1},...,r_{i},...r_{R}\\}$ and each RIS with
index $i$ is assigned to a different RIS called a backup RIS, the set of
backup RISs is $\mathbf{B}=\\{b_{1},...,b_{i},...b_{R}\\}$, managed by the RIS
controller. We study the channel allocation problem regarding different RIS
components, where VR users are requesting service connections. The RIS $r_{i}$
and $b_{i}$ contain $N(i)$ meta-surface blocks that can be allocated to create
THz paths. A service request can occupy $k\in\\{1,...,K\\}$ block based on the
resource availability, where $K$ represents the maximum number of blocks a RIS
can allocate to a single service. We model the arrival and service processes
of VR service requests from a user as a Poisson process with mean rates
$\lambda_{s}$, and $\mu_{s}$, respectively, where $\mu_{s}$ can be concluded
from eq. (3) for different services.

###  III-D System States

The system state $s$ represents the number of VR service requests with
different number of allocated block $k$ in a RIS $r_{i}$, the availability of
the RIS and the next event that can happen in the system:

$\begin{split}S=\\{s|s=&(\Delta,X,e)\\},\end{split}$ (4)

where a set $\Delta=\delta^{r_{1}},...,\delta^{r_{i}},...,\delta^{r_{R}}$
collects all subsets $\delta^{r_{i}}$, which describe a state $s$ and indicate
a number of VR services requested
$\delta^{r_{i}}=\\{\delta_{1}(r_{i}),...,\delta_{k}(r_{i}),...,\delta_{K}(r_{i})\\}$.
The variable $\delta_{k}(r_{i})$ denotes the number of VR services allocated
with $k$ blocks in the main RIS $r_{i}$. A set
$X=\\{X^{r_{1}},...,X^{r_{R}}\\}$ describes the availability of RIS devices
and indicates the number of available meta-surface blocks: $X^{r_{i}}=N(i)$ if
all the elements of the RIS $r_{i}$ are available, $X^{r_{i}}=N(i)-j$ if $j$
elements are failed and $X^{r_{i}}=0$ if the all elements are failed or the
RIS hardware fails. The variable $e$ describes an event that occurs in the VR
over THz RIS network, such as $e=\\{Ar,D^{r},F^{m},Re^{m}\\}$, where a set
$Ar$ denotes the arrival of any VR service request, a set
$D^{r}=\\{D^{r_{1}},...,D^{r_{i}},...,D^{r_{R}}\\}$, and a subset
$D^{r_{i}}=\\{D^{r_{i}}_{1},...,D^{r_{i}}_{k},...,D^{r_{i}}_{K}\\}$ collects
the set of departure events of a VR service from a main RIS $r_{i}$, and
$D^{r_{i}}_{k}$ defines the departure of a VR service allocated in $k$ blocks
from a RIS $r_{i}$, a set $F^{m}=\\{F_{1}^{m},...,F_{i}^{m},...,F_{R}^{m}\\}$
and a variable $F_{i}^{m}$ define the failure process of a meta-surface block
in the RIS $r_{i}$, a set
$Re^{m}=\\{Re_{1}^{m},,...,Re_{i}^{m},...,Re_{R}^{m}\\}$ and a variable
$Re_{i}^{m}$ define the return of a path/meta-surface block in the RIS $r_{i}$
to working state after a failure.

###  III-E Actions

The system controller has several possibilities of actions a to take when it
receives a service request, whether to accept or reject it. The action space
$A(s)$ is described as follows:

$A(s)=\begin{cases}\\{0,(i,k)\\},\;&e\in Ar,\\\
&k\in\\{0,1,2,...,K\\},i\in\\{1,...,R\\}\\\ -1,&e\in\\{D^{r},Re^{m}_{i}\\}\\\
(-2,T),&e\in F^{m}_{i}\end{cases}$ (5)

where $a(s)=(i,k),\forall k\in\\{1,...,K\\}\forall i\in\\{1,...,R\\}$ when a
VR service request is accepted and $k$ blocks are allocated in RIS $r_{i}$,
$a(s)=0$ denotes the action of rejecting a service request. When a service
completes and departs the RIS system, a RIS node or meta-surface block returns
into the system after a failure, no action is required, and the controller
needs only to update the system state, we represent the action as $a(s)=-1$.
When a RIS fails, all the allocated blocks are transferred to the backup RIS,
and when a meta-surface block fails, a corresponding block will be allocated
in the same RIS if resources are available or in a backup RIS otherwise, we
denote the information update and the transfer action as $a(s)=(-2,T)$, where
T is the transfer vector from current RIS state to re-allocation state.

###  III-F Transition Probabilities

We assume that the time period between two continuous decision epoches follows
an exponential distribution and denoted as $\tau(s,a)$, given the current
state $s$ and action $a$. Thus the mean rate of events for a specific state
$s$ and action $a$ denoted as $\gamma(s,a)$, is the sum of the rates of all
events in the RIS system, which is expressed as follows:

$\begin{split}&\forall i\in\\{1,...,R\\},\forall k\in\\{1,...,K\\}:\text{
}\tau(s,a)=\gamma(s,a)^{-1}=\\\
&\begin{cases}\lambda_{s}+\Lambda^{m}+\Theta^{m}+\Theta+k\mu_{s},\;&e=Ar,a=(i,k),\\\
\lambda_{s}+\ \Lambda^{m}+\Theta^{m}+\Theta,&e=Ar,a=0,\\\
\lambda_{s}+(\Lambda^{m}-\lambda^{m})+(\Theta^{m}+\mu^{m})+\Theta,&e=Re_{i}^{m},a=-1,\\\
\lambda_{s}+\Lambda^{m}+\Theta^{m}+\Theta-k\mu_{s},&e=D_{k}^{r_{i}},a=-1,\\\
\lambda_{s}+(\Lambda^{m}+\lambda^{m})+(\Theta^{m}-\mu^{m})+\Theta,&e=F_{i}^{m},a=(-2,T),\end{cases}\end{split}$
(6)

where $\lambda_{s}$ is the arrival rate of VR service requests.
$\Lambda^{m}=\lambda^{m}\sum_{i=1}^{R}(N(i)-X^{r_{i}})$ is the arrival rate of
non available RIS blocks, and $\Theta^{m}=\mu^{m}\sum_{i=1}^{R}N(i)$ is the
failure rate of available RIS blocks.

When an arriving service request is rejected, or a RIS or a RIS block returns
to system, the total number of blocks allocated in RISs is
$\sum_{i=1}^{R}\sum_{k=1}^{K}\delta_{k}(r_{i})$, so the departure rate of a VR
service in RIS system is
$\Theta=\sum_{i=1}^{R}\sum_{k=1}^{K}k\delta_{k}(r_{i})\mu_{s}$. When a service
request is accepted and $k$ blocks are allocated, one more service is added to
the system, thus the departure rate becomes $\Theta+k\mu_{s}$. When a
departure of a VR service from a RIS $r_{i}$ allocated in $k$ blocks occurs,
the departure rate becomes $\Theta-k\mu_{s}$. When a RIS block fails, the
arrival rate and failure rate of the RIS block in the system are adjusted such
that the failed block can return in the future and cannot fail again while it
is already failed. All services admitted in the case of a failed RIS block are
transferred to a backup RIS block, so it should be accounted in the departure
rate, which ensures the system reliability, and thus the number of existing
services remains equal to $\Theta$. The transition probability in our markov
decision model from state $s$ to state $s^{\prime}$ when an action $a$ is
selected is denotes as $p(s^{\prime}|s,a)$, which can be determined under
different events.

  * •

State $s=(\Delta,X,Ar)$, and $a=0$.

$\begin{split}&p(s^{\prime}|s,a)=\begin{cases}\frac{\lambda_{s}}{\tau(s,a)}&s^{\prime}=(\Delta,X,Ar)\\\
\frac{k\delta_{k}(r_{i})\mu_{s}}{\tau(s,a)}&s^{\prime}=(\Delta,X,D_{k}^{r_{i}})\\\
\frac{\lambda^{m}}{\tau(s,a)}&s^{\prime}=(\Delta,X,Re_{i}^{m})\\\
\frac{\mu^{m}}{\tau(s,a)}&s^{\prime}=(\Delta,X,F_{i}^{m})\\\
\end{cases}\end{split}$ (7)

  * •

State $s=(\Delta,X,Ar)$, $a=(i,k)$, and $k\geq 1$.

$\begin{split}&p(s^{\prime}|s,a)=\begin{cases}\frac{\lambda_{s}}{\beta(s)\tau(s,a)}&s^{\prime}=(\widehat{\Delta},X,Ar)\\\
\frac{k(\delta_{k}(r_{i})+1)\mu_{s}}{\beta(s)\tau(s,a)}&s^{\prime}=(\widehat{\Delta},X,D_{k}^{r_{i}})\\\
\frac{k^{\prime}\delta_{k^{\prime}}(r_{i^{\prime}})\mu_{s}}{\beta(s)\tau(s,a)}&s^{\prime}=(\widehat{\Delta},X,D_{k^{\prime}}^{r_{i^{\prime}}})\\\
&k^{\prime}\neq k,i^{\prime}=i||k^{\prime}=k,i^{\prime}\neq i\\\
\frac{\lambda^{m}}{\beta(s)\tau(s,a)}&s^{\prime}=(\widehat{\Delta},X,Re_{i^{\prime}}^{m})\\\
\frac{\mu^{m}}{\beta(s)\tau(s,a)}&s^{\prime}=(\widehat{\Delta},X,F_{i^{\prime}}^{m})\\\
\end{cases}\end{split}$ (8)

where $\beta(s)=\sum_{i=1}^{R}X^{r_{i}}$ denotes the number of RIS blocks that
are available at the state $s$, and
$\widehat{\Delta}=\delta^{r_{1}},...,\delta^{r_{i}}+I_{k},...,\delta^{r_{R}}$,
$I_{k}$ denotes a vector having $K$ elements, with k-th element equal to 1 and
0 for the others.

  * •

State $s=(\Delta,X,D_{k}^{r_{i}})$, $a=-1$.

$\begin{split}&p(s^{\prime}|s,a)=\begin{cases}\frac{\lambda_{s}}{\tau(s,a)}&s^{\prime}=(\widehat{\Delta},X,Ar)\\\
\frac{k(\delta_{k}(r_{i})-1)\mu_{s}}{\tau(s,a)}&s^{\prime}=(\widehat{\Delta},X,D_{k}^{r_{i}})\\\
\frac{k^{\prime}\delta_{k^{\prime}}(r_{i^{\prime}})\mu_{s}}{\tau(s,a)}&s^{\prime}=(\widehat{\Delta},X,D_{k^{\prime}}^{r_{i^{\prime}}})\\\
&k^{\prime}\neq k,i^{\prime}=i||k^{\prime}=k,i^{\prime}\neq i\\\
\frac{\lambda^{m}}{\tau(s,a)}&s^{\prime}=(\widehat{\Delta},X,Re_{i^{\prime}}^{m})\\\
\frac{\mu^{m}}{\tau(s,a)}&s^{\prime}=(\widehat{\Delta},X,F_{i^{\prime}}^{m})\\\
\end{cases}\end{split}$ (9)

where
$\widehat{\Delta}=\delta^{r_{1}},...,\delta^{r_{i}}-I_{k},...,\delta^{r_{R}}$.

  * •

State $s=(\Delta,X,Re_{i}^{m})$, $a=-1$, where $X^{r_{i}}=N(i)-j$, and $j$ is
the number of failed RIS blocks.

$\begin{split}&p(s^{\prime}|s,a)=\begin{cases}\frac{\lambda_{s}}{\tau(s,a)}&s^{\prime}=(\Delta,\widehat{X},Ar)\\\
\frac{k\delta_{k}(r_{i^{\prime}})\mu_{s}}{\tau(s,a)}&s^{\prime}=(\Delta^{R},\widehat{X},D_{k}^{r_{i^{\prime}}})\\\
&i^{\prime}\neq i\\\
\frac{\lambda^{m}}{\tau(s,a)}&s^{\prime}=(\Delta,\widehat{X},Re_{i}^{m})\\\
\frac{\mu^{m}}{\tau(s,a)}&s^{\prime}=(\Delta,\widehat{X},F_{i}^{m})\\\
\end{cases}\end{split}$ (10)

where $\widehat{X}^{r_{i}}=N(i)-j+1$

  * •

State $s=(\Delta,X,F_{i}^{m})$, $a=(-2,T)$, where $X^{r_{i}}=N(i)-j\geq 1$,
The vector $T$ transfers one or more allocated RIS blocks from $r_{i}$ to the
available RIS.

$\begin{split}&p(s^{\prime}|s,a)=\begin{cases}\frac{\lambda_{s}}{\tau(s,a)}&s^{\prime}=(\widehat{\Delta},\widehat{X},Ar)\\\
\frac{k\delta_{k}(r_{i^{\prime}})\mu_{s}}{\tau(s,a)}&s^{\prime}=(\widehat{\Delta},\widehat{X},D_{k}^{r_{i^{\prime}}})\\\
&\text{if}\;\;X^{r_{i}}\leq k\;\;\text{then:}\;i^{\prime}\neq i\\\
\frac{\lambda^{m}}{\tau(s,a)}&s^{\prime}=(\widehat{\Delta},\widehat{X},Re_{i}^{m})\\\
&i^{\prime}\neq i\\\
\frac{\mu^{m}}{\tau(s,a)}&s^{\prime}=(\widehat{\Delta},\widehat{X},F_{i^{\prime}}^{m})\\\
&\text{if}\;\;X^{r_{i}}=1\;\;\text{then:}\;i^{\prime}\neq i\\\
\end{cases}\end{split}$ (11)

where $\widehat{X}^{r_{i}}=N(i)-j-1$, $\widehat{\Delta}=\Delta-T$, $T$ is
determined using Algorithm. 1.

Algorithm 1 Finding Service Transfer Vector

1:Input:  $s=(\Delta,X,F_{i}^{m})$

2:Initialization: $T=T^{1},...,T^{R}$,
$T^{i}=\\{T^{i}_{1},..,T^{i}_{k},..,T^{i}_{K}\\}$,

3:$T^{i}_{k}=0,\;\forall i\in\\{1,...,R\\},\forall k\in\\{1,...,K\\}$.

4:if $\widehat{X}^{r_{i}}=0$ then $k=1$

5: while $\delta_{k}(r_{i})=0$ do

6: $k=k+1$

7: end while

8: $T^{i}_{k}=-1$, $T^{b_{i}}_{k}=1$

9:end if

10:Return $T$

###  III-G Rewards

Given the system state $s$ and the corresponding action $a$, the system reward
of the VR over THz RIS system is denoted by

$r(s,a)=w(s,a)-g(s,a)$ (12)

where $w(s,a)$ is the net lump sum incomes of VR users at the state $s$ when
action $a$ is taken and an event $e$ occurs, and $g(s,a)$ is the expected
system costs.

$\begin{split}w(s,a)=\begin{cases}R_{k}&e=Ar,a=(i,k)\\\ 0&e=Ar_{k},a=0\\\
0&e=Re_{i}^{m},a=-1\\\ 0&e=D_{k}^{r_{i}}a=-1\\\
-\varepsilon\sum_{k=1}^{K}kT_{k}^{i}&,e=F_{i}^{m}a=(-2,T)\end{cases}\end{split}$
(13)

where the variable $R_{k}=Q-\frac{Z}{k}$ denotes the reward of the RIS system
for accepting of the requested service and allocating $k$ blocks. $Q$ denotes
the income reward from VR user satisfaction, $\frac{Z}{k}$ denotes the
transmission cost of occupying $k$ blocks. The constant $\varepsilon$ denotes
the penalty of a meta-surface block failure. When a meta-surface block fails,
a number of services are transferred to the backup RIS, and thus we consider a
penalty proportional to the number of re-allocated blocks as
$-\varepsilon\sum_{k=1}^{K}kT_{k}^{i}$. In our work, we don’t penalize
rejected services, neither reward accomplished services or returned RISs or
returned blocks.

The expected system cost $g(s,a)$ is defined as:

$g(s,a)=c(s,a)\cdot\tau(s,a)$ (14)

where $\tau(s,a)$ is the expected service time defined by eq. (6) from the
state $s$ to the next state in case that action $a$ is chosen and $c(s,a)$ is
the service holding cost rate when the RIS system is in state $s$ in case that
action $a$ is selected. Furthermore, $c(s,a)$ can be described by the number
of occupied blocks in the RIS system, as follows:

$c(s,a)=\sum_{i=1}^{R}\sum_{k=1}^{K}c\cdot k\cdot\delta_{k}^{r_{i}}$ (15)

where $c$ represents the utilization cost of a block unit.

##  IV SMDP-based Channel Allocation Model

In this section, we develop an SMDP-based path allocation model to study the
performance of a RIS system considering the unreliability of RIS devices. We
aim to take optimal decisions at every decision epochs; arrival of new service
request, departure of a service, failure of a RIS, failure of a meta-surface,
return of a failed meta-surface block, where our goal is to maximize the long-
term expected system rewards. The expected discounted reward is given based on
the model in [5] as follows:

$\begin{split}r(s,a)=&w(s,a)-c(s,a)\cdot E_{s}^{a}\\{\int_{0}^{\tau}e^{-\alpha
t}dt\\}\\\ =&w(s,a)-c(s,a)\cdot
E_{s}^{a}\\{\frac{1-e^{-\alpha\tau}}{\alpha}\\}\\\
=&w(s,a)-\frac{c(s,a)}{\alpha+\tau(s,a)}\end{split}$ (16)

where $\alpha$ is a continuous-time discount factor.

Using the defined transition probabilities eq. (7), (8), (9), (10),(11), we
can obtain the maximum long-term discounted reward using a discounted reward
model defined in [5] as

$\nu(s)=\max_{a\in A(s)}\left\\{r(s,a)+\lambda\sum_{s^{\prime}\in
S}p(s^{\prime}|s,a)\nu(s^{\prime})\right\\}$ (17)

where $\lambda=\tau(s,a)/(\alpha+\tau(s,a))$. In the SMDP model, the value of
$\nu(s)$ in a strategy $\psi$ is computed based on the value $\nu(s^{\prime})$
obtained in the strategy $\psi-1$, and as an initial value, the discounted
reward can be set to zero for all states to initialize the computation, which
will converge afterwards to the optimal solution.
To simplify the computation of the reward, let $\rho$ be a finite constant,
where
$\rho=\lambda_{s}+\lambda^{m}\prod_{i=1}^{R}N(i)+\mu^{m}\prod_{i=1}^{R}N(i)+\mu_{s}\sum_{i=1}^{R}N(i)<\infty$.
We define $\overline{p}(s^{\prime}|s,a)$, $\overline{\nu}(s)$, and
$\overline{r}(s,a)$ as the uniformed transition probability, long-term reward,
and reward function, respectively, and given by:

$\overline{r}(s,a)=r(s,a)\frac{\tau(s,a)+\alpha}{\rho+\alpha},\overline{\lambda}=\frac{\rho}{\rho+\alpha}$
(18)
$\begin{split}\overline{p}(s^{\prime}|s,a)=\begin{cases}1-\frac{[1-p(s^{\prime}|s,a)]\tau(s,a)}{\rho}&s^{\prime}=s\\\
\frac{p(s^{\prime}|s,a)\tau(s,a)}{\rho}&s^{\prime}\neq s\\\
\end{cases}\end{split}$ (19)

After uniformization, the optimal reward is given by:

$\overline{\nu}(s)=\max_{a\in
A(s)}\left\\{\overline{r}(s,a)+\overline{\lambda}\sum_{s^{\prime}\in
S}\overline{p}(s^{\prime}|s,a)\overline{\nu}(s^{\prime})\right\\}$ (20)

In order to solve our SMDP-based path Allocation (PA) model, we consider an
iterative algorithm described as follows:

Algorithm 2 Iterative SMDP-PA Algorithm

1:Step 1 (Initialization): $\overline{\nu}^{0}(s)=0$, for all $s\in S$. Set
the value of $\epsilon>0$, and iteration $t=0$.

2:Step 2: Using eq. 20, compute the discounted reward for each state $s$:
$\overline{\nu}^{t+1}(s)=\max_{a\in
A(s)}\left\\{\overline{r}(s,a)+\overline{\lambda}\sum_{s^{\prime}\in
S}\overline{p}(s^{\prime}|s,a)\overline{\nu}^{t}(s^{\prime})\right\\}$

3:Step 3:

4:if $\|\overline{\nu}^{t+1}-\overline{\nu}^{t}\|>\epsilon$ then
$t\longleftarrow t+1$, go to Step 2

5:else go to Step 4

6:end if

7:Step 4: Compute the optimal policy for all $s\in S$
$d_{\epsilon}^{*}(s)\in\text{arg}\max_{a\in
A(s)}\left\\{\overline{r}(s,a)+\overline{\lambda}\sum_{s^{\prime}\in
S}\overline{p}(s^{\prime}|s,a)\overline{\nu}^{t+1}(s^{\prime})\right\\}$

After obtaining the optimal policy from Algorithm 2, the steady states
probabilities are computed using the following system of equations:

$\begin{split}\pi(P-J)=0,\sum_{s\in S}\pi(s)=1\end{split}$ (21)

where $\pi(s)$ represents the steady state probability at state $s$, $P$ is
the transition probabilities matrix, considering the optimal policy
$d_{\epsilon}^{*}$, and $J$ denotes the all-ones matrix.

##  V Numerical results

In this section, we validate and evaluate the proposed SMDP-based
unreliability-aware path allocation for VR over THz RIS system using a Python
simulator to implement the model and the algorithms proposed. The parameters
used for simulation are summarized as follows: $R=1-3$, $K=1-2$, $c=1$,
$\epsilon=100$, $Q=150$, $Z=100$,$\alpha=0.1$, $\lambda_{s}=1-10$,
$\mu_{s}=5$. To investigate the performance of the RIS system under different
system settings, the simulation results present a function of the service
arrival rate, service departure rate, RIS blocks failure rate, RIS blocks
return rate. We define 4 scenarios with following settings: scenario 1) the
RIS network is operating using a two RISs: a main RIS with a single backup RIS
($R=1$) containing $5$ meta-surfaces ($N(1)=5$), and allowing users to
allocate only one block for each VR service ($K=1$); scenario 2) the RIS
network is operating using two main RIS with two backup RISs ($R=2$), similar
to scenario 1, $K=1$; scenario 3) the RIS network is operating with three main
RISs and three backup RISs ($R=3$), the system allows the allocation of two
blocks at maximum for a single VR user request ($K=2$), where each RIS
contains 5 blocks ($N(r_{i})=5,\forall i\in[1,2,3]$); and scenario 4) the RIS
network is operating with three main RISs and three backup RISs ($R=3$), the
system allows the allocation of two blocks at maximum for a single VR user
request ($K=2$), whereby the amount of blocks in RISs was set to
$N(r_{1})=4,N(r_{2})=3,N(r_{3})=2$. Similar to [11], the discount factor
$\alpha$ is 0.1.

(a) Action probabilities (b) Average system reward

(c) Blocking probabilities

Figure 2: Results with different RIS failure rates($\lambda_{s}=1$)

Fig. 2.a) shows the acceptance probability as a function of the RIS block
failure rate under different scenarios defined above. Here, we set
$\lambda_{s}=1$. As expected, the acceptance probability of a service
decreases with increasing failure rate of RIS blocks. The decrease of the
acceptance probability can be explained with the increasing request blocking
due to the capacity of the RIS system reduced by failed RIS blocks. The
highest acceptance probability of around $68\%$ could be reached in scenario 3
with 3 RISs and low RIS block failure rate. This can be explained by the fact
that the high RIS blocks/paths availability with 4 RISs and 4 backup RISs,
where hardware failure is managed by the backup RISs. The RIS system
configured based on the scenario 1 and 2 show the highest acceptance
probability for the higher RIS blocks failure rate starting from $\mu^{m}=0.1$
and decreases from 45 % to 30%. The RIS system in scenario 4 shows the lowest
service acceptance probability up to 37 %, as the RIS system can not always
satisfy the amount of VR user requests with the limited amount of RISs and
additional RIS failures.

Next we investigate the average system reward as a function of different
arrival rates of service requests and different RIS block failure rates. Fig.
3 illustrates that the highest and the lowest average reward could be provided
in scenario 1, and in scenarios 4 and 3 with $\lambda_{s}>9$, respectively. In
general, the average reward decreases with increasing arrival rate of service
requests, which is a result of the limited capacity of RIS system.
Additionally, in scenarios 3 and 4, the service requests can be blocked, when
available RIS do not provide enough meta-surfaces/channels for the requested
service. When the service arrival rate increases, the overall capacity needed
to provide all service requests is higher than the RIS capacity. As a result,
the system rejects any new incoming service requests, which decreases the
average reward value. The average reward is a good metric for future work to
compare an optimal path allocation policy with heuristic or machine learning
based allocation algorithms.

Fig. 2.b) shows an average reward as a function of the RIS block failure rate.
In our settings we highly penalize the RIS block failure, which explains the
drastic decrease of the average reward, since the probability of accepting
services becomes lower, and where we increased the number of RIS. In Fig. 2.b)
the average reward follows a convex decreasing function in terms of RIS block
failure rates, with service arrival rate $\lambda_{s}$ equal to $1$. The
figure shows that with low failure rate the reward is the same under all
scenarios, and then it becomes the worst with scenarios that have more RIS.
The minimum reward for scenario 1 is 0, which means that the single RIS has
failed and no service is accepted, while for scenario 3, the system can have
failed RIS and still accepts service which will have a high probability to be
lost in the case of failure, causing a negative reward value.

Figure 3: Average system reward with different arrival rates of services.
Figure 4: Blocking probabilities with different arrival rates of services.

Finally we illustrate in Fig. 4-2.c) the blocking probabilities with different
arrival rates of services and with different RIS failure rates under different
scenarios. We vary the service arrival rate and $\lambda_{s}=1$ when varying
the RIS block failure rate. The blocking probability is very low with low
arrival rates, less than $0.001$. It increases sharply after reaching the
value $\lambda_{s}=5$, in scenario 1, due to the lack of blocks to allocate of
a single RIS system and reaches the value $0.31$ when $\lambda_{s}=10$. For
high service arrival rate, the more we increase the number of RISs the more
stable our system gets. However, for low and medium arrival rates, scenario 1
with less RISs performs better than scenario 4 with 3 RISs, thus increasing
the number of RISs and meta-surface blocks does not always improve the
performance in terms of service blocking and long-term reward. In Fig. 2.c),
we fix the service arrival rate to 1 and we vary the RIS blocks failure rate,
we remark that the blocking probability is equal to 0 all values under
$\mu^{m}=0.1$ which shows the stability of our channel allocation algorithm.
For $\mu^{m}=0.5$, the blocking increases then to reach a maximum of $0.14$,
$0.03$ and $0.01$ for scenarios 1, 2 and 3, respectively. We see that
increasing the number of RISs and meta-surface blocks highly improves the
performance of RIS network in terms of service blocking.

##  VI Conclusion

We considered path allocation in the virtual reality (VR) applications over
RIS network with controlled access of VR users request by Semi-Markov decision
Process (SMDP). We introduced an optimal path allocation scheme to ensure the
reliability and maximize the system reward in a set of RISs, in which a RIS
device and its meta-surface elements are vulnerable to failures. We formulated
the problem as an SMDP model considering multiple RIS devices in an indoor
environment used to provide services to VR users. Numerical results showed the
average reward and blocking probability with various service arrival and RIS
block failure rates, and under different network configurations. The system
computed corresponding policies to each service arrival rate to ensure the
reliability and maximize long-term rewards. We showed that the proposed scheme
was generally applicable, dynamic and provided an efficient solution to the
path allocation problem. We showed that increasing the number of RISs and
meta-surface blocks does not always improve the performance in terms of
service blocking and long-term reward, for low and medium service arrival
rate. Such finding allows us to better dimensioning RIS networks based on the
expected service rate, in order to improve costs and performance at the same
time. In our future work, a large-scale solution based on reinforcement
learning can be proposed to solve value iteration algorithm, which is known by
its exponential growth.

## Acknowledgment

This work was partially supported by the DFG Project Nr. JU2757/12-1, and by
the Federal Ministry of Education and Research of Germany, joint project
6GRIC, 16KISK031.

## References

  * [1] W. Saad, M. Bennis, and M. Chen, “A vision of 6g wireless systems: Applications, trends, technologies, and open research problems,” _IEEE network_ , vol. 34, no. 3, pp. 134–142, 2019.
  * [2] M. Bensalem and A. Jukan, “Benchmarking machine learning techniques for thz channel estimation problems,” _arXiv preprint arXiv:2104.08122_ , 2021.
  * [3] Q. Wu, S. Zhang, B. Zheng, C. You, and R. Zhang, “Intelligent reflecting surface-aided wireless communications: A tutorial,” _IEEE Transactions on Communications_ , vol. 69, no. 5, pp. 3313–3351, 2021.
  * [4] X. Y. Li and M. S. Tong, “Array failure diagnosis and active compensation for intelligent reflecting surfaces,” in _2021 IEEE International Symposium on Antennas and Propagation and USNC-URSI Radio Science Meeting (APS/URSI)_. IEEE, 2021, pp. 1769–1770.
  * [5] M. L. Puterman, _Markov decision processes: discrete stochastic dynamic programming_. John Wiley & Sons, 2014\.
  * [6] M. Chen, W. Saad, and C. Yin, “Virtual reality over wireless networks: Quality-of-service model and learning-based resource management,” _IEEE Transactions on Communications_ , vol. 66, no. 11, pp. 5621–5635, 2018.
  * [7] C. Chaccour, M. N. Soorki, W. Saad, M. Bennis, and P. Popovski, “Risk-based optimization of virtual reality over terahertz reconfigurable intelligent surfaces,” in _ICC 2020-2020 IEEE International Conference on Communications (ICC)_. IEEE, 2020, pp. 1–6.
  * [8] K. Wang, C.-T. Lam, and B. K. Ng, “Doppler effect mitigation using reconfigurable intelligent surfaces with hardware impairments,” in _2021 IEEE Globecom Workshops (GC Wkshps)_. IEEE, 2021, pp. 1–6.
  * [9] A. Zappone, M. Di Renzo, X. Xi, and M. Debbah, “On the optimal number of reflecting elements for reconfigurable intelligent surfaces,” _IEEE Wireless Communications Letters_ , vol. 10, no. 3, pp. 464–468, 2020.
  * [10] C. e. a. Huang, “Holographic mimo surfaces for 6g wireless networks: Opportunities, challenges, and trends,” _IEEE Wireless Communications_ , vol. 27, no. 5, pp. 118–125, 2020.
  * [11] M. Li, L. Zhao, and H. Liang, “An smdp-based prioritized channel allocation scheme in cognitive enabled vehicular ad hoc networks,” _IEEE Transactions on Vehicular Technology_ , vol. 66, no. 9, pp. 7925–7933, 2017.
  * [12] R. Li and P. Zhu, “Spectrum allocation strategies based on qos in cognitive vehicle networks,” _IEEE Access_ , vol. 8, pp. 99 922–99 933, 2020.
  * [13] C. Huang, A. Zappone, G. C. Alexandropoulos, M. Debbah, and C. Yuen, “Reconfigurable intelligent surfaces for energy efficiency in wireless communication,” _IEEE Transactions on Wireless Communications_ , vol. 18, no. 8, pp. 4157–4170, 2019.
  * [14] L. S. Rothman, I. E. Gordon, A. Barbe, D. C. Benner, P. F. Bernath, M. Birk, V. Boudon, L. R. Brown, A. Campargue, J.-P. Champion _et al._ , “The hitran 2008 molecular spectroscopic database,” _Journal of Quantitative Spectroscopy and Radiative Transfer_ , vol. 110, no. 9-10, pp. 533–572, 2009.
  * [15] J. M. Jornet and I. F. Akyildiz, “Channel modeling and capacity analysis for electromagnetic wireless nanonetworks in the terahertz band,” _IEEE Transactions on Wireless Communications_ , vol. 10, no. 10, pp. 3211–3221, 2011\.


# Relationship of Two Discrete Dynamical Models: One-dimensional Cellular
Automata and Integral Value Transformations

Sreeya Ghosh<EMAIL_ADDRESS>Sudhakar Sahoo<EMAIL_ADDRESS>Sk.
Sarif Hassan<EMAIL_ADDRESS>Jayanta Kumar Das<EMAIL_ADDRESS>Pabitra Pal Choudhury<EMAIL_ADDRESS>Department of Applied Mathematics,
University of Calcutta, Kolkata-700009, India  Applied Statistics Unit, Indian
Statistical Institute, Kolkata-108 , India  Institute of Mathematics and
Applications, Bhubaneshwar-751029, India  Dept. of Mathematics, Pingla Thana
Mahavidyalaya, Paschim Medinipur-721140, India  School of Medicine, Johns
Hopkins University, MD-21210, USA

###### Abstract

Cellular Automaton(CA) and an Integral Value Transformation(IVT) are two well
established mathematical models which evolve in discrete time steps.
Theoretically, studies on CA suggest that CA is capable of producing a great
variety of evolution patterns. However computation of non-linear CA or higher
dimensional CA maybe complex, whereas IVTs can be manipulated easily.
The main purpose of this paper is to study the link between a transition
function of a one-dimensional CA and IVTs. Mathematically, we have also
established the algebraic structures of a set of transition functions of a
one-dimensional CA as well as that of a set of IVTs using binary operations.
Also DNA sequence evolution has been modeled using IVTs.

###### keywords:

Cellular Automaton , Integral Value Transformations

##  1 Introduction

Cellular Automaton(pl. cellular automata, abbrev. CA) is a discrete model
which has applications in computer science, mathematics, physics, complexity
science, theoretical biology and microstructure modeling. This model was
introduced by J.von Neumann and S.Ulam in 1940 for designing self replicating
systems [1, 2, 3].

A CA consists of a finite/countably infinite number of finite-state semi-
automata [4, 5] known as ‘cells’ arranged in an ordered $n$-dimensional grid.
Each cell receives input from the neighbouring cells and changes according to
the transition function. The transitions at each of the cells together induces
a change of the grid pattern. The simplest CA is a CA where the grid is a one-
dimensional line. Stephen Wolfram’s work in the 1980s contributed to a
systematic study of one-dimensional CA, providing the first qualitative
classification of their behaviour [6]. CA has been studied for solving many
interesting problems on utilizing mathematical bases such as polynomial,
matrix algebra, Boolean derivative etc.[7, 8]. Further, dynamic behaviour of
CA can also be studied using various mathematical tools [9, 10, 11, 12], that
help to understand the crucial properties and modeling of various classes of
discrete dynamical system [12].

An Integral Value Transformation (abbrev. IVT), a class of discrete dynamical
system, were first introduced during 2009-10 ([13]). A IVT of $k$-dimension is
a function defined using $p$-adic numbers over $\mathbb{N}_{0}^{k}$ where
$\mathbb{N}_{0}=\mathbb{N}\cup\\{0\\}$, $p\in\mathbb{N}$. The IVTs have been
studied in different viewpoints including the understanding of the evolution
of integer sequences and behavioral patterns of integers in discrete time
points [14, 15].

In this paper, Wolfram code of an elementary CA and global transition function
of a one-dimensional CA has been represented through IVTs. The algebraic
structure of a set of transition functions of a one-dimensional CA as well as
the algebraic structure of a set of IVTs under some binary operations have
been studied. In the last section, some specific applications have been
discussed in which we have seen certain novelty lies in IVTs over one-
dimensional CA.

##  2 Mathematical preliminaries

######  Definition 1.

Let $Q$ be a finite set of memory elements also called the state set.
A global configuration is a mapping from the group of integers ${\mathbb{Z}}$
to the set $Q$ given by $C:{\mathbb{Z}}\rightarrow Q$. The set
$Q^{\mathbb{Z}}$ is the set of all global configurations where
$Q^{\mathbb{Z}}=\\{C|C:{\mathbb{Z}}\rightarrow Q\\}$.

######  Definition 2.

A mapping $\tau:Q^{\mathbb{Z}}\rightarrow Q^{\mathbb{Z}}$ is called a global
transition function.
A CA(denoted by $\mathcal{C}_{\tau}^{Q}$)(reported in [16, 17]) is a triplet
$(Q,Q^{\mathbb{Z}},\tau)$, where,

  * 1.

$Q$ is the finite state set

  * 2.

$Q^{\mathbb{Z}}$ is the set of all configurations

  * 3.

$\tau$ is the global transition function

######  Definition 3.

The set $\mathscr{Q}^{\mathbb{Z}}=\\{\tau|\tau:Q^{\mathbb{Z}}\rightarrow
Q^{\mathbb{Z}}\\}$ is the set of all possible global transition functions of
CA having state set $Q$.

A mapping $\tau$ is invertible if $\forall C_{i},C_{j}\in Q^{\mathbb{Z}}$,
$\exists\tau^{-1}$ such that

$\tau(C_{i})=C_{j}\Leftrightarrow\tau^{-1}(C_{j})=C_{i}$

######  Definition 4.

For $i\in{\mathbb{Z}},r\in{\mathbb{N}}$, let
$S_{i}=\\{i-r,...,i-1,i,i+1,...,i+r\\}\subseteq{\mathbb{Z}}$. $S_{i}$ is the
neighbourhood of the $i^{th}$ cell, $r$ is the radius of the neighbourhood of
a cell. It follows that ${\mathbb{Z}}=\bigcup_{i}S_{i}$.
A restriction from ${\mathbb{Z}}$ to $S_{i}$ induces a restriction of $C$ to
$\overline{c_{i}}$ given by $\overline{c_{i}}:S_{i}\rightarrow Q$; where
$\overline{c_{i}}$ may be called local configuration of the $i^{th}$ cell.
The mapping $\mu_{i}:Q^{S_{i}}\rightarrow Q$ is known as a local transition
function for the $i^{th}$ cell having radius $r$. Thus $\forall
i\in{\mathbb{Z}},\mu_{i}(\overline{c_{i}})\in Q$ and it follows that,

$\tau(C)=\tau(...,c_{i-1},c_{i},c_{i+1},...)=.....\mu_{i-1}(\overline{c_{i-1}}).\mu_{i}(\overline{c_{i}}).\mu_{i+1}(\overline{c_{i+1}}).......$

######  Definition 5.

The set $M=\\{\mu_{i}|\mu_{i}:Q^{S_{i}}\rightarrow Q,i\in\mathbb{Z}\\}$ is the
set of all possible local transition functions of CA having state set $Q$.

######  Definition 6.

If for a particular CA, $|Q|=2$ so that we can write $Q=\\{0,1\\}$, then the
CA is said to be a binary CA or a Boolean CA. A Boolean CA having radius $1$
is known as an Elementary CA(ECA).

######  Definition 7.

Wolfram code is a naming system often used for a one-dimensional CA introduced
by Stephen Wolfram (see[6]).
For a one-dimensional CA with $Q$ states, the local rule $\mu_{i}$ for some
$i^{th}$ cell, $i\in{\mathbb{Z}}$ of radius $r$(neighbourhood $2r+1$) can be
specified by an $Q^{2r+1}$-bit sequence. The decimal equivalent form of this
sequence is known as the Wolfram code.

Thus, the Wolfram code for a particular rule is a number in the range from $0$
to $Q^{Q^{2r+1}}-1$, converted from $Q$-ary to decimal notation.

######  Example 2.1.

Let the local rule of an ECA for some $i^{th}$ cell, $i\in{\mathbb{Z}}$ be,

$\mu_{i}(\overline{c_{i}})=\mu_{i}(c_{i-1},c_{i},c_{i+1})=(c_{i-1}\vee
c_{i+1})\wedge c_{i}$

where ${}^{\prime}\vee^{\prime}$ stands for OR operation,
${}^{\prime}\wedge^{\prime}$ stands for AND operation, $c_{j}$ is the $j^{th}$
cell configuration for $j=i-1,i,i+1$.
Then we get the $2^{3}$-bit sequence as,

$\mu(111)\mu(110)\mu(101)\mu(100)\mu(011)\mu(010)\mu(001)\mu(000)~{}~{}=~{}~{}1~{}1~{}0~{}0~{}1~{}0~{}0~{}0$

The decimal equivalent number for $11001000$ is $200$ and so the Wolfram code
is RULE 200.

######  Definition 8.

A $p$-adic $k-$dimensional Integral Value Transformation(IVT) denoted by
$IVT_{j}^{p,k}$ for $p\in\mathbb{N}$, $k\in\mathbb{N}$ is a function of
$p$-base numbers from $\mathbb{N}_{0}^{k}$ to $\mathbb{N}_{0}$ defined(in
[18]) as

$IVT_{j}^{p,k}(n_{1},n_{2},...,n_{k})=(f_{j}(a_{0}^{n_{1}},...,a_{0}^{n_{k}})f_{j}(a_{1}^{n_{1}},...,a_{1}^{n_{k}})...f_{j}(a_{l-1}^{n_{1}},...,a_{l-1}^{n_{k}}))_{p}=m$

where $\mathbb{N}_{0}=\mathbb{N}\cup\\{0\\}$, $p\in\mathbb{N}$,
$n_{s}=(a_{0}^{n_{s}}a_{1}^{n_{s}}...a_{l-1}^{n_{s}})_{p}$ for $s=1,2,...,k$.
$f_{j}$ is a function from $\\{0,1,...,p-1\\}^{k}$ to $\\{0,1,...,p-1\\}$ for
$j=0,1,...,p^{p^{k}}-1$,
$m$ is the decimal conversion of the $p$-base number.

######  Remark 2.1.

In particular(discussed in [19, 20, 21, 22]), if $\forall i=0,1,...,l-1$, the
function $f_{j}$ be defined as

  1. 1.

$f_{j}(a_{i}^{n_{1}},...,a_{i}^{n_{k}})=\lfloor{(a_{i}^{n_{1}}+...+a_{i}^{n_{k}})/p}\rfloor$,
then $IVT_{j}^{p,k}$ is known as a Modified Carry Value Transformation(MCVT).
Again, $MCVT$ with a $0$ padding at the right end is known as a Carry Value
Transformation(CVT).

  2. 2.

$f_{j}(a_{i}^{n_{1}},...,a_{i}^{n_{k}})=(a_{i}^{n_{1}}+...+a_{i}^{n_{k}})~{}mod~{}p$,
then $IVT_{j}^{p,k}$ is known as an Exclusive OR Transformation(XORT).

  3. 3.

$f_{j}(a_{i}^{n_{1}},...,a_{i}^{n_{k}})=max{(a_{i}^{n_{1}},...,a_{i}^{n_{k}})}$,
then $IVT_{j}^{p,k}$ is known as an Extreme Value Transformation(EVT).

##  3 Wolfram code of an ECA and IVT

For an ECA, Wolfram code for a local rule $\mu$ is the decimal number
$j\in\\{0,1,2,...,255\\}$ obtained from the $8$-bit sequence

$\mu(111)\mu(110)\mu(101)\mu(100)\mu(011)\mu(010)\mu(001)\mu(000)=j$

Therefore, Wolfram code for each local transition function of a
$3$-neighbourhood Boolean CA can be represented by a $2$ base $3$-dimensional
IVT.
The function $\mu$ in the above $8$-bit sequence can be represented by a
function $f_{j}:\\{0,1\\}^{3}\rightarrow\\{0,1\\}$ which gives

$(f_{j}(111)f_{j}(110)f_{j}(101)f_{j}(100)f_{j}(011)f_{j}(010)f_{j}(001)f_{j}(000))_{2}$
$=IVT_{j}^{2,3}(11110000_{2},11001100_{2},10101010_{2})=IVT_{j}^{2,3}(240_{10},204_{10},170_{10})$

Hence it follows that for a $3-$neighbourhood Boolean CA, any Wolfram code
$j\in\\{0,1,2,...255\\}$ can be equivalently represented by
$IVT_{j}^{2,3}(240_{10},204_{10},170_{10})$.

######  Example 3.1.

Wolfram code 200 can be equivalently represented as

$200_{10}=(11001000)_{2}=IVT_{200}^{2,3}(240_{10},204_{10},170_{10})$

However the following example shows that for $j\in\\{0,1,2,...255\\}$, any
$IVT_{j}^{2,3}$ may not correspond to a Wolfram code.

######  Example 3.2.

$IVT_{j}^{2,3}(240_{10},204_{10},171_{10})=IVT_{j}^{2,3}(11110000_{2},11001100_{2},10101011_{2})$
$=(f_{j}(111)f_{j}(110)f_{j}(101)f_{j}(100)f_{j}(011)f_{j}(010)f_{j}(001)f_{j}(001))_{2}$

In this $8$-bit sequence, $f_{j}(000)$ is missing and so this cannot
correspond to any Wolfram code.

###  3.1 Some Particular Wolfram codes and Particular IVTs

We know that transformations such as MCVT, XORT, EVT are particular cases of
IVTs. Again, any Wolfram code can be represented by an IVT. Therefore some
particular Wolfram codes which can be represented by an MCVT, XORT or EVT are
as follows.

  1. 1.

Let the local rule of an ECA for some $i^{th}$ cell, $i\in{\mathbb{Z}}$ be,

$\mu_{i}(\overline{c_{i}})=\mu_{i}(c_{i-1},c_{i},c_{i+1})=(c_{i-1}\wedge
c_{i})\vee((c_{i-1}\vee c_{i})\wedge c_{i+1})$

Then we get the $2^{3}$-bit sequence as $11101000$ and Wolfram code $232$.
Here, $\mu_{i}$ can be represented by function
$f_{j}:\\{0,1\\}^{3}\rightarrow\\{0,1\\}$ given by

$f_{j}(c_{i-1},c_{i},c_{i+1})=(c_{i-1}\wedge c_{i})\vee((c_{i-1}\vee
c_{i})\wedge c_{i+1})=\lfloor{(c_{i-1}+c_{i}+c_{i+1})/2}\rfloor$

Thus, Wolfram code $232$ can be represented as

$(f_{232}(111)f_{232}(110)f_{232}(101)f_{232}(100)f_{232}(011)f_{232}(010)f_{232}(001)f_{232}(000))_{2}$
$=(\lfloor{3/2}\rfloor\lfloor{2/2}\rfloor\lfloor{2/2}\rfloor\lfloor{1/2}\rfloor\lfloor{2/2}\rfloor\lfloor{1/2}\rfloor\lfloor{1/2}\rfloor\lfloor{0/2}\rfloor)_{2}$
$=MCVT_{232}^{2,3}(11110000_{2},11001100_{2},10101010_{2})=MCVT_{232}^{2,3}(240_{10},204_{10},170_{10})$

  2. 2.

Let the local rule of an ECA for some $i^{th}$ cell, $i\in{\mathbb{Z}}$ be,

$\mu_{i}(\overline{c_{i}})=\mu_{i}(c_{i-1},c_{i},c_{i+1})=(c_{i-1}\underline{\vee}c_{i}\underline{\vee}c_{i+1})$

Then we get the $2^{3}$-bit sequence as $10010110$ and Wolfram code $150$.
Here, $\mu_{i}$ can be represented by function
$f_{j}:\\{0,1\\}^{3}\rightarrow\\{0,1\\}$ given by

$f_{j}(c_{i-1},c_{i},c_{i+1})=(c_{i-1}\underline{\vee}c_{i}\underline{\vee}c_{i+1})=(c_{i-1}+c_{i}+c_{i+1})~{}mod~{}2$

Thus, Wolfram code $150$ can be represented as

$(f_{150}(111)f_{150}(110)f_{150}(101)f_{150}(100)f_{150}(011)f_{150}(010)f_{150}(001)f_{150}(000))_{2}$
$=((3mod2)(2mod2)(2mod2)(1mod2)(2mod2)(1mod2)(1mod2)(0mod2))_{2}$
$=XORT_{150}^{2,3}(11110000_{2},11001100_{2},10101010_{2})=XORT_{150}^{2,3}(240_{10},204_{10},170_{10})$

  3. 3.

Let the local rule of an ECA for some $i^{th}$ cell, $i\in{\mathbb{Z}}$ be,

$\mu_{i}(\overline{c_{i}})=\mu_{i}(c_{i-1},c_{i},c_{i+1})=(c_{i-1}\vee
c_{i}\vee c_{i+1})$

Then we get the $2^{3}$-bit sequence as $11111110$ and Wolfram code $254$.
Here, $\mu_{i}$ can be represented by function
$f_{j}:\\{0,1\\}^{3}\rightarrow\\{0,1\\}$ given by

$f_{j}(c_{i-1},c_{i},c_{i+1})=(c_{i-1}\vee c_{i}\vee
c_{i+1})=max\\{c_{i-1},c_{i},c_{i+1}\\}$

Thus, Wolfram code $254$ can be represented as

$(f_{254}(111)f_{254}(110)f_{254}(101)f_{254}(100)f_{254}(011)f_{254}(010)f_{254}(001)f_{254}(000))_{2}$
$=(11111110)_{2}$
$=EVT_{254}^{2,3}(11110000_{2},11001100_{2},10101010_{2})=EVT_{254}^{2,3}(240_{10},204_{10},170_{10})$

##  4 Transition Function of a CA and IVT

######  Definition 9.

The set
$T^{p,k}=\\{IVT_{j}^{p,k}|IVT_{j}^{p,k}:\mathbb{N}_{0}^{k}\rightarrow\mathbb{N}_{0}\\}$
is the set of all $p$-base $k$-dimensional IVTs for
$p\in\mathbb{N},k\in\mathbb{N}$.

######  Definition 10.

The $v$-fold cartesian product $\underbrace{T^{p,k}\times...\times
T^{p,k}}_{v~{}times}$ for $v\in\mathbb{N}$, denoted by $\mathscr{T}^{v}$ is
given by

$\mathscr{T}^{v}=\\{(IVT_{j_{1}}^{p,k},IVT_{j_{2}}^{p,k},...,IVT_{j_{v}}^{p,k})\\}$

where $IVT_{j_{s}}^{p,k}:\mathbb{N}_{0}^{k}\rightarrow\mathbb{N}_{0}\in
T^{p,k}$, for $s=1,2,...,v(\in\mathbb{N})$

######  Definition 11.

Let a restriction on $IVT_{j}^{p,k}$ from $\mathbb{N}_{0}^{k}$ to
$Q^{k}=\\{0,1,...,p-1\\}^{k}$ for $p\in\mathbb{N}$ be denoted by
$\underline{IVT}_{j}^{p,k}$. The set
$T^{p,k}_{~{}|Q}=\\{\underline{IVT}_{j}^{p,k}|\underline{IVT}_{j}^{p,k}:Q^{k}\rightarrow
Q\\}$ is the set of all $p$-base $k$-dimensional IVTs when
$\mathbb{N}_{0}^{k}$ is restricted to the subset $Q^{k}$. Therefore for
$(\eta_{1},\eta_{2},...,\eta_{k})\in Q^{k}$ we get,

$\underline{IVT}_{j}^{p,k}(\eta_{1},\eta_{2},...,\eta_{k})=f_{j}(\eta_{1},\eta_{2},...,\eta_{k})_{p}=m\in
Q$

######  Definition 12.

The set
$\mathscr{T}^{v}_{~{}~{}|Q}=\\{(\underline{IVT}_{j_{1}}^{p,k},\underline{IVT}_{j_{2}}^{p,k},...,\underline{IVT}_{j_{v}}^{p,k})\\}$
is the $v$-fold cartesian product $\underbrace{T^{p,k}_{~{}|Q}\times...\times
T^{p,k}_{~{}|Q}}_{v~{}times}$ when $\mathbb{N}_{0}^{k}$ is restricted to
subset $Q^{k}$ where $\underline{IVT}_{j_{s}}^{p,k}:Q^{k}\rightarrow Q\in
T^{p,k}_{~{}|Q}$ for $s=1,2,...,v(\in\mathbb{N})$

Now, a local transition function of any $i^{th}$ cell of a one-dimensional CA
having $p(\in\mathbb{N})$ states and radius $r(\in\mathbb{N})$ will be of the
form

$\mu_{i}(\overline{c_{i}})=\mu_{i}(c_{i-r},...,c_{i},...,c_{i+r})=c_{i}^{*}$

where $c_{i-r},...,c_{i},...,c_{i+r},c_{i}^{*}\in\\{0,1,...,p-1\\}$.
This can be represented by some $\underline{IVT}_{j_{i}}^{p,k}$, where
$p\in\mathbb{N},k=2r+1$ and $j_{i}\in\\{0,1,2,...,(p^{p^{k}}-1)\\}$ is the
underlying Wolfram code(which is in turn equal to
$IVT_{j_{i}}^{p,k}(240_{10},204_{10},170_{10})$).
Thus $\forall i\in\mathbb{Z}$,

$\mu_{i}(\overline{c_{i}})\equiv\underline{IVT}_{j_{i}}^{p,k}(\overline{c_{i}})$

Now if $\tau$ be the global transition function of any $v(\in\mathbb{N}\geq
k)$-celled CA, then for a global configuration $C=(c_{1},c_{2},...,c_{v})$, we
get

$\tau(C)=\tau(c_{1},c_{2},...,c_{v})=\mu_{1}(\overline{c_{1}}).\mu_{2}(\overline{c_{2}})....\mu_{v}(\overline{c_{v}})$

Therefore it follows that,

$\tau(c_{1},c_{2},...,c_{v})\equiv(\underline{IVT}_{j_{1}}^{p,k}(\overline{c_{1}}),\underline{IVT}_{j_{2}}^{p,k}(\overline{c_{2}}),...,\underline{IVT}_{j_{v}}^{p,k}(\overline{c_{v}}))$

Hence for any $v$-celled ECA it follows that,

$\tau(C)\equiv(\underline{IVT}_{j_{1}}^{2,3}(\overline{c_{1}}),\underline{IVT}_{j_{2}}^{2,3}(\overline{c_{2}}),...,\underline{IVT}_{j_{v}}^{2,3}(\overline{c_{v}}))$

where $j_{1},j_{2},...,j_{v}\in\\{0,1,...,255\\}$.
Now if $\tau$ be the global transition function of a countably infinite celled
CA with cells having $k$ neighbourhood, then for any global configuration
$C=(...c_{i-1},c_{i},c_{i+1},...)$, we get

$\tau(C)=.....\mu_{i-1}(\overline{c_{i-1}}).\mu_{i}(\overline{c_{i}}).\mu_{i+1}(\overline{c_{i+1}}).......$

Therefore it follows that,

$\tau(C)\equiv(....,\underline{IVT}_{j_{i-1}}^{p,k}(\overline{c_{i-1}}),\underline{IVT}_{j_{i}}^{p,k}(\overline{c_{i}}),\underline{IVT}_{j_{i+1}}^{p,k}(\overline{c_{i+1}}),....)$

where $...j_{i-1}j_{i},j_{i+1},...\in\\{0,1,2,...,(p^{p^{k}}-1)\\}$.

######  Example 4.1.

Let the initial configuration of a CA having state set $\\{0,1,2\\}$ be
$C_{0}=(01201)_{3}$ and the transition function be given by

$\tau(01201)_{3}=\mu_{1}(101)\mu_{2}(012)\mu_{3}(120)\mu_{4}(201)\mu_{5}(010)=(02001)_{3}$

where $\mu_{1},\mu_{3},\mu_{5}$ follow Wolfram code $377$ and
$\mu_{2},\mu_{4}$ follow Wolfram code $588$ for $3$-state CA.
A local transition function can be equivalently represented by some
$\underline{IVT}_{j}^{3,3}$ and thus it follows that $\tau(01201)_{3}$ is
equivalent to

$\underline{IVT}_{377}^{3,3}(1,0,1)\underline{IVT}_{588}^{3,3}(0,1,2)\underline{IVT}_{377}^{3,3}(1,2,0)\underline{IVT}_{588}^{3,3}(2,0,1)\underline{IVT}_{377}^{3,3}(0,1,0)$

Conversely, for any $\underline{IVT}_{j}^{p,k}$ if $k$ be odd, i.e. if
$k=2r+1$ for some $r<k(\in\mathbb{N}_{0})$, then
$\underline{IVT}_{j}^{p,k}(\eta_{1},\eta_{2},...,\eta_{2r+1})$ will be
equivalent to a local transition function of the $(r+1)^{th}$ cell in a CA
with $p(\in\mathbb{N})$ states and $2r+1$ neighbourhood whose underlying
Wolfram code is $j\in\\{0,1,...,p^{p^{k}}-1\\}$, given by

$\underline{IVT}_{j}^{q,l}(\eta_{1},\eta_{2},...,\eta_{2r+1})=\underline{IVT}_{j}^{p,k}(\overline{\eta}_{r+1})\equiv\mu_{r+1}(\overline{\eta}_{r+1})$

######  Remark 4.1.

For a $p(\in\mathbb{N})$-state $k(=2r+1\in\mathbb{N})$-neighbourhood CA,
clearly $\forall\overline{c_{i}}\in Q^{S_{i}}\subseteq Q^{\mathbb{Z}}$
$\mu_{j}(\overline{c_{i}})\equiv\underline{IVT}_{j}^{p,k}(\overline{c_{i}})$
where $j\in\\{0,1,...,p^{p^{k}}-1\\}$ is the underlying Wolfram Code. It
follows that the set of local transition functions $M$ is equivalent to the
set $T^{p,k}_{~{}|Q}$ and vice-versa.
Hence a function $\phi:M\rightarrow T^{p,k}_{~{}|Q}$ defined by
$\phi(\mu_{j})(\overline{c_{i}})=\underline{IVT}_{j}^{p,k}(\overline{c_{i}})$
is an isomorphism.
Moreover, for any $v(\in\mathbb{N}\geq k)$-celled CA, having a global
configuration $C=(c_{1},c_{2},...,c_{v})$, if
$\mathscr{Q}^{v}=\\{\tau|\tau:Q^{v}\rightarrow Q^{v}\\}$, then
$\forall,\overline{c_{i}}\in Q^{k}\subseteq Q^{v},i=1,2,...,v$, it follows
that a function $\phi:\mathscr{Q}^{v}\rightarrow\mathscr{T}^{v}_{~{}|Q}$
defined by

$\phi(\tau)(c_{1},c_{2},...,c_{v})\equiv(\underline{IVT}_{j_{1}}^{p,k}(\overline{c_{1}}),\underline{IVT}_{j_{2}}^{p,k}(\overline{c_{2}}),...,\underline{IVT}_{j_{v}}^{p,k}(\overline{c_{v}}))$

is an isomorphism.

##  5 Some Algebraic Results on CA and IVT

######  Theorem 5.1.

$(\mathscr{Q}^{\mathbb{Z}},\circ)$ forms a monoid w.r.t. composition of global
transition functions.

###### Proof.

Clearly $\mathscr{Q}^{\mathbb{Z}}$ is closed and associative under composition
of global transition functions.
The transition function $\mu_{e}$ such that $\forall c_{i}\in Q$,
$\mu_{e}(\overline{c_{i}})=c_{i}$ is the local identity and it follows that
$\tau_{e}\in\mathscr{Q}^{\mathbb{Z}}$ is the global identity such that
$\forall C\in Q^{\mathbb{Z}},i\in\mathbb{Z}$,

$\tau_{e}(C)=.....\mu_{e}(\overline{c_{i-1}})\mu_{e}(\overline{c_{i}})\mu_{e}(\overline{c_{i+1}}).....=C$

Hence the theorem. ∎

######  Corollary 5.1.

$(\overline{\mathscr{Q}^{\mathbb{Z}}},\circ)$ forms a group w.r.t. composition
of global transition functions w
$\overline{\mathscr{Q}^{\mathbb{Z}}}\subseteq\mathscr{Q}^{\mathbb{Z}}$ is the
set of all invertible global transition functions of CA having state set $Q$.

###### Proof.

Since any
$\tau\in\overline{\mathscr{Q}^{\mathbb{Z}}}\subseteq\mathscr{Q}^{\mathbb{Z}}$
is invertible, the corollary holds true. ∎

######  Theorem 5.2.

$(\mathscr{T}^{v},\circ)$ forms a monoid w.r.t. composition of IVTs.

###### Proof.

The set $\mathscr{T}^{v}$, for $v\in\mathbb{N}$, is closed under composition
${}^{\prime}\circ^{\prime}$ since for any
$(IVT_{i_{1}}^{p,k},IVT_{i_{2}}^{p,k},...,IVT_{i_{v}}^{p,k}),(IVT_{j_{1}}^{p,k},IVT_{j_{2}}^{p,k},...,IVT_{j_{v}}^{p,k})\in\mathscr{T}^{v}$
and for any
$(n_{1},n_{2}...,n_{v})\in\mathbb{N}_{0}^{v}$
$\exists~{}(m_{1},m_{2},...,m_{v})\in\mathbb{N}_{0}^{v}$ such that,

$\displaystyle\left((IVT_{i_{1}}^{p,k},IVT_{i_{2}}^{p,k},...,IVT_{i_{v}}^{p,k})\circ(IVT_{j_{1}}^{p,k},IVT_{j_{2}}^{p,k},...,IVT_{j_{v}}^{p,k})\right)(n_{1},n_{2},...,n_{v})$
$\displaystyle=\left((IVT_{i_{1}}^{p,k}\circ
IVT_{j_{1}}^{p,k}),(IVT_{i_{2}}^{p,k}\circ
IVT_{j_{2}}^{p,k}),...,(IVT_{i_{v}}^{p,k}\circ
IVT_{j_{v}}^{p,k})\right)(n_{1},n_{2},...n_{v})$
$\displaystyle=\left((IVT_{i_{1}}^{p,k}\circ
IVT_{j_{1}}^{p,k})(\overline{n_{1}}),(IVT_{i_{2}}^{p,k}\circ
IVT_{j_{2}}^{p,k})(\overline{n_{2}}),...,(IVT_{i_{v}}^{p,k}\circ
IVT_{j_{v}}^{p,k})(\overline{n_{v}})\right)$
$\displaystyle=\left(IVT_{i_{1}}^{p,k}(IVT_{j_{1}}^{p,k}(\overline{n_{1}})),IVT_{i_{2}}^{p,k}(IVT_{j_{2}}^{p,k}(\overline{n_{2}})),...,IVT_{i_{v}}^{p,k}(IVT_{j_{v}}^{p,k}(\overline{n_{v}}))\right)$
$\displaystyle=IVT_{i_{1}}^{p,k}(\overline{n_{1}^{*}})IVT_{i_{2}}^{p,k}(\overline{n_{2}^{*}})...IVT_{i_{v}}^{p,k}(\overline{n_{v}^{*}})=(m_{1},m_{2},...,m_{v})_{p}$

where
$n_{s}^{*}=IVT_{j_{s}}^{p,k}(\overline{n_{s}})=IVT_{j_{s}}^{p,k}(\eta_{1}^{s},\eta_{2}^{s},...,\eta_{k}^{s})$
for $s=1,2,...,v$.
$\mathscr{T}^{v}$ is associative under ${}^{\prime}\circ^{\prime}$ since
composition of functions are associative.
Again, for $(n_{1},n_{2}...,n_{v})\in\mathbb{N}_{0}^{v}$
$\exists~{}(IVT_{e_{1}}^{p,k},IVT_{e_{2}}^{p,k},...,IVT_{e_{v}}^{p,k})\in\mathscr{T}^{v}$
such that

$(IVT_{e_{1}}^{p,k},IVT_{e_{2}}^{p,k},...,IVT_{e_{v}}^{p,k})(n_{1},n_{2},...,n_{v})$
$=IVT_{e_{1}}^{p,k}(\overline{n_{1}})IVT_{e_{2}}^{p,k}(\overline{n_{2}})...IVT_{e_{v}}^{p,k}(\overline{n_{v}})=(n_{1},n_{2},...,n_{v})$

Since $IVT_{e_{s}}^{p,k}(\overline{n_{s}})=n_{s}~{}\forall s=1,...,v,$ it
follows that $e_{1}=e_{2}=...=e_{v}=e(say)$
Thus $(IVT_{e}^{p,k},IVT_{e}^{p,k},...,IVT_{e}^{p,k})$ is the identity element
of $\mathscr{T}^{v}$
Hence the theorem. ∎

######  Definition 13.

Modular addition and multiplication of two local transition functions for a
$p(\in\mathbb{N})$-state CA are defined $\forall i\in\mathbb{Z}$ as

$(\mu^{1}_{i}\oplus_{p}\mu^{2}_{i})(\overline{c_{i}})=\mu^{1}_{i}(\overline{c_{i}})\oplus_{p}\mu^{2}_{i}(\overline{c_{i}})~{}~{}and$
$(\mu^{1}_{i}\otimes_{p}\mu^{2}_{i})(\overline{c_{i}})=\mu^{1}_{i}(\overline{c_{i}})\otimes_{p}\mu^{2}_{i}(\overline{c_{i}})$

######  Definition 14.

Modular addition and multiplication of two $p(\in\mathbb{N})$-base
$k(\in\mathbb{N})$-dimensional IVTs(see [18]) are defined
$\forall(n_{1},n_{2},...,n_{k})\in\mathbb{N}_{0}^{k}$ and
$j_{1},j_{2}\in\\{0,1,...,p^{p^{k}}-1\\}$, as

$(IVT_{j_{1}}^{p,k}\oplus_{p}IVT_{j_{2}}^{p,k})(n_{1},n_{2},...,n_{k})=IVT_{j_{1}}^{p,k}(n_{1},n_{2},...,n_{k})\oplus_{p}IVT_{j_{2}}^{p,k}(n_{1},n_{2},...,n_{k})$
$=\left(f_{j_{1}}(a_{0}^{n_{1}},...,a_{0}^{n_{k}})\oplus_{p}f_{j_{2}}(a_{0}^{n_{1}},...,a_{0}^{n_{k}})...f_{j_{1}}(a_{l-1}^{n_{1}},...,a_{l-1}^{n_{k}})\oplus_{p}f_{j_{2}}(a_{l-1}^{n_{1}},...,a_{l-1}^{n_{k}})\right)_{p}~{}~{}and,$
$(IVT_{j_{1}}^{p,k}\otimes_{p}IVT_{j_{2}}^{p,k})(n_{1},n_{2},...,n_{k})=IVT_{j_{1}}^{p,k}(n_{1},n_{2},...,n_{k})\otimes_{p}IVT_{j_{2}}^{p,k}(n_{1},n_{2},...,n_{k})$
$=\left(f_{j_{1}}(a_{0}^{n_{1}},...,a_{0}^{n_{k}})\otimes_{p}f_{j_{2}}(a_{0}^{n_{1}},...,a_{0}^{n_{k}})...f_{j_{1}}(a_{l-1}^{n_{1}},...,a_{l-1}^{n_{k}})\otimes_{p}f_{j_{2}}(a_{l-1}^{n_{1}},...,a_{l-1}^{n_{k}})\right)_{p}$

where, $n_{s}=(a_{0}^{n_{s}},a_{1}^{n_{s}}...,a_{l-1}^{n_{s}})_{p}$ for
$s=1,2,...,k$.

######  Theorem 5.3.

$(\mathscr{Q}^{\mathbb{Z}},\oplus_{p},\otimes_{p})$ forms a commutative ring
with identity under the operations $\oplus_{p}$ and $\otimes_{p}$ defined as

$(\tau_{1}\oplus_{p}\tau_{2})(C)=...(\mu^{1}_{i-1}\oplus_{p}\mu^{2}_{i-1})(\overline{c_{i-1}}).(\mu^{1}_{i}\oplus_{p}\mu^{2}_{i})(\overline{c_{i}}).(\mu^{1}_{i+1}\oplus_{p}\mu^{2}_{i+1})(\overline{c_{i+1}})...~{}and$
$(\tau_{1}\otimes_{p}\tau_{2})(C)=...(\mu^{1}_{i-1}\otimes_{p}\mu^{2}_{i-1})(\overline{c_{i-1}}).(\mu^{1}_{i}\otimes_{p}\mu^{2}_{i})(\overline{c_{i}}).(\mu^{1}_{i+1}\otimes_{p}\mu^{2}_{i+1})(\overline{c_{i+1}})...$

where $\tau_{1},\tau_{2}\in\mathscr{Q}^{\mathbb{Z}}$, $C\in Q^{\mathbb{Z}}$,
$\oplus_{p}$ denotes addition modulo $p$ and $\otimes_{p}$ denotes
multiplication modulo $p$ for $|Q|=p(\in\mathbb{N})$.

###### Proof.

In a $p(\in\mathbb{N})$-state CA, for any
$\tau_{1},\tau_{2}\in\mathscr{Q}^{\mathbb{Z}},$

$(\tau_{1}\oplus_{p}\tau_{2})(C)\in
Q^{\mathbb{Z}}~{}~{}and~{}~{}(\tau_{1}\otimes_{p}\tau_{2})(C)\in
Q^{\mathbb{Z}}$

since $\forall i\in\mathbb{Z},$

$(\mu^{1}_{i}\oplus_{p}\mu^{2}_{i})(\overline{c_{i}})\in
Q~{}~{}and~{}~{}(\mu^{1}_{i}\otimes_{p}\mu^{2}_{i})(\overline{c_{i}})\in Q$

Therefore $\mathscr{Q}^{\mathbb{Z}}$ is closed w.r.t. $\oplus_{p}$ and
$\otimes_{p}$.
Associativity follows from associativity of $\oplus_{p}$ and $\otimes_{p}$.
The local transition function $\mu_{0}$ such that $\forall c_{i}\in Q$,
$\mu_{0}(\overline{c_{i}})=0$ is the additive identity since $\forall
i\in\mathbb{Z}$

$(\mu_{0}\oplus_{p}\mu_{i})(\overline{c_{i}})=(\mu_{i}\oplus_{p}\mu_{0})(\overline{c_{i}})=\mu_{i}(\overline{c_{i}})$

It follows that $\tau_{0}\in\mathscr{Q}^{\mathbb{Z}}$ is the additive identity
such that $\forall C\in Q^{\mathbb{Z}}$,

$\tau_{0}(C)=...\mu_{0}(\overline{c_{i-1}})\mu_{0}(\overline{c_{i}})\mu_{0}(\overline{c_{i+1}})...$

The local transition function $\mu_{id}$ such that $\forall c_{i}\in Q$,
$\mu_{id}(\overline{c_{i}})=1$ is the multiplicative identity since $\forall
i\in\mathbb{Z}$

$(\mu_{id}\otimes_{p}\mu_{i})(\overline{c_{i}})=(\mu_{i}\otimes_{p}\mu_{id})(\overline{c_{i}})=\mu_{i}(\overline{c_{i}})$

It follows that $\tau_{id}\in\mathscr{Q}^{\mathbb{Z}}$ is the multiplicative
identity such that $\forall C\in Q^{\mathbb{Z}}$,

$\tau_{id}(C)=...\mu_{id}(\overline{c_{i-1}})\mu_{id}(\overline{c_{i}})\mu_{id}(\overline{c_{i+1}})...$

Now any local transition function $\mu_{i}$, is a $p^{k}$-bit sequence
$b_{1}b_{2}...b_{p^{k}}$(say), for a $p(\in\mathbb{N})$-state
$k(\in\mathbb{N})$-neighbourhood CA where $b_{1},...,b_{p^{k}}\in
Q=\\{0,1,...,p\\}$. Clearly for any $b_{s}\in Q$, $\exists b_{s}^{-1}\in Q$
such that $\forall s=1,2,...,p^{k}$, $b_{s}\oplus_{p}b_{s}^{-1}=0$.
Thus for any $\mu_{i}(\equiv b_{1}...b_{p^{k}})$, $\exists\mu_{i}^{-1}(\equiv
b_{1}^{-1}...b_{p^{k}}^{-1})$ such that $\forall c_{i}\in Q$,

$(\mu_{i}^{-1}\oplus_{p}\mu_{i})(\overline{c_{i}})=(\mu_{i}\oplus_{p}\mu_{i}^{-1})(\overline{c_{i}})=\mu_{0}(\overline{c_{i}})=0$

It follows that for any $\tau\in\mathscr{Q}^{\mathbb{Z}}$,
$\exists\tau^{-1}\in\mathscr{Q}^{\mathbb{Z}}$ such that $\forall C\in Q$,

$(\tau\oplus_{p}\tau^{-1})(C)=...(\mu_{i-1}\oplus_{p}\mu_{i-1}^{-1})(\overline{c_{i-1}})(\mu_{i}\oplus_{p}\mu_{i}^{-1})(\overline{c_{i}})(\mu_{i+1}\oplus_{p}\mu_{i+1}^{-1})(\overline{c_{i+1}})...=\tau_{0}(C),$
$(\tau^{-1}\oplus_{p}\tau)(C)=...(\mu_{i-1}^{-1}\oplus_{p}\mu_{i-1})(\overline{c_{i-1}})(\mu_{i}^{-1}\oplus_{p}\mu_{i})(\overline{c_{i}})(\mu_{i+1}^{-1}\oplus_{p}\mu_{i+1})(\overline{c_{i+1}})...=\tau_{0}(C),$

Thus for any global transition function $\tau$, its additive inverse exists in
$\mathscr{Q}^{\mathbb{Z}}$.
Commutativity follows from commutativity of $\oplus_{p}$ and $\otimes_{p}$.
Now for any local transitions $\mu_{i}^{1},\mu_{i}^{2},\mu_{i}^{3}$, $\forall
c_{i}\in Q,i\in\mathbb{Z}$ we get,

$(\mu_{i}^{1}\otimes_{p}(\mu_{i}^{2}\oplus_{p}\mu_{i}^{3}))(\overline{c_{i}})=(\mu_{i}^{1}\otimes_{p}\mu_{i}^{2})(\overline{c_{i}})\oplus_{p}(\mu_{i}^{1}\otimes_{p}\mu_{i}^{3})(\overline{c_{i}})~{}~{}and,$
$((\mu_{i}^{2}\oplus_{p}\mu_{i}^{3})\otimes_{p}\mu_{i}^{1})(\overline{c_{i}})=(\mu_{i}^{2}\otimes_{p}\mu_{i}^{1})(\overline{c_{i}})\oplus_{p}(\mu_{i}^{3}\otimes_{p}\mu_{i}^{1})(\overline{c_{i}})$

Therefore for $\tau_{1},\tau_{2},\tau_{3}\in\mathscr{(}Q)^{\mathbb{Z}}$,
$\forall C\in Q^{\mathbb{Z}}$ we get,

$(\tau_{1}\otimes_{p}(\tau_{2}\oplus_{p}\tau_{3}))(C)=(\tau_{1}\otimes_{p}\tau_{2})(C)\oplus_{p}(\tau_{1}\otimes_{p}\tau_{3})(C)~{}~{}and,$
$((\tau_{2}\oplus_{p}\tau_{3})\otimes_{p}\tau_{1})(C)=(\tau_{2}\otimes_{p}\tau_{1})(C)\oplus_{p}(\tau_{3}\otimes_{p}\tau_{1})(C)$

Hence the theorem. ∎

######  Remark 5.1.

The following example shows that
$(\mathscr{Q}^{\mathbb{Z}},\oplus_{p},\otimes_{p})$ will not form a field
under the operations $\oplus_{p}$ and $\otimes_{p}$ even if $|Q|=p$ is prime.

######  Example 5.1.

For initial configuration $C=(10001)_{2}$, let

$\tau(10001)_{2}=(\mu(110)\mu(100)\mu(000)\mu(001)\mu(011))_{2}$

Let $\mu$ follow Wolfram code $3(\neg(c_{i-1}\vee c_{i}))$.
Then
$\tau(10001)_{2}=(\mu_{3}(110)\mu_{3}(100)\mu_{3}(000)\mu_{3}(001)\mu_{3}(011))_{2}=(00110)_{2}$.
Now,
$\tau_{id}(10001)_{2}=(\mu_{id}(110)\mu_{id}(100)\mu_{id}(000)\mu_{id}(001)\mu_{id}(011))_{2}=(11111)_{2}$.
But $\nexists$ $\tau^{-1}$ such that
$(\tau\otimes_{2}\tau^{-1})(10001)_{2}=(11111)_{2}$ since $\nexists$
$\mu^{-1}$ such that for all local configurations $\mu\otimes_{2}\mu^{-1}=1$.

######  Theorem 5.4.

$(\mathscr{T}^{v},\oplus_{p},\otimes_{p})$ forms a commutative ring under the
operations $\oplus_{p}$ and $\otimes_{p}$ defined as

$\left((IVT_{i_{1}}^{p,k},IVT_{i_{2}}^{p,k},...,IVT_{i_{v}}^{p,k})\oplus_{p}(IVT_{j_{1}}^{p,k},IVT_{j_{2}}^{p,k},...,IVT_{j_{v}}^{p,k})\right)(n_{1},n_{2},...,n_{v})$
$=\left((IVT_{i_{1}}^{p,k}\oplus_{p}IVT_{j_{1}}^{p,k}),(IVT_{i_{2}}^{p,k}\oplus_{p}IVT_{j_{2}}^{p,k}),.....,(IVT_{i_{v}}^{p,k}\oplus_{p}IVT_{j_{v}}^{p,k})\right)(n_{1},n_{2},...,n_{v})$
$=\left((IVT_{i_{1}}^{p,k}\oplus_{p}IVT_{j_{1}}^{p,k})(\overline{n_{1}}),(IVT_{i_{2}}^{p,k}\oplus_{p}IVT_{j_{2}}^{p,k})(\overline{n_{2}}),.....,(IVT_{i_{v}}^{p,k}\oplus_{p}IVT_{j_{v}}^{p,k})(\overline{n_{v}})\right)$
$and,\left((IVT_{i_{1}}^{p,k},IVT_{i_{2}}^{p,k},...,IVT_{i_{v}}^{p,k})\otimes_{p}(IVT_{j_{1}}^{p,k},IVT_{j_{2}}^{p,k},...,IVT_{j_{v}}^{p,k})\right)(n_{1},n_{2},...,n_{v})$
$=\left((IVT_{i_{1}}^{p,k}\otimes_{p}IVT_{j_{1}}^{p,k}),(IVT_{i_{2}}^{p,k}\otimes_{p}IVT_{j_{2}}^{p,k}),....,(IVT_{i_{v}}^{p,k}\otimes_{p}IVT_{j_{v}}^{p,k})\right)(n_{1},n_{2},...,n_{v})$
$=\left((IVT_{i_{1}}^{p,k}\otimes_{p}IVT_{j_{1}}^{p,k})(\overline{n_{1}}),(IVT_{i_{2}}^{p,k}\otimes_{p}IVT_{j_{2}}^{p,k})(\overline{n_{2}}),....,(IVT_{i_{v}}^{p,k}\otimes_{p}IVT_{j_{v}}^{p,k})(\overline{n_{v}})\right)$

where
$i_{s},j_{s}\in\\{0,1,...,p^{p^{k}}-1\\},~{}p,k\in\mathbb{N},~{}~{}\overline{n_{s}}=(\eta_{1}^{s},\eta_{2}^{s},...,\eta_{k}^{s})$
for $s=1,2,...,v$

###### Proof.

For any
$(IVT_{i_{1}}^{p,k},IVT_{i_{2}}^{p,k},...,IVT_{i_{v}}^{p,k}),(IVT_{j_{1}}^{p,k},IVT_{j_{2}}^{p,k},...,IVT_{j_{v}}^{p,k})\in\mathscr{T}^{v}$,
and $(n_{1},n_{2},...,n_{v})\in\mathbb{N}_{0}^{v}$,

$\left((IVT_{i_{1}}^{p,k},IVT_{i_{2}}^{p,k},...,IVT_{i_{v}}^{p,k})\oplus_{p}(IVT_{j_{1}}^{p,k},IVT_{j_{2}}^{p,k},...,IVT_{j_{v}}^{p,k})\right)(n_{1},n_{2},...,n_{v})\in\mathscr{\mathbb{N}_{0}}^{v}$
$and,\left((IVT_{i_{1}}^{p,k},IVT_{i_{2}}^{p,k},...,IVT_{i_{v}}^{p,k})\otimes_{p}(IVT_{j_{1}}^{p,k},IVT_{j_{2}}^{p,k},...,IVT_{j_{v}}^{p,k})\right)(n_{1},n_{2},...,n_{v})\in\mathscr{\mathbb{N}_{0}}^{v}$

since for every $s=1,2,...,v,$

$(IVT_{i_{s}}^{p,k}\oplus_{p}IVT_{j_{s}}^{p,k})(\overline{n_{s}})\in\mathbb{N}_{0}~{}~{}and~{}~{}(IVT_{i_{s}}^{p,k}\otimes_{p}IVT_{j_{s}}^{p,k})(\overline{n_{s}})\in\mathbb{N}_{0}$

where $\overline{n_{s}}=(\eta_{1}^{s},\eta_{2}^{s},...,\eta_{k}^{s})$
Therefore $\mathscr{T}^{v}$ is closed w.r.t. $\oplus_{p}$ and $\otimes_{p}$
for $p\in\mathbb{N}$.
Associativity follows from associativity of $\oplus_{p}$ and $\otimes_{p}$.
$IVT_{0}^{p,k}\in T^{p,k}$ is such that
$\forall\overline{n_{s}}\in\mathbb{N}_{0}^{k},$
$IVT_{0}^{p,k}(\overline{n_{s}})=0$ is the additive identity of $T^{p,k}$
since $\forall s=1,2,...,v$

$(IVT_{0}^{p,k}\oplus_{p}IVT_{s}^{p,k})(\overline{n_{s}})=(IVT_{s}^{p,k}\oplus_{p}IVT_{0}^{p,k})(\overline{n_{s}})=IVT_{s}^{p,k}(\overline{n_{s}})$

where, for each
$(\overline{n_{s}})=(\eta_{1},\eta_{2},...,\eta_{k})\in\mathbb{N}_{0}^{k}$,

$IVT_{0}^{p,k}(\eta_{1},\eta_{2},...,\eta_{k})=(f_{0}(a_{0}^{\eta_{1}},...,a_{0}^{\eta_{k}}),...,f_{0}(a_{l-1}^{\eta_{1}},...,a_{l-1}^{\eta_{k}}))=0$

where, $\eta_{u}=(a_{0}^{\eta_{u}}a_{1}^{\eta_{u}}...a_{l-1}^{\eta_{u}})_{p}$
for $u=1,2,...,k.$
It follows that $(IVT_{0}^{p,k},IVT_{0}^{p,k},...,IVT_{0}^{p,k})$ is the
additive identity of $\mathscr{T}^{v}$ such that for any
$(n_{1},n_{2},...,n_{v})\in\mathbb{N}_{0}^{v}$

$(IVT_{0}^{p,k},IVT_{0}^{p,k},...,IVT_{0}^{p,k})(n_{1},n_{2},...,n_{v})=\left(IVT_{0}^{p,k}(\overline{n_{1}}),IVT_{0}^{p,k}(\overline{n_{2}}),...,IVT_{0}^{p,k}(\overline{n_{v}})\right)$

For any $IVT_{s}^{p,k}\in T^{p,k}$ $\exists~{}IVT_{-s}^{p,k}\in T^{p,k}$ such
that $\forall\overline{n_{s}}\in\mathbb{N}_{0}^{k}$,

$(IVT_{s}^{p,k}\oplus_{p}IVT_{-s}^{p,k})(\overline{n_{s}})=(IVT_{-s}^{p,k}\oplus_{p}IVT_{s}^{p,k})(\overline{n_{s}})=IVT_{0}^{p,k}(\overline{n_{s}})=0$

It follows that for any
$(IVT_{i_{1}}^{p,k},IVT_{i_{2}}^{p,k},...,IVT_{i_{v}}^{p,k})\in\mathscr{T}^{v}$,
$\exists~{}(IVT_{-i_{1}}^{p,k},IVT_{-i_{2}}^{p,k},...,IVT_{-i_{v}}^{p,k})\in\mathscr{T}^{v}$
such that $\forall(n_{1},n_{2},...,n_{v})\in\mathbb{N}_{0}^{v}$,

$\left((IVT_{i_{1}}^{p,k},IVT_{i_{2}}^{p,k},...,IVT_{i_{v}}^{p,k})\oplus_{p}(IVT_{-i_{1}}^{p,k},IVT_{-i_{2}}^{p,k},...,IVT_{-i_{v}}^{p,k})\right)(n_{1},n_{2},...,n_{v})$
$=(IVT_{0}^{p,k},IVT_{0}^{p,k},...,IVT_{0}^{p,k})(n_{1},n_{2},...,n_{v})$
$=\left((IVT_{-i_{1}}^{p,k},IVT_{-i_{2}}^{p,k},...,IVT_{-i_{v}}^{p,k})\oplus_{p}(IVT_{i_{1}}^{p,k},IVT_{i_{2}}^{p,k},...,IVT_{i_{v}}^{p,k})\right)(n_{1},n_{2},...,n_{v})$

Thus for any element of $\mathscr{T}^{v}$ its additive inverse exists in
$\mathscr{T}^{v}$.
Commutativity follows from commutativity of $\oplus_{p}$ and $\otimes_{p}$.

Now for any $IVT_{h}^{p,k},IVT_{i}^{p,k},IVT_{j}^{p,k}\in T^{p,k}$,
$\forall\overline{n_{s}}\in\mathbb{N}_{0}^{k}$, we get,

$(IVT_{h}^{p,k}\otimes_{p}(IVT_{i}^{p,k}\oplus_{p}IVT_{j}^{p,k}))(\overline{n_{s}})=(IVT_{h}^{p,k}\otimes_{p}IVT_{i}^{p,k})(\overline{n_{s}})\oplus_{p}(IVT_{h}^{p,k}\oplus_{p}IVT_{j}^{p,k})(\overline{n_{s}}),$
$((IVT_{i}^{p,k}\oplus_{p}IVT_{j}^{p,k})\otimes_{p}IVT_{h}^{p,k})(\overline{n_{s}})=(IVT_{i}^{p,k}\otimes_{p}IVT_{h}^{p,k})(\overline{n_{s}})\oplus_{p}(IVT_{j}^{p,k}\oplus_{p}IVT_{h}^{p,k})(\overline{n_{s}})$

Thus for any
$(IVT_{h_{1}}^{p,k},...,IVT_{h_{v}}^{p,k}),(IVT_{i_{1}}^{p,k},...,IVT_{i_{v}}^{p,k}),(IVT_{j_{1}}^{p,k},...,IVT_{j_{v}}^{p,k})\in\mathscr{T}^{v},~{}\forall(n_{1},...,n_{v})\in\mathbb{N}_{0}^{v}$,

$\left(IVT_{h_{1}}^{p,k},...,IVT_{h_{v}}^{p,k})\otimes_{p}\left((IVT_{i_{1}}^{p,k},...,IVT_{i_{v}}^{p,k})\oplus_{p}(IVT_{j_{1}}^{p,k},...,IVT_{j_{v}}^{p,k})\right)\right)(n_{1},...,n_{v})$
$=\left((IVT_{h_{1}}^{p,k},...,IVT_{h_{v}}^{p,k})\otimes_{p}(IVT_{i_{1}}^{p,k},...,IVT_{i_{v}}^{p,k})\right)(n_{1},...,n_{v})$
$\oplus_{p}\left((IVT_{h_{1}}^{p,k},...,IVT_{h_{v}}^{p,k})\otimes_{p}(IVT_{j_{1}}^{p,k},...,IVT_{j_{v}}^{p,k})\right)(n_{1},...,n_{v}),and$
$\left(\left((IVT_{i_{1}}^{p,k},...,IVT_{i_{v}}^{p,k})\oplus_{p}(IVT_{j_{1}}^{p,k},...,IVT_{j_{p}}^{p,k})\right)\otimes_{p}(IVT_{h_{1}}^{p,k},...,IVT_{h_{v}}^{p,k})\right)(n_{1},...,n_{v})$
$=\left((IVT_{i_{1}}^{p,k},...,IVT_{i_{v}}^{p,k})\otimes_{p}(IVT_{h_{1}}^{p,k},...,IVT_{h_{v}}^{p,k})\right)(n_{1},...,n_{v})$
$\oplus_{p}\left((IVT_{j_{1}}^{p,k},...,IVT_{j_{v}}^{p,k})\otimes_{p}(IVT_{h_{1}}^{p,k},...,IVT_{h_{v}}^{p,k})\right)(n_{1},...,n_{v})$

Hence the theorem. ∎

######  Theorem 5.5.

$(\mathscr{T}^{v}_{~{}~{}|Q},\oplus_{p},\otimes_{p})$ forms a commutative ring
with identity under the operations $\oplus_{p}$ and $\otimes_{p}$.

###### Proof.

Clearly $(\mathscr{T}^{v}_{~{}~{}|Q},\oplus_{p},\otimes_{p})$ for
$p,k,v\in\mathbb{N}$ is a commutative ring since
$\mathscr{T}^{v}_{~{}~{}|Q}\subseteq\mathscr{T}^{v}$ when $\mathbb{N}_{0}^{v}$
is restricted to $Q^{v}$.
Now, for any $(\eta_{1},\eta_{2},...,\eta_{k})\in Q^{k}$, $\exists$
multiplicative identity $\underline{IVT}_{id}^{p,k}\in T^{p,k}_{~{}|Q}$ such
that

$\underline{IVT}_{id}^{p,k}(\eta_{1},\eta_{2},...,\eta_{k})=\left(f_{id}(\eta_{1},\eta_{2},...,\eta_{k})\right)_{p}=1$
$since~{}(\underline{IVT}_{j}^{p,k}\otimes_{p}\underline{IVT}_{id}^{p,k})(\eta_{1},\eta_{2},...,\eta_{k})=\underline{IVT}_{j}^{p,k}(\eta_{1},\eta_{2},...,\eta_{k})=\left(f_{j}(\eta_{1},\eta_{2},...,\eta_{k})\right)_{p},$
$and~{}(\underline{IVT}_{id}^{p,k}\otimes_{p}\underline{IVT}_{j}^{p,k})(\eta_{1},\eta_{2},...,\eta_{k})=\underline{IVT}_{j}^{p,k}(\eta_{1},\eta_{2},...,\eta_{k})=\left(f_{j}(\eta_{1},\eta_{2},...,\eta_{k})\right)_{p}$

It follows that
$(\underline{IVT}_{id}^{p,k},\underline{IVT}_{id}^{p,k},...,\underline{IVT}_{id}^{p,k})\in\mathscr{T}^{v}_{~{}~{}|Q}$
is the multiplicative identity of $\mathscr{T}^{v}_{~{}~{}|Q}$ such that
$\forall(n_{1},n_{2},...,n_{v})\in Q^{v}$,

$(\underline{IVT}_{id}^{p,k},\underline{IVT}_{id}^{p,k},...,\underline{IVT}_{id}^{p,k})(n_{1},n_{2},...,n_{v})=\underline{IVT}_{id}^{p,k}(\overline{n_{1}})\underline{IVT}_{id}^{p,k}(\overline{n_{2}})...\underline{IVT}_{id}^{p,k}(\overline{n_{v}})$

where
$\underline{IVT}_{id}^{p,k}(\overline{n_{s}})=\underline{IVT}_{id}^{p,k}(\eta_{1}^{s},\eta_{2}^{s},...,\eta_{k}^{s})=1$
for each $s=1,2,...,v$.
Hence the theorem. ∎

##  6 Modelling of DNA Sequence Evolution

DNA can be modelled as a one-dimensional CA using rule matrix multiplication
for linear CA(reported in [23]). The DNA sequence corresponds to the CA
lattice and the deoxyribose sugars to the CA cells. The $4$ sugar bases A, C,
T and G correspond to $4$ possible states of the CA cell.
Now, $1$-neighbourhood CA transition rule is practically absurd since the
transition of cell states of a CA is dependent on neighbouring cells.
Consequently, computation using $4$-state, $k(\in\mathbb{N}\geq
2)$-neighbourhood CA maybe complex. However, in the domain of IVTs,
computations using one-dimensional IVTs hold good. Moreover, for non-linear
transition rules of a CA, the corresponding rule matrix maynot be obtained in
general.
Hence, modelling DNA sequence evolution in terms of one-dimensional IVTs of
$4$-base is a suitable alternative(see [24]).
For any one-variable system having base $4$, there can be $4^{4^{1}}=256$
different functions of which $4^{1}=4$ are linear functions and the others
non-linear. The following example depicts DNA sequence evolution in terms of
IVTs where the sugar bases have been represented with numbers as follows:

$A\rightarrow 0,C\rightarrow 1,T\rightarrow 2,G\rightarrow 3$

######  Example 6.1.

Let CTCTAGAGGGAA be a particular DNA strand of length $12$ at some time. This
strand corresponds to the number sequence $121203033300$.
Evolution of this strand at the next time step can be represented by any
$(IVT_{j_{1}}^{4,1},...,IVT_{j_{12}}^{4,1})\in\tau^{12}$ where
$j_{1},...j_{12}\in\\{0,1,...,4^{4^{1}}-1\\}$.
Let the DNA strand be broken into $2$ blocks of $6$ sugar bases each.
If the first block evolves according to non-linear function
$f_{78}(0\rightarrow 2,1\rightarrow 3,2\rightarrow 0,3\rightarrow 1)$ and the
second block evolves according to linear function $f_{108}(0\rightarrow
0,1\rightarrow 3,2\rightarrow 2,3\rightarrow 1)$ then,

$(IVT_{j_{1}}^{4,1},...,IVT_{j_{12}}^{4,1})(\underbrace{121203}_{block1}\underbrace{033300}_{block2})_{4}$
$=\left(f_{78}(1)f_{78}(2)f_{78}(1)f_{78}(2)f_{78}(0)f_{78}(3)f_{108}(0)f_{108}(3)f_{108}(3)f_{108}(3)f_{108}(0)f_{108}(0)\right)_{4}$
$=(303021011100)_{4}$

Thus the DNA strand evolved at the next step would be GAGATCACCCAA. Hence the
evolution pattern at any later time step can be obtained recursively.

##  7 Conclusion

In this paper Wolfram code and transition function of a one-dimensional CA has
been represented in terms of an IVT. Moreover, if the domain of IVTs is
restricted from positive integers to $p(\in\mathbb{N})$-base numbers, then an
odd dimensional IVT is equivalent to a local transition function of a CA. It
could be proved that the set of all transition functions of a
$p(\in\mathbb{N})$-state CA, forms a commutative ring with identity, whereas
the set of $p$-base IVTs forms only a commutative ring under modular addition
and multiplication. However, for the set of $p$-base IVTs multiplicative
identity under modular addition and multiplication exists, when the domain of
IVTs is restricted from positive integers to $p(\in\mathbb{N})$-base numbers.
The novelty of using IVTs instead of one-dimensional CA, for modelling DNA
sequence evolution has been discussed and depicted in the last section.

## References

  * [1] J. von Neumann, A. W. Burks, et al., Theory of self-reproducing automata, IEEE Transactions on Neural Networks 5 (1) (1966) 3–14.
  * [2] J. L. Schiff, Cellular automata: a discrete view of the world, Vol. 45, John Wiley & Sons, 2011.
  * [3] S. Ulam, On some mathematical problems connected with patterns of growth of figures, in: Proceedings of Symposia in Applied Mathematics, Vol. 14, Am. Math. Soc. Vol. 14, Providence, 1962, pp. 215–224.
  * [4] S. Ghosh, S. Basu, Evolution patterns of some boolean cellular automata having atmost one active cell to model simple dynamical systems, Bull. Cal. Math Soc. 108 (6) (2016) 449–464.
  * [5] S. Ghosh, S. Basu, Evolution patterns of finite celled synchronous cel- lular automata having atmost one active cell, Proceedings of The 10th International Conference MSAST 2016 (2016) 154–164.
  * [6] S. Wolfram, A new kind of science, Wolfram Media, Inc., Champaign, IL, USA, 2002\.
  * [7] P. P. Choudhury, S. Sahoo, M. Chakraborty, S. K. Bhandari, A. Pal, Investigation of the global dynamics of cellular automata using boolean derivatives, Computers & Mathematics with Applications 57 (8) (2009) 1337–1351.
  * [8] A. K. Das, A. Sanyal, P. Palchaudhuri, On characterization of cellular automata with matrix algebra, Information sciences 61 (3) (1992) 251–277.
  * [9] A. Wuensche, Attractor basins of discrete networks, Cognitive Science Research Paper.
  * [10] A. Wuensche, Discrete dynamics lab: Tools for investigating cellular automata and discrete dynamical networks, Kybernetes.
  * [11] X. Xu, Y. Song, S. P. Banks, On the dynamical behavior of cellular automata, International Journal of Bifurcation and Chaos 19 (04) (2009) 1147–1156.
  * [12] R. Edwards, A. Maignan, A class of discrete dynamical systems with properties of both cellular automata and l-systems, Natural Computing (2019) 1–33.
  * [13] S. S. Hassan, P. P. Choudhury, S. Sahoo, R. B. Singh, B. K. Nayak, Collatz function like integral value transformations, Alexandria journal of Mathematics 1 (2) (2012) 30–35.
  * [14] S. S. Hassan, P. P. Choudhury, B. K. Nayak, A. Ghosh, J. Banerjee, Integral value transformations: a class of affine discrete dynamical systems and an application, arXiv preprint arXiv:1110.0724.
  * [15] J. K. Das, S. Sahoo, S. Hassan, P. P. Choudhury, Two dimensional discrete dynamics of integral value transformations, arXiv preprint arXiv:1709.05205.
  * [16] S. Ghosh, S. Basu, Some algebraic properties of linear synchronous cellular automata, arXiv preprint arXiv:1708.09751.
  * [17] J. Kari, Theory of cellular automata: A survey, Theoretical computer science 334 (1-3) (2005) 3–33.
  * [18] S. S. Hassan, B. K. Nayak, P. P. Choudhury, One-dimensional p-adic integral value transformation, Journal of Orissa Mathematical Society 31 (2) (2012) 116–124.
  * [19] P. P. Choudhury, S. Sahoo, B. K. Nayak, S. Hassan, Theory of carry value transformation (cvt) and its application in fractal formation, arXiv preprint arXiv:0904.0534.
  * [20] P. P. Choudhury, S. S. Hassan, S. Sahoo, B. K. Nayak, Act of cvt and evt in the formation of number theoretic fractals, International Journal of Computational Cognition 9 (1) (2011) 1–8.
  * [21] J. K. Das, P. P. Choudhury, S. Sahoo, Multi-number cvt-xor arithmetic operations in any base system and its significant properties, in: 2016 IEEE 6th International Conference on Advanced Computing (IACC), IEEE, 2016, pp. 769–773.
  * [22] S. Pal, S. Sahoo, B. K. Nayak, Properties of carry value transformation, International Journal of Mathematics and Mathematical Sciences 2012.
  * [23] C. Mizas, G. C. Sirakoulis, V. Mardiris, I. Karafyllidis, N. Glykos, R. Sandaltzopoulos, Reconstruction of dna sequences using genetic algorithms and cellular automata: Towards mutation prediction?, Biosystems 92 (1) (2008) 61–68.
  * [24] S. S. Hassan, P. P. Choudhury, R. Guha, S. Chakraborty, A. Goswami, Dna sequence evolution through integral value transformations, Interdisciplinary Sciences: Computational Life Sciences 4 (2) (2012) 128–132.