See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/260289638

Self-Replicating Patterns in 2D Linear Cellular Automata

Article in International Journal of Bifurcation and Chaos · January 2014

DOI: 10.1142/S021812741430002X

CITATIONS READS

24 1,288

4 authors:

Su Uğuz Ugur Sahin

SU Mathematics Academy Rochester Institute of Technology
52 PUBLICATIONS 643 CITATIONS 22 PUBLICATIONS 341 CITATIONS

SEE PROFILE SEE PROFILE

Hasan Akin Irfan Siap

Harran University American University of Sharjah
149 PUBLICATIONS 1,444 CITATIONS 122 PUBLICATIONS 2,889 CITATIONS

SEE PROFILE SEE PROFILE

All content following this page was uploaded by Su Uğuz on 30 December 2015.

The user has requested enhancement of the downloaded file.

 January 29, 2014 6:59 WSPC/S0218-1274 1430002

International Journal of Bifurcation and Chaos, Vol. 24, No. 1 (2014) 1430002 (24 pages)

c World Scientific Publishing Company
DOI: 10.1142/S021812741430002X

Self-Replicating Patterns in 2D Linear

Cellular Automata
Selman Uguz∗
Department of Mathematics, Arts and Science Faculty,
Harran University, Sanliurfa 63120, Turkey
selmanuguz@gmail.com
uguz@mathematik.hu-berlin.de
Uḡur Sahin
Rochester Institute of Technology,
Multi Agent Biorobotic Laboratory, Rochester, NY, USA
Int. J. Bifurcation Chaos 2014.24. Downloaded from www.worldscientific.com

useee@rit.edu
Hasan Akin
by 198.136.31.68 on 12/27/15. For personal use only.

Department of Mathematics, Faculty of Education,

Zirve University, Gaziantep 27260, Turkey
akinhasan25@gmail.com
Irfan Siap
Department of Mathematics, Arts and Science Faculty,
Yıldız Technical University, Istanbul 34210, Turkey
irfansiap@hotmail.com

Received March 27, 2013; Revised July 23, 2013

This paper studies the theoretical aspects of two-dimensional cellular automata (CAs), it classi-
fies this family into subfamilies with respect to their visual behavior and presents an application
to pseudo random number generation by hybridization of these subfamilies. Even though the
basic construction of a cellular automaton is a discrete model, its macroscopic behavior at large
evolution times and on large spatial scales can be a close approximation to a continuous system.
Beyond some statistical properties, we consider geometrical and visual aspects of patterns gen-
erated by CA evolution. The present work focuses on the theory of two-dimensional CA with
respect to uniform periodic, adiabatic and reflexive boundary CA (2D PB, AB and RB) condi-
tions. In total, there are 512 linear rules over the binary field Z2 for each boundary condition
and the effects of these CA are studied on applications of image processing for self-replicating
patterns. After establishing the representation matrices of 2D CA, these linear CA rules are clas-
sified into groups of nine and eight types according to their boundary conditions and the number
of neighboring cells influencing the cells under consideration. All linear rules have been found to
be rendering multiple self-replicating copies of a given image depending on these types. Multiple
copies of any arbitrary image corresponding to CA find innumerable applications in real life
situation, e.g. textile design, DNA genetics research, statistical physics, molecular self-assembly
and artificial life, etc. We conclude by presenting a successful application for generating pseudo
numbers to be used in cryptography by hybridization of these 2D CA subfamilies.

Keywords: Cellular automata; representation matrix; self-replicating patterns; image processing;

cryptography by hybridization.

∗
Author for correspondence

1430002-1
 January 29, 2014 6:59 WSPC/S0218-1274 1430002

S. Uguz et al.

1. Introduction reported in the literature [Siap et al., 2011a; Uguz

Cellular automata (CA for brevity) are discrete et al., 2013a; Ying et al., 2009]. Due to differ-
dynamical systems and their behavior is completely ent important applications of CA in many research
specified in terms of local rules. CAs introduced by areas (e.g. mathematics, computer science, physics,
Ulam and von Neumann [von Neumann, 1966] in chemistry, cryptography, etc) with many different
the early 1950’s, have been studied by Hedlund from purposes (e.g. simulation of some natural phe-
a mathematical perspective [Hedlund, 1969]. Since nomena, pseudo random number generation model,
then many researchers have taken interest in the image processing), CA has been of important atten-
study of CA. One-dimensional CA has been inves- tion in the last few decades [Adamatzky et al.,
tigated to a large extent. However, little interest has 2006; Akın, 2005; Akın & Siap, 2007; Blackburn
been given to two-dimensional cellular automata et al., 1997; Chua & Yang, 1988; Dogaru & Chua,
(2D CA). von Neumann [1966] showed that a cel- 1999, 2000; Das, 1990; Dihidar & Choudhury, 2004;
lular automaton could be universal, a CA was Khan et al., 1997, 1999]. Due to its structure,
organized, each cell of which had a state space of CA can be modeled to understand many behav-
29 states, and it was obtanied that the organized iors in nature easily. Most of the studies in CA
Int. J. Bifurcation Chaos 2014.24. Downloaded from www.worldscientific.com

CA could operate any computable operation. Mean- investigates the one-dimensional case [Inokuchi &
while, because of its complexity, von Neumann rules Sato, 2000]. Note that two-dimensional (2D) CA has
were never operated on a computer. In the early found applications in traffic modeling. For instance
multivalue (including ternary) cellular automaton
by 198.136.31.68 on 12/27/15. For personal use only.

eighties, Wolfram [1983] studied in detail a fam-

ily of one-dimensional (1D) CA rules and showed models for traffic flow are proposed in [Nishi-
that even some simplest rules are capable of com- nari & Takahashi, 2000]. CA have found appli-
plex behavior. He studied also 1D CA with the cations in cryptography [Blackburn et al., 1997],
help of polynomial algebra. Inokuchi & Sato [2000] recently multistate CA have also found applica-
investigated the behaviors of 1D CA generated by tions in cryptography [Mihaljevic et al., 1999] and
the local rule 156. Das [1990] studied the char- especially two-dimensional CA has been proposed
acterization of 1D CA by making use of linear for multisecret sharing scheme for colored images
algebra. Recently, 2D CA has attracted much inter- [Alvarez et al., 2008]. The set of papers [Chattopad-
est. Some basic and precise mathematical models hyay et al., 1999; Dihidar & Choudhury, 2004; Khan
using matrix algebra over the binary field that char- et al., 1997, 1999] deals with the behavior of the uni-
acterize the behavior of 2D nearest neighborhood form 2D CA over binary fields. In [Julian & Chua,
linear CA with null and periodic boundary condi- 2002], the replication properties of additive CA are
tions have been seen in the literature [Choudhury analyzed to extend the existing results.
et al., 2005; Das, 1990; Dihidar & Choudhury, 2004; Recently the studies related to the emergence of
Khan et al., 1997, 1999; Packard & Wolfram, 1985]. self-replicating structures in 1D and 2D CA space
Khan et al. [1997] obtained an analytical approach appeared in [Bilotta et al., 2005; Chou & Reggia,
to study all the possible nearest neighborhood 2D 1997; Gravner & Griffeath, 2011; Mitra & Kumar,
CA linear transformations. They proposed a new 2005; Chua & Mainzer, 2011; Reggia et al., 1998].
rule convention by dividing the 2D linear CA and For example, Gravner et al. [2011] studied the the-
studied the characterization of that 2D CA for dif- ory and application of additive Rule 22 1D Cellular
ferent rules. von Neumann started and sketched a Automata to explain the reason for frequent replica-
path that begins with self-replicating CAs and ends tions and present a method for collecting the small-
with self-replicating physical machines. Packard est periodic seeds. Further, in [Mitra & Kumar,
and Wolfram [Packard & Wolfram, 1985; Wolfram, 2005], the fractal replication in time-manipulated
1983] made much progress within self-replicating 1D CAs was investigated to exhibit complex fractal
physics of CA. Some other studies on CA up to replication behaviors.
now are listed in the references. Everyone agrees In this paper, we study the theory of two-di-
with von Neumann that at some point along this mensional uniform periodic, adiabatic and reflexive
path, it is necessary to move away from discrete boundary CA (2D PCA, ACA, RCA) of all linear
space models to continuous space models. rules (e.g. von Neumann, Moore neighborhood and
Characterization and applications of some spe- the others) and applications of image process-
cific uniform and hybrid 2D CA linear rules are ing for self-replicating patterns (see Figs. 3–18).

1430002-2
 January 29, 2014 6:59 WSPC/S0218-1274 1430002

Self-Replicating Patterns in 2D Linear Cellular Automata

In other words, we are interested in cases when a The organization of the paper is presented as
CA replicates under some special number of evolu- follows. Section 2 discusses the technical preliminar-
tion (i.e. iteration number), that is, makes copies ies of the subject and their details. A mathemati-
of a finite collection of finite configurations, called cal model for CA with the earlier works is given in
self-replicating patterns. Our aim is to investigate Sec. 3. In Sec. 4, the rule matrices of 2D finite peri-
self-replicating patterns for some special bound- odic CA with linear rules and their properties are
aries with their effects. We investigate their clas- presented. The application of 2D CA in image pro-
sification under periodic, adiabatic and reflexive cessing for the self-replicating patterns are given in
boundary conditions over the binary field Z2 . We Sec. 5. The classifications are presented in Sec. 6.
obtain the rule matrix (or representation matrix) In Sec. 7, an application to cryptography obtained
of 2D finite CA for all rules and boundary condi- by the hybridization of these families of CA is pre-
tions. Further, applications of image processing as sented. Finally a conclusion is drawn in Sec. 8.
self-replicating patterns corresponding to the lin-
ear rules of 2D uniform CA with periodic, adia- 2. Technical Preliminaries
batic and reflexive boundary conditions over Z2 are
also studied. We present some illustrative exam- In this section, we introduce 2D CA over the binary
Int. J. Bifurcation Chaos 2014.24. Downloaded from www.worldscientific.com

ples and figures. Using the rule matrices obtained field Z2 = {0, 1} by using the uniform linear local
in this work, the present paper contributes fur- rules. We recall the definition of a CA. Further, we
ther to the algebraic structure of these CA and consider the two-dimensional lattice Z2 and the con-
by 198.136.31.68 on 12/27/15. For personal use only.

2
relates the results to applications studied by dif- figuration space Ω = {0, 1}Z with elements
ferent authors previously (i.e. [Choudhury et al., σ : Z2 → {0, 1}.
2010; Packard & Wolfram, 1985; Wolfram, 1983]).
The paper introduces the 2D nine-neighborhood The value of σ at a point v ∈ Z2 will be denoted
CA and the rules by which the dependencies of a by σv . Let u1 , . . . , us ∈ Z2 be a finite set of distinct
cell are governed. The application of such linear vectors and f : {0, 1}s → {0, 1, 2} be a function.
rules on designed matrices is demonstrated which CA with local rule f is defined as a pair (Ω, Ff ),
forms the basis of self-replicating image processing. where the global transition map Ff : Ω → Ω is
The paper also studies the effect of these 512 linear given by
rules on a particular image. Especially, these rules (Ff σ)v = f (σv+u1 , . . . , σv+us ), v ∈ Z2 .
are used for image transformations as translation,
The function f is called the local rule. The space
multiplication of one image into several replicating
Ω is assumed to be equipped with a (metrizable)
images. While the translation and multiplication
Tychonoff topology; it is easily seen that the global
can be carried out on any arbitrary image, struc-
transition map Ff introduced above and the shift
tured images are needed for others. Some rules yield
operator Uv are continuous in this topology. The
weird and wonderful patterns as seen in the next
2D finite CA consists of m × n cells arranged in m
sections.
rows and n columns, where each cell takes one of
The self-replicating implications of von Neu-
the values of 0 or 1. A configuration of the system
mann for research in nanotechnology, theoretical
is an assignment of states to all the cells. Every
biology and artificial life were discussed in [Smith
configuration determines a next configuration via
et al., 2003]. Self-replication is the process in
a linear transition rule that is local in the sense
which an object or structure produces a copy of
that the state of a cell at time (t + 1) depends
itself. Of course there is some difference between
only on the states of some of its neighbors at time t
self-replication and self-reproduction. In the self-
using modulo 2. For 2D CA nearest neighbors, there
replication side, an exact duplicate is made (see
Figs. 2–12). Since multiple copies of an arbitrary
image have innumerable applications in real life sit- Table 1. Local rule number conventions
for 2D finite CA.
uations (for example, textile design, DNA genetics
research, etc., see [Chua & Mainzer, 2011; Dogaru & 26 = 64 27 = 128 28 = 256
Chua, 1999, 2000; Schadschneider & Schreckenberg, 5
2 = 32 0
2 =1 21 = 2
1993; Rubio et al., 2004; Smith et al., 2003]), the
24 = 16 23 = 8 22 = 4
findings of this study are interesting.

1430002-3
 January 29, 2014 6:59 WSPC/S0218-1274 1430002

S. Uguz et al.

• A null boundary (NB) CA is where the extreme

cells are connected to 0-state.
• A periodic boundary (PB) CA is where the
extreme cells are adjacent to each other (see
Table 3 or proof of Lemma 2).
• A adiabatic boundary (AB) CA duplicates the
value of the cell in an extra virtual neighbor (see
Table 4).
• A reflexive boundary (RB) CA is designed such
Fig. 1. The nearest neighborhood comprises eight cells that the value of left and right neighbors are the
which surround center xij with the coefficients ci ∈ Z2 for same with respect to the boundary cell.
i = 1, 2, 4, . . . , 128. The values of ci will be restricted to the
case of being zero or nonzero (i.e. ∈ Z2 ). According to this The 2D infinite CA generated by the local rule Rule
assignment to the coefficients ci in Eq. (1) the rule number
will be defined. The linear combination of the neighboring
with periodic boundary is defined as
cells on which each cell value is dependent is called the rule 2 2
number of the 2D CA over Z2 . FRule=PB : ZZ2 → ZZ2 where
Int. J. Bifurcation Chaos 2014.24. Downloaded from www.worldscientific.com

(t)
(FRule=PB x)(i,j)
are nine cells arranged in a 3 × 3 matrix center-
ing that particular cell (see [Chattopadhyay et al.,
by 198.136.31.68 on 12/27/15. For personal use only.

(t) (t) (t)

1999; Das, 1990; Dihidar & Choudhury, 2004] for = c1 x(i,j) + c2 x(i,j+1) + c4 x(i+1,j+1)
the details). For 2D CA there are many types of (t) (t) (t)
neighborhoods, but in this work we restrict our- + c8 x(i+1,j) + c16 x(i+1,j−1) + c32 x(i,j−1)
selves to all linear rules from Rule 1 to Rule 512.
(t) (t)
So, we can define the (t + 1)th state of the (i, j)th + c64 x(i−1,j−1) + c128 x(i−1,j)
cell as follows;
(t)
+ c256 x(i−1,j+1) (mod 2)
(t+1) (t) (t) (t)
x(i,j) = c1 x(i,j) + c2 x(i,j+1) + c4 x(i+1,j+1)
(t+1)
= x(i,j) . (2)
(t) (t) (t)
+ c8 x(i+1,j) + c16 x(i+1,j−1) + c32 x(i,j−1)
In this paper, FPB denotes a 2D finite CA gen-
(t) (t)
+ c64 x(i−1,j−1) + c128 x(i−1,j) erated by the rule with periodic boundary (PB)
(as above), similarly FAB with adiabatic boundary
(t) (AB) and FRB with reflexive boundary (RB). It is
+ c256 x(i−1,j+1) (mod 2), (1)
well known that these CA are discrete dynamical
where the values of ci will be restricted to the case systems formed by a finite two-dimensional array
of being zero or nonzero i.e. binary. According to m × n composed by identical objects called cells.
this assignment to the coefficients ci in equation (1) Let
the rule number will be defined. The linear combi-
nation of the neighboring cells on which each cell I : Mm×n (Z2 ) → Zmn
2 .
value is dependent is called the rule number of the
2D CA over the field Z2 . Regarding the neighbor- I takes the tth state [Xt ] given by
hood of the extreme cells, there exist four different  
x11 x12 ··· x1n
approaches.
x ··· x2n 
 21 x22 
 . .. 
 . .. 
Table 2. 2D finite CA3×3 with the center  . . ··· . 
element x(i,j) .
xm1 xm2 ··· xmn
x(i−1,j−1) x(i−1,j) x(i−1,j+1) → (x11 , x12 , . . . , x1n , . . . , xm1 , . . . , xmn )T . (3)
x(i,j−1) x(i,j) x(i,j+1)
x(i+1,j−1) x(i+1,j) x(i+1,j+1) Therefore, the local rules will be assumed to
act on Zmn
2 rather than Mm×n (Z2 ). The binary

1430002-4
 January 29, 2014 6:59 WSPC/S0218-1274 1430002

Self-Replicating Patterns in 2D Linear Cellular Automata

information matrix of order m × n denoted by 3. Mathematical Model for Cellular

 (t) (t)
 Automata Rules
x11 . . . x1n
  CAs are nowadays useful mathematical models for
 . .. .. 
C (t) =  .. . .  systems to obtain many different complicated pat-
 
(t) (t) terns of behavior. The extension from one dimen-
xm1 . . . xmn sion (1D) to two dimension (2D) is significant for
is called the configuration of the 2D finite CA at comparisons with many experimental results on
a particular time t. From (3), we can define as pattern formation in physical and many different
follows, systems. In the literature, there are several possi-
 (t)   (t+1)  ble lattices and neighborhood structures for two-
x11 x11 dimensional CAs, i.e. triangular, square, hexagonal,
 .   .  etc. [Packard & Wolfram, 1985; Siap et al., 2011b;
 .   . 
 .   .  Uguz et al., 2013b]. This paper considers primar-
   
 (t)   (t+1)  ily square lattice, with its neighborhood structures
 x1n  x1n 
    illustrated in Fig. 1. We consider possible near-
 .   . 
Int. J. Bifurcation Chaos 2014.24. Downloaded from www.worldscientific.com

(TRule=PB )mn×mn . 

..  =  .. 
  
est neighborhood structures to construct the rule
    matrices over two-dimensional CAs. In the cellu-
 (t)   (t+1) 
 xm1  xm1  lar automaton iteration, the value of the center
   
 ..   .. 
by 198.136.31.68 on 12/27/15. For personal use only.

cell is updated according to a rule which depends

 .   . 
    on the values of the possible neighborhood cells.
(t) (t+1) It is seen that despite the simplicity of their con-
xmn xmn
struction, CAs have very complicated behaviors (see
where Figs. 2–18). The application of linear rules men-
(t+1) (t) (t) (t) tioned in the previous section can be realized on a
xij = c1 xi(j) + c32 xi(j−1) + c2 xi(j+1) configuration matrix, where every entry is either 0
(t) (t) (t) or 1 (for the case Z2 ). It may be mentioned that
+ c4 xi+1(j+1) + c8 x(i+1)j + c16 x(i+1)j−1 instead of applying the same rule to each entry of
the configuration matrix, it is admissible to apply
(t) (t)
+ c64 x(i−1)j−1 + c128 x(i−1)j different rules to different entries at the same time.
While the former characterizes the uniform CA,
(t)
+ c256 x(i−1)j+1 (mod 2), (4) the latter characterizes hybrid CA (an application
of this type is given in Sec. 7). An illustrative
where i denotes the ith row of the matrix C (t) and example is presented for uniform null boundary
j denotes the jth column of the matrix C (t) . Hence, von Neumann CA corresponding to Rule 170NB
the action on configuration sets is given as below.

(TRule )mn×mn · [Xt ] = [Xt+1 ]. Example 3.1. We present a 2D CA with configura-

tion of size 3 × 3 under the null boundary condition
The matrix (TRule )mn×mn is called the rule matrix to illustrate the theory. By using the linearity of
with respect to the 2D finite CAm×n . The conven- rule,
tional method of 2D CA with periodic boundary
can be explained in Table 3. Rule 170NB = Rule(2 + 8 + 32 + 128)NB
= Rule 2NB + Rule 8NB
Table 3. Periodic boundary condition in a 2D finite CA3×3 .
+ Rule 32NB + Rule 128NB
x(i+1,j−1) x(i−1,j−1) x(i,j−1) x(i+1,j−1) x(i−1,j−1)
is applied uniformly to each cell of a problem
x(i+1,j+1) x(i−1,j+1) x(i,j+1) x(i+1,j+1) x(i−1,j+1)
matrix of order (3 × 3) with null boundary condi-
x(i+1,j) x(i−1,j) x(i,j) x(i+1,j) x(i−1,j) tion (extreme cells are connected with 0-states). If
x(i+1,j−1) x(i−1,j−1) x(i,j−1) x(i+1,j−1) x(i−1,j−1) we take m = 3 and n = 3, then we consider a config-
x(i+1,j+1) x(i−1,j+1) x(i,j+1) x(i+1,j+1) x(i−1,j+1) uration of size 3 × 3 with null boundary condition.
Now, we apply the Rule 170NB, and we obtain the

1430002-5
 January 29, 2014 6:59 WSPC/S0218-1274 1430002

S. Uguz et al.

rule matrix T170NB as note is that these Type n rules are not related to
  the types given by Wolfram [1983].
0 1 0 1 0 0 0 0 0
1 0
 0 1 0 1 0 0 0  Remark 3.1. In [Choudhury et al., 2010], these clas-
 
0 1 0 0 0 1 0 0 0 sifications are referred to as Group n rules (we call
 
1 0 0 0 1 0 1 0 0 Type n rules just in case they are confused with the
 
  algebraic group structure), the grouping has been
T170NB = 0 1 0 1 0 1 0 1 0
  Group n for n = 1, 2, . . . , 9, including the rules that
0 0 1 0 1 0 0 0 1
  refer to the dependency of current cell on N neigh-
0 0
 0 0 1 0 0 0 1  boring cells amongst top, bottom, left, right, top-
 
0 0 0 0 1 0 1 0 1 left, top-right, bottom-left, bottom-right and itself
0 0 0 0 0 1 0 1 0 (see Fig. 1).
 
S3 I3 03 Here we briefly mention how Type 1 rules dif-
  fer when the boundary conditions change. For the
=  I3 S3 I3 
null and periodic boundary case (see Fig. 5), Type 1
Int. J. Bifurcation Chaos 2014.24. Downloaded from www.worldscientific.com

03 I3 S3 9×9 includes 1, 2, 4, 8, 16, 32, 64, 128, and 256. Whereas

where each submatrix is of order 3 × 3, and for the adiabatic and reflexive boundary case (see
  Fig. 6), Type 1 includes 1, 2, 3, 4, 5, 8, 9, 16,
by 198.136.31.68 on 12/27/15. For personal use only.

0 1 0 17, 32, 33, 64, 65, 128, 129, 256 and 257. Simi-
 
S3×3 = 1 0 1. larly rules belonging to other Type n have been
0 1 0 obtained. It is noted that number of 1’s presented
in the binary sequence of a rule is the same as its
The evolution of 2D CAs from seeds called type number. These T ype n rules are obtained by
as a first image in Figs. 4–20, consist of a few the number n of self-replicating number of the first
nonzero initial sites. Similar cases in one dimen- image (see Figs. 2–12). These rules are classified in
sion, some CA give regular and self-similar patterns, Tables 5 and 6 with respect to the chosen boundary
others give complicated and random patterns (see conditions.
Figs. 14–17). Some new features in two dimensions
are the generation of patterns with different bound-
aries observed in many natural systems. Detailed 4. Rule Matrices of 2D Finite
analysis will be given in Sec. 5. CA Rules
For simplicity, we consider only 2D CA lin-
ear rules. The rule convention is organized as fol- In this section, we obtain the rule matrix corre-
lows. When we consider the nearest neighbors of sponding to a 2D finite CA with the periodic bound-
2D CA, there are nine variables which are under ary generated by the local rules over the field Z2
consideration as given in Fig. 2. The center cell by presenting the auxiliary matrices that play an
marked xij (see Fig. 1) is the cell under consid- important role in the rule matrix of a 2D cellular
eration. In 2D CA, the state of the cell which is automaton. Further, this will be established for each
under consideration depends on its neighboring cell boundary case.
states. Each of the cells could be considered as a The rule matrices of rule number R are denoted
variable and thus for 2D CA there are nine vari- by TR . We study the rule matrix TR such that TR
ables to be studied. The number of linear rules can operates on the current CA states [X t ] (the binary
be realized in the following way. The number of matrix of dimension (m×n)) and generates the next
rules combined state [X t+1 ] of (m × n).
  by a combination
 of
 these nine vari-
ables is 90 + 91 + 92 + · · · + 99 = 512 which
includes rules characterizing no dependency. Note
4.1. Rule matrices with primary
that, these 512 linear rules were previously classi-
fied by taking into account the number of cells under
rules under null boundary
just null boundary consideration [Choudhury et al., condition
2010] (see Table 5). The classification presented in The auxiliary matrices T1 and T2 for the null bound-
Tables 5 and 6 defines Type n rules. An important ary are defined as follows:

1430002-6
 January 29, 2014 6:59 WSPC/S0218-1274 1430002

Self-Replicating Patterns in 2D Linear Cellular Automata

   
0 1 0 0 . 0 0 0 . 0
0 . 1 . .
 0 1 0   0 . 
 .  
T1 =  . . . .  and T2 = 0 1 0 . . .
   
. . . . 1 . . . . .
0 0 0 0 0 0 0 . 1 0

Lemma 1 [Choudhury et al., 2005]. The representation of the next state of all primary rules
(1 , 2 , 4 , 8 , 16 , 32 , 64 , 128 and 256 ) under the null boundary condition can be given by using the auxil-
iary matrices T1 and T2 defined above in the following way:
Rule 1N : [Xt+1 ] = [Xt ] Rule 2N : [Xt+1 ] = [Xt ][T2 ]
Rule 4N : [Xt+1 ] = [T1 ][Xt ][T2 ] Rule 8N : [Xt+1 ] = [T1 ][Xt ]
Rule 16N : [Xt+1 ] = [T1 ][Xt ][T1 ] Rule 32N : [Xt+1 ] = [Xt ][T1 ]
Rule 64N : [Xt+1 ] = [T2 ][Xt ][T1 ] Rule 128N : [Xt+1 ] = [T2 ][Xt ]
Int. J. Bifurcation Chaos 2014.24. Downloaded from www.worldscientific.com

Rule 256N : [Xt+1 ] = [T2 ][Xt ][T2 ].

4.2. Rule matrices with primary rules under periodic boundary condition
by 198.136.31.68 on 12/27/15. For personal use only.

The auxiliary matrices T1p and T2p for periodic boundary case are defined as follows:
   
0 1 0 0 . 0 0 . 0 1
0 0 1 0 .  1 0 . . .
   
   
T1p =  . . . . .  and T2p = 0 1 0 . . . (5)
   
 . . . . 1 . . . . .
1 0 0 0 0 0 0 . 1 0
Proposition 1. The fundamental periodic number rule matrices T1PR , T2PR , T4PR , T8PR , T16PR , T32PR ,
T128PR , T256PR are respectively given by
     
In 0 0 0 . T1p 0 0 0 . T2p 0 0 0 .
0 In 0 0 .      0 T2p 0 0 
  0 T1p 0 0 .  .
 
.  T2PR =    
T1PR =  . . . .  . . . . . T32PR = . . . . .
     
. 0 0 In 0   . 0 0 T1p 0   . 0 0 T2p 0 
. 0 0 0 In . 0 0 0 T1p . 0 0 0 T2p
     
0 T1p 0 0 . 0 0 0 0 T2p 0 In 0 0 .
 0 0 T1p 0  . T2p 0 0 0 .  0 0 In 0 
.
     
     
T4PR = . . . .  . T64PR =  0 T2p 0 0 .  T8PR =. . . . 
.
     
 0 0 0 0 T1p   . . . . .  0 0 0 0 In 
T1p 0 0 0 . . 0 0 T2p 0 In 0 0 0 .
     
0 0 0 0 In 0 T2p 0 0 . 0 0 0 0 T1p
In 0 0 0 .  0 0 T2p 0  . T1p 0 0 0 . 
     
     
T128PR =  0 In 0 0 .  T16PR =  . . . .  T256PR =  0 T1p 0
. 0 . 
     
. . . . .  0 0 0 0 T2p   . . . . . 
. 0 0 In 0 T2p 0 0 0 . . 0 0 T1p 0

where T1p and T2p are given as in (5). Also In is an identity matrix n × n type.

1430002-7
 January 29, 2014 6:59 WSPC/S0218-1274 1430002

S. Uguz et al.

Proof. In order to determine the rule matrix Lemma 2. The next state of all primary rules (1,
(TP R )mn×mn we need to determine the action of 2 , 4 , 8 , 16 , 32 , 64 , 128 , 256 ) of 2D periodic cellular
(TP R )mn×mn on the base vectors. First, we consider automaton over Z2 can be represented as follows:
the linear transformation (T) from m × n matrix
Rule 1P : [Xt+1 ] = [Xt ]
space to itself. Next, we relate the transformation
(T) with (TP R ). Let eij denote the matrix of size Rule 2P : [Xt+1 ] = [Xt ][T2p ]
m × n where the (i, j) position is equal to one and Rule 4P : [Xt+1 ] = [T1p ][Xt ][T2p ]
the rest of the entries equal to zero. It is well known
that these vectors give the standard basis for this Rule 8P : [Xt+1 ] = [T1p ][Xt ]
space. Given eij , the image of eij which is T (eij ) Rule 16P : [Xt+1 ] = [T1p ][Xt ][T1p ]
is related to the suitable nearest neighbors. Then Rule 32P : [Xt+1 ] = [Xt ][T1p ]
T (eij ) equals to a linear combination of its suit-
able neighbors corresponding to the rules. Hence, Rule 64P : [Xt+1 ] = [T2p ][Xt ][T1p ]
without getting into details, we obtain the rule Rule 128P : [Xt+1 ] = [T2p ][Xt ]
matrices.

Rule 256P : [Xt+1 ] = [T2p ][Xt ][T2p ].
Int. J. Bifurcation Chaos 2014.24. Downloaded from www.worldscientific.com

From Proposition 1, one can easily see the fol- Proof. Let
lowing result which reduces the number of indepen-  
dent primary rules from eight to four. The following x11 x12 x13
 
by 198.136.31.68 on 12/27/15. For personal use only.

is due to the matrix transpose equality (T1p )t = T2p . [Xt ] = x21 x22 x23 

Corollary 4.1. The following matrix transpose x31 x32 x33

identitites are satisfied: (where x11 , x12, . . . , x33 ∈ Z2 ) be the state of CA at
time t. Let RP ([Xt ]) denote the next state of ([Xt ])
(T2P R )t = T32P R , (T16P R )t = T256P R ,
with respect to the rule number. To obtain the state
(T8P R )t = T128P R , (T4P R )t = T64P R . of CA at time (t + 1) Rule1: [Xt+1 ] = [Xt ], we will
do the following operations: we get the rule matri-
Hence we get the following general rule matrix ces TP R of designed orders. The periodic boundary
result for the periodic case as a theorem. case of state [Xt ] can be taken as
Theorem 1 [Periodic Case]. The matrix for any x33 x31 x32 x33 x31
periodic boundary CA rule (PB) can be represented
x13 x11 x12 x13 x11
as
x23 x21 x22 x23 x21 .
[TP R ]mn×mn
x33 x31 x32 x33 x31
 
Ap Bp 0 0 . 0 Dp x13 x11 x12 x13 x11
 
Cp Ap Bp 0 . . 0 We can show one of the states obtained explicitly
 
 0 Cp Ap Bp 0 . .  and the others follow in a similar way. Let us con-
 
 .  sider Rule 4P.
= . . . . . .   
 
 . . 0 Cp Ap Bp 0 x22 x23 x21
   
  R4P ([Xt ]) = x32 x33 x31 
0 . . 0 Cp Ap Bp 
Ep 0 . . 0 Cp Ap x12 x13 x11
  
where Ap , Bp , Cp , Dp , Ep are one of the follow- 0 1 0 x11 x12 x13
ing matrices of the order of n × n : 0, I, T1p , T2p ,   
= 0 0 1 x21 x22 x23 
I + T1p , I + T2p , T1p + T2p and I + T1p + T2p .
1 0 0 x31 x32 x33
 
Proof. By applying Proposition 1 and making use 0 0 1
of linearity, the result is obtained. Note that in  
× 1 0 0.

matrix representation, T1p T2p , I = In×n = identity
and 0 = 0n×n zero matrix are all of type n × n.
0 1 0

1430002-8
 January 29, 2014 6:59 WSPC/S0218-1274 1430002

Self-Replicating Patterns in 2D Linear Cellular Automata

Corollary 4.2. Rank of the periodic auxiliary Table 4. 2D finite CA2×2 with
matrices [T1p ]n×n and [T2p ]n×n is n. In other words, adiabatic boundary condition.
the periodic auxiliary matrices are invertible.
x11 x11 x12 x12
Example 4.1 [von Neumann Neighborhood]. Since x11 x11 x12 x12
Rule 170P = Rule 2P + Rule 8P + Rule 32P + x21 x21 x22 x22
Rule 128P, we have
x21 x21 x22 x22
[Xt+1 ] = [Xt ][T2p ] + [T1p ][Xt ] + [Xt ][T1p ]
+ [T2p ][Xt ].
Then we obtain the following description:
 
x11 x12 x13
 
T170P ([Xt ]) = T170P x21 x22 x23 
x31 x32 x33
 
Int. J. Bifurcation Chaos 2014.24. Downloaded from www.worldscientific.com

x12 + x21 + x13 + x31 x11 + x13 + x22 + x32 x12 + x23 + x11 + x33
 
= x11 + x22 + x31 + x23 x12 + x23 + x32 + dx21 x13 + x33 + x22 + x21 
x21 + x32 + x11 + x33 x22 + x33 + x31 + x12 x23 + x32 + x31 + x13
by 198.136.31.68 on 12/27/15. For personal use only.

       
x31 x32 x33 x12 x13 x11 x21 x22 x23 x13 x11 x12
       
= x11 x12 x13  + x22 x23 x21  + x31 x32 x33  + x23 x21 x22 
x21 x22 x23 x32 x33 x31 x11 x12 x13 x33 x31 x32
= [Xt ][T2p ] + [T1p ][Xt ] + [Xt ][T1p ] + [T2p ][Xt ].

4.3. Rule matrices with primary rules under adiabatic boundary condition
The auxiliary matrices T1a and T2a for the adiabatic boundary case are defined as follows:
   
0 1 0 0 . 1 0 0 . 0
0 0 1 0 . 1 0 . . . 
   
 . .  and T2a = 
 
T1a =  . . . 0 1 0 . . . (6)
   
. . . . 1 . . . . .
0 0 0 0 1 0 0 . 1 0
Proposition 2. The fundamental adiabatic boundary (AB), rule number (n), rule matrices TnAB : T1AB ,
T2AB , T4AB , T8AB , T16AB , T32AB , T128AB , T256AB are
     
In 0 0 0 . T1a 0 0 0 . T2a 0 0 0 .
0 I 0 0 .   0 T .   0 T . 
 n   1a 0 0   2a 0 0 
     
T1AB = . . . . . T2AB =  .
 . . . .  T32AB = 
 . . . . . 
     
 . 0 0 In 0   . 0 0 T1a 0   . 0 0 T2a 0 
. 0 0 0 In . 0 0 0 T1a . 0 0 0 T2a
     
0 T1a 0 0 . T2a 0 0 0 0 0 In 0 0 .
0 0 T     .
 1a 0 .  T2a 0 0 0 . 0 0 In 0 
     
T4AB =   . . . . .  T64AB =  0
  T2a 0 0 . T8AB = . .
 . . . 
     
0 0 0 0 T1a   . . . . . 0 0 0 0 In 
0 0 0 0 T1a . 0 0 T2a 0 0 0 0 0 In

1430002-9
 January 29, 2014 6:59 WSPC/S0218-1274 1430002

S. Uguz et al.

     
In 0 0 0 0 0 T2a 0 0 . T1a 0 0 0 0
I . 0 0 T .  T .
 n 0 0 0   2a 0   1a 0 0 0 
     
T128AB =
 0 In 0 0 . T16AB 
= . . . . .  T256AB =
 0 T1a 0 0 .

     
. . . . . 0 0 0 0 T2a   . . . . .
. 0 0 In 0 0 0 0 0 T2a . 0 0 T1a 0
where T1a and T2a are given as in (6). Also In is the identity matrix n × n type.

Proof. In order to determine the rule matrix (TAB )mn×mn we need to determine the action of (TAB )mn×mn
on the base vectors. The rule matrix related to these equations is obtained after similar calculations as in
the proof of Proposition 1.

Hence we get the following general rule matrix result for the adiabatic case as a theorem.
Theorem 2 [Adiabatic Case]. The rule matrix for any adiabatic boundary CA rule (AB) can be represented
as
Int. J. Bifurcation Chaos 2014.24. Downloaded from www.worldscientific.com

 
Aa Ba 0 0 . 0 0
 
 Ca Aa Ba 0 . . 0
 
0 . 
by 198.136.31.68 on 12/27/15. For personal use only.

 Ca Aa Ba 0 . 
 . 
[TAB ]mn×mn = . . . . . . 
 
 . . 0 Ca Aa Ba 0
 
 
0 . . 0 Ca Aa Ba 
0 0 . . 0 Ca Aa
where Aa , Ba , Ca are one of the following matrices of the order of n × n : 0, I, T1a , T2a , I + T1a , I + T2a ,
T1a + T2a and I + T1a + T2a .

Proof. The desired result follows by applying Proposition 2.

Lemma 3. The next state of all primary rules (1 , 2 , 4 , 8 , 16 , 32 , 64 , 128 , 256 ) of 2D adiabatic cellular
automaton with Z2 can be represented as follows:
Rule 1AB: [Xt+1 ] = [Xt ] Rule 2AB: [Xt+1 ] = [Xt ][T1a ]t
Rule 4AB: [Xt+1 ] = [T1a ][Xt ][T1a ]t Rule 8AB: [Xt+1 ] = [T1a ][Xt ]
Rule 16AB: [Xt+1 ] = [T1a ][Xt ][T2a ]t Rule 32AB: [Xt+1 ] = [Xt ][T2a ]t
Rule 64AB: [Xt+1 ] = [T2a ][Xt ][T2a ]t Rule 128AB: [Xt+1 ] = [T2a ][Xt ]
Rule 256AB: [Xt+1 ] = [T2a ][Xt ][T1a ]t .
It is easily seen that the adiabatic auxiliary matrices are not invertible.
Corollary 4.3. The rank of the adiabatic auxiliary matrices [T1a ]n×n and [T2a ]n×n is (n − 1).

4.4. Rule matrices with primary rules under reflexive boundary condition
The auxiliary matrices T1r and T2r for the reflexive boundary case are defined as follows:
   
0 1 0 0 . 0 1 0 . 0
0 0 1 0   0 . . .
 . 1 
   
T1r =  . . . . .  and T2r = 0 1 0 . . . (7)
   
. . . . 1 . . . . .
0 0 0 1 0 0 0 . 1 0

1430002-10
 January 29, 2014 6:59 WSPC/S0218-1274 1430002

Self-Replicating Patterns in 2D Linear Cellular Automata

Proposition 3. The fundamental reflexive boundary (RB), rule number (n), rule matrices TnRB : T1RB ,
T2RB , T4RB , T8RB , T16RB , T32RB , T128RB , T256RB are
     
In 0 0 0 . T1r 0 0 0 . T2r 0 0 0 .
0 I 0 0 .   0 T .   0 T . 
 n   1r 0 0   2r 0 0 
     
T1RB = . . . . . T2RB =  .
 . . . .  
 T32AB =  . . . . . 

     
 . 0 0 In 0   . 0 0 T1r 0   . 0 0 T2r 0 
. 0 0 0 In . 0 0 0 T1r . 0 0 0 T2r
     
0 T1r 0 0 . 0 T2r 0 0 0 0 In 0 0 .
0 .  T . 0 0 I .
 0 T1r 0   2r 0 0 0   n 0 
     
T4RB =
. . . . .  T64RB =
 0 T2r 0 0 .
 T8RB 
= . . . . .
     
0 0 0 0 T1r   . . . . . 0 0 0 0 In 
0 0 0 T1r 0 . 0 0 T2r 0 0 0 0 In 0
Int. J. Bifurcation Chaos 2014.24. Downloaded from www.worldscientific.com

     
0 In 0 0 0 0 T2r 0 0 . 0 T1r 0 0 0
I . 0 0 T   .
 n 0 0 0   2r 0 .  T1r 0 0 0 
     
by 198.136.31.68 on 12/27/15. For personal use only.

T128RB =
 0 In 0 0 .
 T16RB 
= . . . . 
.  T256RB = 
 0 T1r 0 0 .

     
. . . . . 0 0 0 0 T2r   . . . . .
. 0 0 In 0 0 0 0 T2r 0 . 0 0 T1r 0

where T1r and T2r are given as in (7).

Lemma 4. The next state of all primary rules (1 ,
Proof. The rule matrix related to these equations 2 , 4 , 8 , 16 , 32 , 64 , 128 , 256 ) of 2D reflexive cellular
can be found by using the base vectors.
automaton over Z2 can be represented as follows:

Rule 1RB: [Xt+1 ] = [Xt ]

Hence we get the following general rule matrix
result for the reflexive case as a theorem. Rule 2RB: [Xt+1 ] = [Xt ][T1r ]t

Theorem 3 [Reflexive Case]. The rule matrix for a

Rule 4RB: [Xt+1 ] = [T1r ][Xt ][T1r ]t
reflexive boundary CA rule (RB) is represented as Rule 8RB: [Xt+1 ] = [T1r ][Xt ]
[TRB ]mn×mn Rule 16RB: [Xt+1 ] = [T1r ][Xt ][T2r ]t
  Rule 32RB: [Xt+1 ] = [Xt ][T2r ]t
Ar Br 0 0 . 0 0
  Rule 64RB: [Xt+1 ] = [T2r ][Xt ][T2r ]t
Cr Ar Br 0 . . 0
 
  Rule 128RB: [Xt+1 ] = [T2r ][Xt ]
 0 Cr Ar Br 0 . . 
  Rule 256RB: [Xt+1 ] = [T2r ][Xt ][T1r ]t .
= 
. . . . . . . 

 
 . . 0 Cr Ar Br 0 It is easily seen that the reflexive auxiliary
 
0 Br  matrices are not of full rank, i.e. these are nonin-
 . . 0 Cr Ar  vertible matrices.
0 0 . . 0 Cr Ar
Corollary 4.4. The rank of the reflexive auxiliary
where Ar , Br , Cr are one of the following matrices matrices [T1r ]n×n and [T2r ]n×n is (n − 1).
of the order of n × n: 0, I, T1r , T2r , I + T1r , I + T2r ,
T1r + T2r and I + T1r + T2r . Here we briefly emphasize on the importance
of the reversibility property of linear CA. The
Proof. From Proposition 3 and linearity, the proof dimension of the kernel of the transition matrix
is obtained.
of CA gives a clue to draw the state transition

1430002-11
 January 29, 2014 6:59 WSPC/S0218-1274 1430002

S. Uguz et al.

Fig. 2. An application of Rule 8 with null (NB), periodic (PB), adiabatic (AB) and reflexive (RB) boundary respectively
after 16 iterations of the first image.
Int. J. Bifurcation Chaos 2014.24. Downloaded from www.worldscientific.com
by 198.136.31.68 on 12/27/15. For personal use only.

Fig. 3. An application of Rule 72 after 16 iterations of the first image.

Fig. 4. An application of Rule 7 after 16 iterations of the first image.

Fig. 5. An application of Rule 149 after 16 iterations of the first image.

Fig. 6. An application of Rule 93 after 16 iterations of the first image.

1430002-12
 January 29, 2014 6:59 WSPC/S0218-1274 1430002

Self-Replicating Patterns in 2D Linear Cellular Automata

Fig. 7. An application of Rule 31 after 16 iterations of the first image.

Int. J. Bifurcation Chaos 2014.24. Downloaded from www.worldscientific.com
by 198.136.31.68 on 12/27/15. For personal use only.

Fig. 8. An application of Rule 63 after 16 iterations of the first image.

Fig. 9. An application of Rule 191 after 16 iterations of the first image.

Fig. 10. An application of Rule 415 after 16 iterations of the first image.

Fig. 11. An application of Rule 510 after 16 iterations of the first image.

1430002-13
 January 29, 2014 6:59 WSPC/S0218-1274 1430002

S. Uguz et al.

Fig. 12. An application of Rule 511 after 16 iterations of the first image.
Int. J. Bifurcation Chaos 2014.24. Downloaded from www.worldscientific.com
by 198.136.31.68 on 12/27/15. For personal use only.

Fig. 13. An application of Rule 315 after 5, 12, 15 and 16 iterations of the first image.

1430002-14
 January 29, 2014 6:59 WSPC/S0218-1274 1430002

Self-Replicating Patterns in 2D Linear Cellular Automata

Int. J. Bifurcation Chaos 2014.24. Downloaded from www.worldscientific.com
by 198.136.31.68 on 12/27/15. For personal use only.

Fig. 14. An application of Rule 413 after 7, 12, 15 and 16 iterations of the first image.

Fig. 15. An application of Rule 510 after 5, 11, 12 and 16 iterations of the first image.

1430002-15
 January 29, 2014 6:59 WSPC/S0218-1274 1430002

S. Uguz et al.
Int. J. Bifurcation Chaos 2014.24. Downloaded from www.worldscientific.com
by 198.136.31.68 on 12/27/15. For personal use only.

Fig. 16. An application of Rule 171 after 7, 12, 13 and 15 iterations of the first image.

diagram [Chattopadhyay et al., 1999] to determine In the next section, by applying the rule
its reversibility. Thus, in order to determine the matrices to the patterns, we generate the new pat-
dimension of the kernel of a 2D CA, one can study terns and classify CA linear rules based on the
the rank of (Trules )mn×mn . For finite CA, in order behavior of the rule in the nth iteration and their
to obtain the inverse of a 2D finite linear CA many boundaries.
authors [Khan et al., 1997, 1999; Siap et al., 2011b]
have made use of the rule matrices. Since we have
5. Application of 2D CA in Image
already found the rule matrix Trules correspond-
ing to 2D finite CA, we can state the following
Processing: Self-Replicating
relation between the column vectors X (t) and the Patterns
rule matrix Trules : X (t+1) = Trules X (t) (mod 2). If Self-replicating pattern generation is one of the
the rule matrix Trules is nonsingular, then we have most interesting topics and research areas in non-
linear science. A motif is considered as a basic
X (t) = (Trules )−1 X (t+1) (mod 2). subpattern. Pattern generation is the process of
transforming copies of the motif about the array
Thus a main problem will be whether the rule (1D), plane (2D) or space (3D) in order to cre-
matrix Trules is invertible or not. If the rule matrix ate the whole repeating pattern with no overlaps
Trules has full rank, then it is invertible, so the 2D and blanks [Gravner & Griffeath, 2011; Packard &
finite CA is reversible, otherwise it is irreversible. Wolfram, 1985; von Neumann, 1966; Wolfram,
Reversibility investigation on the rule matrices 1983]. These patterns have some mathematical
given in Theorems 1–3 is left for another work or properties which make generating algorithm possi-
for the interested readers as open problems. ble. A cellular automaton is a good candidate for

1430002-16
 January 29, 2014 6:59 WSPC/S0218-1274 1430002

Self-Replicating Patterns in 2D Linear Cellular Automata

Int. J. Bifurcation Chaos 2014.24. Downloaded from www.worldscientific.com
by 198.136.31.68 on 12/27/15. For personal use only.

Fig. 17. An application of Rule 171 after 4, 8, 12 and 16 iterations of the first image.

an algorithmic approach used for pattern gener- this kind of trivial self-replicating procedure is eas-
ation. The history of self-replicating pattern pro- ily implemented in any programming language.
grams starts with John von Neumann who contrived Creating an algorithmic approach for generat-
a cellular automaton that took some input, and pro- ing self-replicating patterns of digital images (motif
duced as output that input [von Neumann, 1966]. as in first image) is important and sometimes
However if the automaton itself was given as input, a difficult task. Meanwhile many researchers are
the automaton will reproduce itself as output. faced with many challenges in building and devel-
von Neumann’s automaton program is an exam- oping tiling algorithms such as providing simple
ple of what is known as trivial self-replicating pro- and applicable algorithm to describe high com-
gram because the structure to reproduce is encoded plex patterns models. Growth from simple motif
directly within the program or the input. Hence in 2D CAs can produce self-replicating patterns

Fig. 18. An application of nonsymmetric pattern for Rule 312 after 16 iterations of the first image.

1430002-17
 January 29, 2014 6:59 WSPC/S0218-1274 1430002

S. Uguz et al.

with complicated boundaries (null, periodic, adia- Remark 5.1. In Figs. 13 and 14, one can see that the
batic and reflexive), characterized by a variety of evolutions from steps 15 to 16 change drastically
growth dimensions. The approach given here leads on the number of live cells. For visual inspection,
to an interesting algorithm for generating different the density population always seems to increase
patterns. In this paper we use the CAs with all gradually but in step 16 many cells die quickly
the nearest neighborhoods to generate self-replicate [Chopard & Droz, 1998; Reggia et al., 1998; Mar-
patterns of digital images. For applying 2D null, tinez et al., 2011, 2012; von Neumann, 1966]. Such
periodic, adiabatic and reflexive CA linear rules in evolutions become more important for some appli-
image processing, we take a binary matrix of size cations areas of CA.
(100 × 100) due to computational limitations. We
We present an illustrative example for the case
map each element of the matrix to a unique pixel
n = 4, i.e. the iteration number 24 = 16. It may also
on the screen (writing new MATLAB codes) and we
be observed that the rules belong to the same type
color a pixel white for 0, black for 1 for the matrix
though they create equal number of copies, the dis-
elements. Then we take another image (as a motif)
tributions of these copies differ (see Figs. 6 and 7).
whose size is less than (30 × 30) for which patterns
For example (see Fig. 10), the Rule 415 is of Type 7
are to be generated and put it in the center of the
Int. J. Bifurcation Chaos 2014.24. Downloaded from www.worldscientific.com

for null and periodic boundary case but Type 6 for

binary matrix. This way the image is drawn within
adiabatic and reflexive boundary case, that is, the
an area of (100×100) pixels. To classify with respect
seventh and sixth copies of that image are found in
to their boundary conditions, we add null, periodic,
by 198.136.31.68 on 12/27/15. For personal use only.

the display matrix corresponding to the boundary

adiabatic and reflexive boundary conditions to the
cases. Such copies of the iterating image, may how-
input image. Then we apply 2D CA linear rules on
ever be formed within the display matrix provided
that (100 × 100) matrix and each time the rule is
that the maximum length of the image considered
applied using the changed matrix and a new image
in all directions, does not exceed 30% of the length
is redrawn (Figs. 2–12). In our model, two states, i.e.
of row or column (since rule matrices are a square
black and white, are used to represent the states of
matrix) of the display matrix (here it is 100). More
cells. Therefore the pattern is treated as the devel-
research effort is required to explain why only t = 24
oping and redrawing of black and white patterns.
times repetition of the rules causes the appearance
Then one can give different colors to these patterns
of self-replicating patterns of any arbitrary image.
using different types of graphics packages. The rules
other than the fundamental rules generate different
patterns of the given image. It is observed from the 5.2. From chaotic behavior to order
figures that the self-replicating patterns can be gen- or vice versa
erated only when the number of repetitions is 2n
Figures 13 and 14 present the case that help us to
where (n = 4).
distinguish between the types and have this type
defined as the case from chaos to order. This can be
5.1. Self-replicating patterns : Type seen very easily from these figures. When the iter-
n and multiple copies of any ation numbers increase from t = 1 to t = 15, there
arbitrary image on null, is chaotic behavior of the images. When t = 16, a
kind of miracle happens, and then self-replicating
periodic, adiabatic and
patterns appear in the space diagrams. This repli-
reflexive 2D linear CA cation is valid when the first seed image decorated
It is observed from the corresponding figures that does not exceed 30% of the length of row or column
the rules other than the fundamental ones create of the display matrix.
multiple copies of the given image, the number of
copies being the same as the type number to which
the applied rule belongs. Hence we obtain the max- 5.3. From order behavior to order
imum number of copies an image can have on the If we consider Figs. 15–17, the symmetric beauty
application of such rules which is 9 for null and order is preserved when increasing the iteration
periodic boundary case, because the maximum type number t. This is also valid for the nonsymmet-
number is 9 as found before in null case [Choudhury ric figure as given in Fig. 18. Moreover, there is no
et al., 2005, 2010]. importance for order behaviors of the seed image

1430002-18
 January 29, 2014 6:59 WSPC/S0218-1274 1430002

Self-Replicating Patterns in 2D Linear Cellular Automata

whether its size is larger than 30% of the length of The entire classification for four different type of
row or column of the display matrix. Our examples boundaries is shown in Tables 5 and 6.
of programmatic CAs and repetition of simple rules
can create very nice complex patterns of archety-
pal beauty (see Fig. 16). There is also an important 6.1. Null and periodic boundary
observational result in Fig. 17. If the first image rules
exceeds 30% of the length of row or column of the Remark 6.1. The problem of deciding self-
display matrix, the self-replication pattern when the replicating patterns (i.e. m) for Rule n with NB,
iteration number t reaches 16 does not occur. Also PB, AB, RB algebraically is interesting. This is
behaviors for different boundaries produce different equivalent to determining which Rule n corresponds
shapes when t = 16. Hence we have a classifica- to T ype m classification scheme given in Tables 5
tion device and tables up to self-replicating pattern and 6. Also there is a need for more research effort
number and for the case the seed image is less than to explain why only t = 24 = 16 times iteration of
30% of the display matrix. These will be presented the rules causes the appearance of self-replicating
in the next section. pattern phenomena.
Int. J. Bifurcation Chaos 2014.24. Downloaded from www.worldscientific.com

6. The Classification Types of 2D

CA Linear Rules 6.2. Adiabatic and reflexive
boundary rules
by 198.136.31.68 on 12/27/15. For personal use only.

In this section our aim is to classify 512 linear rules

into different types which we called Type m (see Here the linear CA rules are classified on the basis of
Tables 5 and 6). The natural number m is the num- their capacities in producing multiple similar (self-
ber of self-replicating patterns after some iterations replicating) figures. The relation between Tables 5
of the first image (i.e. see Figs. 2–12). and 6 is summarized in the following remark.
First we studied the patterns being generated
for a given first image (or seed image) for all linear Remark 6.2. In Tables 5 and 6, each pattern is gen-
rules iterating it a fixed number of times (we get erated for a fixed seed by the application of the
replicating images for t = 16). Hence we classified CA rules on each cell in the matrix for tth itera-
the rules on the basis of these generated patterns. tions. The differences in Tables 5 and 6 are observed

Table 5. Null and periodic boundary linear 2D CA rules can be classified based on the natural number of the pattern
generated. Type m means that m copies of the images appear after the first image iterates.

Types Null and Periodic Boundary Rules

Type 1 1, 2, 4, 8, 16, 32, 64, 128, 256

Type 2 18, 20, 34, 66, 68, 72, 80, 132, 136, 144, 192, 257, 260, 264, 272, 288, 320, 3, 5, 6, 9, 10, 12, 17, 24, 33, 36, 40,
48, 65, 129, 257, 258, 384
Type 3 21, 22, 28, 35, 38, 42, 50, 52, 69, 76, 84, 88, 100, 104, 112, 137, 140, 148, 152, 162, 196, 200, 208, 232, 262, 268,
273, 276, 280, 290, 292, 296, 304, 322, 324, 328, 336, 352, 388, 392, 400, 448, 7, 11, 13, 14, 19, 25, 26, 37, 41, 44,
49, 56, 67, 73, 74, 81, 82, 97, 98, 104, 131, 133, 134, 138, 145, 146, 161, 164, 168, 176, 193, 194, 224, 259, 265,
266, 289, 292, 321, 385, 386, 416
Type 4 29, 30, 39, 43, 46, 51, 53, 54, 58, 60, 77, 83, 85, 87, 90, 92, 99, 101, 106, 108, 116, 120, 141, 149, 153, 154, 156,
163, 166, 172, 178, 180, 184, 197, 201, 204, 212, 216, 226, 228, 240, 263, 269, 270, 277, 278, 281, 284, 291, 293,
294, 298, 300, 305, 308, 312, 323, 325, 326, 329, 330, 332, 353, 354, 356, 360, 368, 389, 390, 393, 396, 401, 404,
408, 418, 420, 424, 432, 449, 450, 452, 456, 464, 480, 15, 23, 27, 45, 57, 71, 75, 78, 86, 89, 102, 105, 114, 135,
139, 142, 147, 150, 165, 170, 177, 195, 202, 209, 210, 225, 267, 279, 297, 306, 387, 394, 402, 417
Type 5 31, 47, 55, 59, 61, 62, 79, 91, 103, 108, 109, 110, 115, 117, 118, 121, 122, 124, 143, 151, 155, 157, 158, 171, 173,
174, 181, 185, 186, 188, 199, 203, 205, 206, 211, 213, 214, 217, 218, 220, 227, 229, 230, 233, 234, 236, 241, 242,
244, 248, 271, 279, 283, 285, 286, 295, 301, 302, 303, 307, 309, 310, 313, 314, 316, 327, 331, 333, 334, 339, 341,
342, 345, 346, 348, 355, 357, 358, 361, 362, 364, 369, 370, 372, 376, 391, 395, 397, 398, 403, 405, 406, 409, 410,
412, 419, 421, 422, 425, 426, 428, 433, 434, 436, 440, 453, 454, 457, 458, 460, 465, 466, 468, 472, 481, 482, 484,
488, 496, 107, 167, 179, 451

(Continued)

1430002-19
 January 29, 2014 6:59 WSPC/S0218-1274 1430002

S. Uguz et al.

Table 5. (Continued)

Types Null and Periodic Boundary Rules

Type 6 63, 95, 119, 125, 126, 159, 182, 183, 187, 190, 207, 215, 221, 222, 231, 237, 245, 246, 249, 252, 287, 311, 317,
318, 335, 343, 347, 349, 350, 359, 365, 366, 373, 374, 377, 378, 380, 399, 407, 413, 414, 423, 429, 430, 435, 437,
438, 444, 455, 459, 461, 462, 467, 469, 470, 473, 474, 476, 483, 485, 486, 489, 490, 492, 497, 498, 500, 504, 111,
123, 175, 187, 219, 231, 235, 238, 243, 250, 315, 365, 371, 411, 442, 427, 435, 441
Type 7 127, 191, 223, 247, 253, 254, 319, 351, 367, 375, 379, 381, 382, 415, 431, 439, 445, 446, 463, 471, 475, 477, 478,
487, 491, 493, 494, 499, 501, 502, 505, 506, 508, 239, 251, 443
Type 8 255, 383, 447, 479, 495, 503, 507, 509, 510
Type 9 511

when the different boundaries are applied to the Since rule matrices are necessarily square
fixed seed image. Let us consider for example how matrices (i.e. mn×mn), the nonsingular rule matrix
the pattern for Rule 149 is generated. For Rule called reversible CA deserves to be studied closely
Int. J. Bifurcation Chaos 2014.24. Downloaded from www.worldscientific.com

149, the cells under consideration are highlighted because a nonsingular matrix must produce cyclic
as shown in Fig. 5. Applying this rule on an ini- state transition diagram having enumerable appli-
tial seed produces Fig. 5 at the 16th iteration. Rule cations in different areas such as Pattern Classifica-
by 198.136.31.68 on 12/27/15. For personal use only.

149 is of Type 4 for Null and Periodic boundaries tion, Clustering, Encryption and Decryption, Data
(see Table 5), whereas Rule 149 is Type 3 for Adia- Compression etc. [Martinez et al., 2011, 2012; Stin-
batic and Reflexive boundaries (see Table 6). This son, 2005; Wuensche & Adamatzky, 2006; Wuen-
is easily observed from Fig. 5. sche, 2009].

Table 6. Adiabatic and reflexive boundary linear 2D CA rules can be classified based on the natural number of the
pattern generated.

Types Adiabatic and Reflexive Boundary Rules

Type 1 1, 2, 3, 4, 5, 8, 9, 16, 17, 32, 33, 64, 65, 128, 129, 256, 257
Type 2 6, 7, 10, 11, 12, 13, 18, 19, 20, 21, 24, 25, 34, 35, 36, 37, 40, 41, 48, 49, 66, 67, 68, 69, 72, 73, 80, 81, 96, 97,
130, 131, 132, 133, 136, 137, 144, 145, 160, 161, 192, 193, 258, 259, 260, 261, 264, 265, 272, 273, 288, 289, 320,
321, 384, 385
Type 3 112, 113, 134, 135, 138, 139, 140, 141, 146, 147, 148, 149, 152, 153, 162, 163, 164, 165, 168, 169, 176, 177, 194,
195, 196, 197, 200, 201, 208, 209, 224, 225, 262, 263, 266, 267, 268, 269, 274, 275, 276, 277, 280, 281, 290, 291,
292, 293, 296, 297, 304, 305, 322, 323, 324, 325, 328, 329, 336, 337, 352, 353, 386, 387, 388, 389, 392, 393, 400,
401, 416, 417, 448, 449
Type 4 30, 31, 46, 47, 54, 55, 58, 59, 60, 61, 78, 79, 86, 87, 90, 91, 92, 93, 102, 103, 106, 107, 108, 109, 114, 115, 116,
117, 120, 121, 142, 143, 150, 151, 154, 155, 156, 157, 166, 167, 170, 171, 172, 173, 178, 179, 180, 181, 184, 185,
198, 199, 202, 203, 204, 205, 210, 211, 212, 213, 216, 217, 226, 227, 228, 229, 232, 233, 240, 241, 270, 271, 278,
279, 282, 283, 284, 285, 294, 295, 298, 299, 300, 301, 306, 307, 308, 309, 312, 313, 326, 327, 330, 331, 332, 333,
338, 339, 340, 341, 344, 345, 354, 355, 356, 357, 360, 361, 368, 369, 390, 391, 394, 395, 396, 397, 402, 403, 404,
405, 408, 409, 418, 419, 420, 421, 424, 425, 432, 433, 450, 451, 452, 453, 456, 457, 464, 465, 480, 481
Type 5 62, 63, 94, 95, 110, 111, 118, 119, 122, 123, 124, 125, 158, 159, 174, 175, 182, 183, 186, 187, 188, 189, 190, 191,
206, 207, 214, 215, 218, 219, 220, 221, 230, 231, 234, 235, 236, 237, 242, 243, 244, 245, 248, 249, 286, 287, 302,
303, 310, 311, 314, 315, 316, 317, 334, 335, 342, 343, 346, 347, 348, 349, 358, 359, 362, 363, 364, 365, 370, 371,
372, 373, 376, 377, 398, 399, 406, 407, 410, 411, 412, 413, 422, 423, 426, 427, 428, 429, 434, 435, 436, 437, 440,
441, 454, 455, 458, 459, 460, 461, 466, 467, 468, 469, 472, 473, 482, 483, 484, 485, 488, 489, 496, 497
Type 6 126, 127, 222, 223, 238, 239, 246, 247, 250, 251, 252, 253, 318, 319, 350, 351, 366, 367, 374, 375, 378, 379, 380,
381, 414, 415, 430, 431, 438, 439, 442, 443, 444, 445, 462, 463, 470, 471, 474, 475, 476, 477, 486, 487, 490, 491,
492, 493, 498, 499, 500, 501, 504, 505
Type 7 254, 255, 382, 383, 446, 447, 478, 479, 494, 495, 502, 503, 506, 507, 508, 509
Type 8 510, 511

1430002-20
 January 29, 2014 6:59 WSPC/S0218-1274 1430002

Self-Replicating Patterns in 2D Linear Cellular Automata

7. An Application in Cryptography IV. Run Test: The run test aims to see if the devi-
ation of the number of runs for several lengths from
An important need in applications of cryptography
the expected values is negligible or not.
is to generate a random number of binary bits of
particular length. This is a very difficult problem
since the generation of such sequence of bits relies V. Autocorrelation Test: This test determines
on algorithms and programs that are built system- the correlation between the sequence and noncyclic
atically. Further, a method of deciding the random- shifted version of it.
ness is an important and challenging issue. In order
to solve this problem a method of randomizing the Pseudo random numbers or bits are used for
sequences is needed. In this section we present such several purposes in cryptography but one of the
a method by utilizing the hybrid structure of the 2D main applications is the generation of a key for a
CA studied in the previous sections. Though this is cryptosystem [Stinson, 2005]. The algorithm used in
not a new method, the success of CA on generating a cryptosystem may be very efficient, however if the
pseudo numbers is not always possible. For instance, key is vulnerable to some attacks, then the cipher
if the hybridization is not used, in general, such a will be insecure. Therefore, generating pseudo ran-
Int. J. Bifurcation Chaos 2014.24. Downloaded from www.worldscientific.com

process fails. Further, the success even in the case dom numbers or bits is vital.
of hybridization is still not straight forward. How- CAs are used for pseudo random bit genera-
ever, in this section we prove statistically that a tors as besides some other methods [Martin & Solé,
by 198.136.31.68 on 12/27/15. For personal use only.

suggested specific hybridization is very successful. 2008; Schiff, 2010; Guan & Tan, 2004]. In [Rubio
In order to test such a sequence for randomness we et al., 2004] the use of one-dimensional linear hybrid
have applied five basic tests [Menezes et al., 1996]. CAs as pseudo random bit generators is investi-
In a sequel we present these five basic tests briefly gated. Here in this work, we also show that, two-
with the application under the consideration. dimensional linear hybrid CAs can be used as a
The following basic tests are applied to pseudo random bit generator.
the sequences obtained herein for testing their To this end, we generated 100 sequences of bits
randomness: of length 1024 in a such a way that we evolved a
5 × 5 lattice of cells which are chosen randomly
I. Frequency Test: The aim of this test is to 1024 times and we concatenate a fixed cell of each
determine whether the number of 0’s and 1’s in a time step. The cells were evolved by hybridization
sequence of bits are approximately the same, as we of the rule numbers 109 and 308 respectively. In
would expect for a random sequence. the sequel, 99 of the sequences that we generated
passed the frequency test, all of them passed the
II. Serial Test: The aim of this test is to deter-
serial test, 95 of them passed the poker test, 98 of
mine if the number of occurrences of 00, 01, 10 and
them passed the run test and all of them passed the
11 are approximately the same or not.
autocorrelation test.
III. Poker Test: The poker test aims to deter- Now we present an example to illustrate the
mine if the number of the distinct subsequences of application among the tested sequences that passed
length m are approximately the same or not such all the tests. We use the hexadecimal notation in
that n/m ≥ 5 · 2m . order to save space of a sequence of bits that we
generated and that is as follows:

3C56E72D 5EECC297 286D52A9 6A0D841F CE45E198 EBCE81BB 114109A8 75D9F85F 55612617

52CB4749 517C5AA2 85C440B0 BC4E6C7 C6BB427A EF17A787 6C89279F E7D812C7 2E1CBD0
283E694F D5DFDA8B 18371F59 248E8DFE B9DBA5DA A212A52F A51EB3BC D90D137E
E93573CA 3AB069E9 A150F4EF B1D04A13 2D9AB64B 3DEF449C.
There are 504 zeros and 520 ones in the sequence and the value of the statistic X1 is 0.25.
The number of 00, 01, 10 and 11’s are 236, 267, 267 and 253 respectively and the value of the statistic
X2 is 2.2944.
The number of nonoverlapping subsequences 000, 001, 010, 011, 100, 101, 110 and 111 are 44, 42,
47, 46, 33, 50, 31 and 48 respectively and the value of the statistic X3 is 8.0674.

1430002-21
 January 29, 2014 6:59 WSPC/S0218-1274 1430002

S. Uguz et al.

from the sequence and add them up. If we apply

this random number obtained via this method to
the picture of Lena 19, we get the encrypted image
of Lena 20 and by XORing again we get the original
image 19 back.

8. Conclusion
In this paper, we discuss in theory two-dimensional,
uniform periodic, adiabatic and reflexive boundary
CAs of linear rules and applications of image pro-
cessing. It is seen that CAs theory can be applied
successfully in self-replicating patterns of image
processing. Just a nontrivial self-replicating pat-
tern is shown in the paper (see Fig. 18). We inves-
Fig. 19. Lena’s original image. tigate 2D CA transition matrix rules with these
Int. J. Bifurcation Chaos 2014.24. Downloaded from www.worldscientific.com

boundaries over the binary field Z2 . We also study

The value of the statistic X4 is 6.5407. the applications of image processing corresponding
Choosing d = 8 the value of the statistic X5 to the linear rules of 2D uniform CA with these
by 198.136.31.68 on 12/27/15. For personal use only.

is 0.3764. boundary conditions over Z2 . Properties of the 2D

For a significance level of α = 0.05, the thresh- finite CA over other fields (see [Akın & Siap, 2007])
old values for X1 , X2 , X3 , X4 and X5 are 3.8415, remain to be of great research interest. Some char-
5.9915, 14.0671, 9.4877 and 1.96 [Menezes et al., acterization and applications on a 2D finite CA by
1996]. Hence, this sequence will pass all the tests. using matrix algebra built on Z3 are planned in
This shows statistically that the sequence is a future studies. Also, some results will be analyzed
pseudo number. on the rule numbers 2460N and 2460P [Siap et al.,
Now, in order to see concretely that the 2010]. However after making use of the matrix rep-
sequence is pseudo random, we will encrypt an resentation of 2D CA, an algorithm will be provided
image by using the sequence as a key in such a way to obtain the number of Garden of Eden configura-
that we will consider the matrix of the pixels of the tions for the 2D CA defined by some rules.
image and we consider our key a matrix of the same In future studies the application of two-
size with the matrix of the image and we will bitwise dimensional periodic, adiabatic and reflexive CAs
XOR. Afterwards we will consider the result matrix to the problems of noise removal, border detection
and the transpose of the matrix which we obtained in digital images, also CA with extended neigh-
borhood for epidemic propagation are planned to
be explored with imaging science. Although only
some important primary image transformations are
being investigated for symmetric binary images, one
can consider that the work can extend further for
any other complex image transformations as well as
many colored images (i.e. colors are chosen in Zp for
p > 2 prime number). Our forthcoming research is
continuing in that direction. Finally, there are sev-
eral open questions raised by the authors that may
attract many researchers.

Acknowledgments
The first author thanks Prof. Dr. Ferat Sahin and
especially Dr. Ugur Sahin for the kind hospitality
during the visit at the Rochester Institute of Tech-
Fig. 20. Lena’s encrypted image. nology (RIT). S. Uguz would also like to thank

1430002-22
 January 29, 2014 6:59 WSPC/S0218-1274 1430002

Self-Replicating Patterns in 2D Linear Cellular Automata

The Council of Higher Education (YOK) for the Das, A. K. [1990] “Additive cellular automata: Theory
support of his visit in RIT. The authors wish to and application as a built-in self-test structure,” PhD
thank TUBITAK (Project Number: 110T713) as thesis, I. I. T. Kharagpur, India.
well for their support. We would also like to thank Dihidar, S. K. & Choudhury, P. P. [2004] “Matrix alge-
the anonymous referees for their valuable sugges- braic formulae concerning some exceptional rules of
two dimensional cellular automata,” Inform. Sci. 165,
tions that has lead to an improved version.
91.
Dogaru, R. & Chua, L. O. [1999] “Emergence of uni-
References cellular organisms from a simple generalized cellular
automata,” Int. J. Bifurcation and Chaos 9, 1219–
Adamatzky, A., Martinez, G. J. & Mora, J. C. [2006]
1236.
“Phenomenology of reaction–diffusion binary-state
Dogaru, R. & Chua, L. O. [2000] “Mutations of the game
cellular automata,” Int. J. Bifurcation and Chaos 16,
of life: A generalized cellular automata perspective of
2985–3005.
Akın, H. [2005] “On the directional entropy of Z2 -actions complex adaptive systems,” Int. J. Bifurcation and
generated by additive cellular automata,” Appl. Math. Chaos 10, 1821–1866.
Comput. 170, 339–346. Gravner, J. & Griffeath, D. [2011] “The one-dimensional
exactly 1 cellular automaton: Replication, periodicity,
Int. J. Bifurcation Chaos 2014.24. Downloaded from www.worldscientific.com

Akın, H. & Siap, I. [2007] “On cellular automata over

Galois rings,” Inform. Process. Lett. 103, 24. and chaos from finite seeds,” J. Statist. Phys. 142,
Alvarez, G., Encinas, L. H. & Rey, A. M. [2008] “A mul- 168–200.
tisecret sharing scheme for color images based on cel- Gravner, J., Gliner, G. & Pelfrey, M. [2011] “Replica-
by 198.136.31.68 on 12/27/15. For personal use only.

lular automata,” Inform. Sci. 178, 4382. tion in one-dimensional cellular automata,” Physica D
Bilotta, E., Pantano, P. & Lohn, J. D. [2005] “Emer- 240, 1460–1474.
gent patterning phenomena in 2D cellular automata,” Guan, S. U. & Tan, S. K. [2004] “Pseudorandom
Artif. Life 11, 339–362. number generation with self-programmable cellular
Blackburn, S. R., Murphy, S. & Peterson, K. G. [1997] automata,” IEEE Trans. Computer-Aided Design of
“Comments on theory and applications of cellular Integrated Circuits and Systems 23, 1095–1101.
automata in cryptography,” IEEE Trans. Comput. Hedlund, G. A. [1969] “Endomorphisms and automor-
46, 637. phisms of full shift dynamical system,” Math. Syst.
Chattopadhyay, P., Choudhury, P. P. & Dihidar, S. K. Th. 3, 320.
[1999] “Characterisation of a particular hybrid trans- Inokuchi, S. & Sato, T. [2000] “On limit cycles and
formation of two-dimensional cellular automata,” transient lengths of cellular automata with threshold
Comput. Math. Appl. 38, 207–216. rules,” Bull. Inform. Cybernet. 32, 2360.
Chopard, B. & Droz, M. [1998] Cellular Automata Julian, P. & Chua, L. O. [2002] “Replication properties
Modelling of Physical Systems (Cambridge University of parity cellular automata,” Int. J. Bifurcation and
Press). Chaos 12, 477–494.
Chou, H. H. & Reggia, J. A. [1997] “Emergence of self- Khan, A. R., Choudhury, P. P., Dihidar, K., Mitra,
replicating structures in a cellular automata space,” S. & Sarkar, P. [1997] “VLSI architecture of a cel-
Physica D 110, 252–276. lular automata machine,” Comput. Math. Appl. 33,
Choudhury, P. P., Nayak, B. K., Sahoo, S. & Rath, S. P. 79.
[2005] “Theory and applications of two-dimensional, Khan, A. R., Choudhury, P. P., Dihidar, K. & Verma,
null-boundary, nine-neighborhood, cellular automata R. [1999] “Text compression using two dimensional
linear rules,” Tech. Report No. ASD/2005/4, 13 cellular automata,” Comput. Math. Appl. 37, 115.
arXiv: 0804.2346. Martin, B. & Solé, P. [2008] Pseudo-Random Sequences
Choudhury, P. P., Sahoo, S., Hassan, S. S., Basu, S., Generated by Cellular Automata, Int. Conf. Relations,
Ghosh, D., Kar, D., Ghosh, Ab., Ghosh, Av. & Ghosh, Orders and Graphs: Interactions with Computer Sci-
A. K. [2010] “Classification of cellular automata rules ence (Mahdia, Tunisie).
based on their properties,” Int. J. Comp. Cogn. 8, Martinez, G. J., Adamatzky, A., Stephens, C. R. & Hoe-
50–54. flich, A. F. [2011] “Cellular automaton supercollid-
Chua, L. O. & Yang, L. [1988] “Cellular neural networks: ers,” Int. J. Mod. Phys. C 22, 419–439.
Theory,” IEEE Trans. Circuits Syst. 35, 1257–1272. Martinez, G. J., Adamatzky, A. & Sanz, R. A. [2012]
Chua, L. O. & Mainzer, K. [2011] The Universe as “Complex dynamics of elementary cellular automata
Automaton: From Simplicity and Symmetry to Com- emerging from chaotic rules,” Int. J. Bifurcation and
plexity (Springer). Chaos 22, 1250023.

1430002-23
 January 29, 2014 6:59 WSPC/S0218-1274 1430002

S. Uguz et al.

Menezes, A. J., Oorschot, P. C., Menezes, A. & Van- Siap, I., Akın, H. & Sah, F. [2011a] “Characterization
stone, S. A. [1996] Handbook of Applied Cryptography of two dimensional cellular automata over ternary
(CRC Press). fields,” J. Franklin Instit. 348, 1258.
Mihaljevic, M., Zheng, Y. & Imai, H. [1999] “A family of Siap, I., Akın, H. & Uguz, S. [2011b] “Structure and
fast dedicated one-way hash functions based on linear reversibility of 2D hexagonal cellular automata,”
cellular automata over GF(q),” IEICE Trans. Fund. Comput. Math. Appl. 62, 4161.
E82-A, 40–47. Smith, A., Turney, P. & Ewaschuk, R. [2003] “Self-
Mitra, S. & Kumar, S. [2005] “Fractal replication in time- replicating machines in continuous space with virtual
manipulated one-dimensional cellular automata,” physics,” Artif. Life 9, 21–40.
Compl. Syst. 16, 191–208. Stinson, D. R. [2005] Cryptography: Theory and Practice
Nishinari, K. & Takahashi, D. [2000] “Multi-value cel- (Chapman and Hall/CRC Press, Ontario).
lular automaton models and metastable states in a Uguz, S., Siap, I. & Akın, H. [2013a] “2-dimensional
congested phase,” J. Phys. A 33, 7709. reversible hexagonal cellular automata with periodic
Packard, N. H. & Wolfram, S. [1985] “Two-dimensional boundary,” Acta Physica Polonica A 123, 480–483.
cellular automata,” J. Stat. Phys. 38, 901. Uguz, S., Akın, H. & Siap, I. [2013b] “Reversibility algo-
Reggia, J. A., Chou, H. H. & Lohn, J. D. [1998] rithms for 3-state hexagonal cellular automata with
“Emergence of self-replicating structures in a cellular periodic boundaries,” Int. J. Bifurcation and Chaos
Int. J. Bifurcation Chaos 2014.24. Downloaded from www.worldscientific.com

automata space,” Adv. Comput. 47, 141–183. 23, 1350101.

Rubio, C. F., Encinas, L. H., White, S. H., Rey, A. M. & von Neumann, J. [1966] The Theory of Self-Reproducing
Sanchez, G. R. [2004] “The use of linear hybrid cel- Automata (Univ. of Illinois Press, Urbana, USA).
by 198.136.31.68 on 12/27/15. For personal use only.

lular automata as pseudorandom bit generators in Wolfram, S. [1983] “Statistical mechanics of cellular
cryptography,” Neural Parall. Scient. Comput. 12, automata,” Rev. Mod. Phys. 55, 601.
175. Wuensche, A. & Adamatzky, A. [2006] “On spiral
Schadschneider, A. & Schreckenberg, M. [1993] “Cellular glider-guns in hexagonal cellular automata: Activator-
automaton models and traffic flow,” J. Phys. A 26, inhibitor paradigm,” Int. J. Mod. Phys. C 17, 1009.
679–683. Wuensche, A. [2009] “Cellular automata encryption: The
Schiff, J. L. [2010] Cellular Automata: A Discrete View reverse algorithm, z-parameter and chain-rules,” Par-
of the World (Wiley & Sons). all. Process. Lett. 19, 283.
Siap, I., Akın, H. & Sah, F. [2010] “Garden of eden Ying, Z., Zhong, Y. & Pei-Min, D. [2009] “On behavior
configurations for 2-D cellular automaton with rule of two-dimensional cellular automata with an excep-
2460N,” Inform. Sci. 180, 3562. tional rule,” Inform. Sci. 179, 613.

1430002-24

View publication stats