Theoretical

Computer Science
ELSEVIER Theoretical Computer Science 218 (1999) 325-346

Two-dimensional cellular automata recognizer

Veronique Terrier *
GREYC, Universit& de Caen, Campus 2. 14032 Caen, France

Abstract

We are investigating cellular automata on two-dimensional array as language recognizer. Linear

acceleration for Moore and Von Neumann neighborhood is presented. Relationships with one-
dimensional CAs and Turing machines are considered. Some limitations of the power capabilities
of real-time recognition are shown. @ 1999 Published by Elsevier Science B.V. All rights
reserved.

1. Introduction

Cellular automata appear to be a relevant model for massively parallel computa-

tion. To evaluate their computation capability a lot of interest has been devoted to
one-dimensional CAs as language recognizer. In recent years several papers investi-
gate various types of two-dimensional CAs [ 1,4,5,8]. Here we will investigate some
basic properties of two-dimensional CAs as two-dimensional language recognizer with
parallel input mode and bounded computation. Indeed in a practical point of view two-
dimensional array looks more natural. Clearly on two-dimensional array the behavior
of CAs becomes more complex. For instance with regard to the global properties the
reversibility and smjectivity problems become indecidable in dimension two [6]. About
the language recognition when the input mode is sequential Cole [2] has shown that
the power strictly increases with the dimension of the space. But actually to solve
problems in higher dimensions often consists in extending methods developed for the
dimension one. Here we will generalize techniques used in one-dimensional CAs.
There are several possible definitions of two-dimensional CA recognizers according
to the choice of the neighborhood, the different ways to supply the input and to get the
result. In this paper we will restrict to Moore and Von Neumann neighborhood, with a
parallel input mode where the inputs are supplied in an array rectangular in shape and
with the result of the computation is get on a distinguished cell (more often the upper-
leftmost cell). The definitions are specified in Section 2. In Section 3 we adapt the

* E-mail: [email protected].

0304-3975/99/$-see front matter @ 1999 Published by Elsevier Science B.V. All rights reserved
PII: SO304-3975(98)00329-6
326 V. Terrier I Theoretical Computer Science 218 (1999) 325-346

linear speed-up methods known for one-dimensional CAs to two-dimensional CAs. In

particular for Von Neumann neighborhood this generalization leads to a solution where
the grouped cells overlap each other. In Sections 4 and 5 we compare two-dimensional
CAs with one-dimensional CAs and Turing machines. The last section focuses on real-
time computation and its limitation using counting arguments developed before for one-
dimensional CAs. In particular we present a language not real-time recognizable with
Moore neighborhood which is real-time recognizable with Von Neumann neighborhood.

2. Definitions

A two-dimensional cellular automaton is a two-dimensional array of identical finite

automata (cells) indexed by Z2 and working synchronously. Each cell evolves according
its neighborhood at discrete time step. Formally a two-dimensional CA is a 3-tuple
(S,N, 6) where S is the set of states, N = {(xi, yi ), . . . , (xk, yk)} c Z2 the neighborhood,
6 : Sk + S the transition function. Denoting ((u, u), t) the state of the cell (u, v) at time
t, we have ((u,~~),~)=~(((u+x,,o+Y,),~- l),...,((u+Xk,V+Xk),t-1)).
The two classic neighborhoods are considered in this paper: the Moore neigh-
borhood where N = {(x, v): [1(x,v)ll oo < l}, the Von Neumann neighborhood where
N={(x,Y): tl(x,r)lli = 1).
Here we are interested in CAs as language recognizer. For that purpose we distin-
guish two subsets of S : C and Saccept;C corresponds to the alphabet of the language
and Sac+ is the subset of accepting states. We specify also a distinguished cell, more
often the cell (1 ,l ), which communicates with outside.
In a natural way the two-dimensional languages will be investigated but also to
compare two-dimensional CAs with other one-dimensional models the one-dimensional
languages will be examined. For two-dimensional languages we need the classic defi-
nitions developed for two-dimensional objects. A picture over an alphabet C is a m *n
array of elements of C. The size of the picture is denoted by (m,n). p(i,j), where
1 <i < m and 1 <j <n, denotes the element on line i and column j of the picture p.
Z** denotes the set of all pictures over Z and Cm*” the set of all pictures of size (m,n).
We will consider only parallel input mode: at initial time 0, for 1 d i <n and 1 d j d m,
each element p(i, j) of the input picture p is fed to the cell (i, j). We restrict to bounded
computation, so the other cells remain in a special state # during all the computation.
We say that a CA accepts the picture p in t steps if the distinguished cell enters an ac-
cepting state at time t. Let T be a function from N2 to N. We say that a CA recognizes
the language L in time T if it accepts the pictures p of size (m,n) in time T(m,n). As
in one-dimensional case we define real time as the minimal time needed by the distin-
guished cell to read any particular part of the input. Thus when the distinguished cell
is the cell (l,l), the real time corresponds to the function T(m, n) = max(m, n) - 1
for Moore neighborhood and the function T(m,n) = m + n - 2 for Von Neumann
neighborhood. And for a constant c > 1, T(m, n) = cmax(m, n) (resp. c(m + n)) gives
rise to linear time. CAMoore(T(m,n)) (resp. CAw(T(m,n))) will denote the class of
 V. Terrier I Theoretical Computer Science 218 (1999) 325-346 321

2-dimensional languages recognized in time T(m,n) by a CA with Moore (resp. Von

Neumann) neighborhood.
For one-dimensional language recognition by two-dimensional CAs the first ambigu-
ity is in the way the input words are fed into two-dimensional array. For our practical
purposes we will consider the words are written in a square in a snakelike order man-
ner. So a word of length n will correspond to a picture of size (r&z], [fil ) with the
letters successively written from let? to right and from right to left, and where the last
line is completed with [,/%l’ - 12blank symbols /?.
For example at . . . ~214corresponds to the picture

al a2 a3 a4
a8 aI a6 a5
a9 al0 all al2
B P a14 a13

Let f be a function from N to N. We say that a CA recognizes the language L in time

f if it accepts the words w of length n in time f(n). Thus when the distinguished cell
is the cell (1,l ), the real time corresponds to the function f(n) = [fi] - 1 for Moore
neighborhood and the function f(n) = 2[fil - 2 for Von Neumann neighborhood.
CA ~~~&f(n)) (resp. CA\r~(f(n))) will denote the class of l-dimensional languages
recognized in time f(n) by a CA with Moore (resp. Von Neumann) neighborhood.

3. Linear acceleration

The linear acceleration known for one-dimensional CAs (cf. [3,7]) which establishes
that a language recognized in time f(n) is also recognized in time n+ [(f(n)-n)/k] for
some k could be generalized to two-dimensional CAs. An initial phase (of max(m,n)
steps for Moore neighborhood and m + n - 1 steps for Von Neumann neighborhood)
will consist in compacting the cells by group of k x k cells. After this phase the
CA could work k times faster for Moore neighborhood and (k + 1)/2 times faster for
Von Neumann neighborhood. So a language recognized in time T(m,n) will be also
recognized in time max(m, n) + [( T(m, n) - max(m, n))/kl with Moore neighborhood
and in time m+n-1+2[(T( m,n)-m-n+l)/(k+l)l with Von Neumann neighborhood.

3.1. The Moore neighborhood case

Let A be a CA which recognizes the language L in time T(m,n). We will build a

CA B which recognizes the language L in time max(m, n) + [( T(m, n) - max(m, n))/kl
for some k. The features of the CA B are as described in [7] for the one-dimensional
case: while computing at the same speed as the initial CA A, the CA B performs
grouping and synchronization to stop it and launch an automaton which runs k times
faster than the initial CA A. The grouping process is performed both on the lines and
the columns. The lines grouping process propagates leftwards and is such that at time
328 V. Terrier / Theoretical Computer Science .?I8 (1999) 3.X-346

A(i,l+n-t+Ci-I-n+t)k,t) A(i,k+n-t+(j-1-n+t)k,t)

m-t+1

A(l+m-t+(i-1-m+t)k, A( l+m-t+(i-1-m+t)
l+n-t+(j-I-n+t)k,t) “’ k+n-t+(i-I-n+t)k
A( l+m-t +(i- 1-m+t)kj,t)

B(ij,t) = B (i&t) = :

A(k+m-t +(i-I-m+t)kj,t)
A(k+m-t+(i-1-m+t)k, A(k+m-t+(i- 1-m+t)
I+n-t+(i-1-n+t)k,t) .” k+n-t+(i- 1-n+t)k

mI _

Fig. 1. The grouping process at time t.

t the lines m-t+l,m-t+2,..., m are grouped by k; so to stop it a synchronisation is

required at time m. Symmetrically the columns grouping process propagates upwards
and must be stopped at time n.
We first describe the synchronization processes. Recall that it exists a one- dimen-
sional CA which synchronizes a segment of length n in n-l steps provided the two
extremities be set initially in special states Grea and Gight (see [7]). So on the au-
tomaton B we synchronize each column in order to synchronize all cells at time m
and each line in order to synchronize all cells at time n. For that purpose on each cell
(i,j) one state is devoted to the synchronization of the line i and a second one to the
synchronization of the column j. At time 1 for each cell these two states are set in
the special states Gteft or Ghsht or in a quiescent state according their west, east, north
and south neighbors are in the border state #.
We now describe the grouping process. See Fig. 1. We need the following notations.
A(i, j, t) will denote the state of the cell (i, j) at time t on the initial CA A (in particular
A(i, j, t) is the border state # if i > m or j > n); B(i, j, t) will denote the state of the cell
(i, j) at time t on the CA B.

i if i<m -t and t<m,

Ll,fi( i, t) will represent l+m-t+(i-(l+m-t))k ifi>m-t and t<m,

j
1 +(i- 1)k if t>m,

if j<n -t and tdn,

G&i, t> l+n-t+(j-(I+.-t))k ifj>n-tandtdn,
1 +(j- 1)k if t>n,

Lright(i, t) L1e’(i’
t, if i<m -t,
Ldi, t) + k - 1 if i>m - t,
 V. Terrier/ Theoretical Computer Science 218 (1999) 325-346 329

and

if j<n - t,
ctOp(jT t,
Cbott,,(j, t)
1 C,,(j,t)+k-1 ifj>n-t.

Proposition 1. For any CA A there exists a CA B such that if at time 0 the two
CA A and B are in the same conjiguration then at time t with t <max(m,n), B(i, j, t)
contains the following array of states:

A(htt(i, t>,GopCAt), t) ... A(hii,hdi, t), ctop(j, t), t)

,
A(&n(i, 0, &tdj,t), t) . :’. A&ight(i, t>, ~bottom(j~ t), t)

and from time t >max(m, n) the CA B can perform in one step k steps of the CA A.

Proof. At time 1, &ft(i, 1) is i, Leght(i, 1) is i for i <m and i+k- 1 for i = m, Ctop(j, 1)
is j, Cb,,tiOm(j, 1) is j for j < n and j+k- 1 for j = m. Hence we could define a transition
function such that the site (m,n) whose east and south neighbors are in state # enters
A(m,n, 1) # ... #
# #
#
in state . . ; the rightmost sites (i, n), with i cm, whose east neighbors
. . . ..
# ... #
are in state # enters in state A(i, n, 1)# . . . #; the lowest sites (m, j), with j <n, whose
A(m,j, 1)
#
north neighbors are in state # enters in state . ; the other sites evolve as on

#
the CA A.
At times t dmin(m,n), observe that as Ll&i, t) - 134.&i - 1, t - l), &ight(i, t) +
1 <I%ight(i + 1, t - I), Ctop(j, t) - 1 2 Ctop(j - 1, t - l), Ck?aO,(jy t) + 1 < Cbottodj +
1, t - 1), we have the required information to compute all the states A(u, u, t) with
Lright(i,t)~U~Ll,~(i,t) and ~bottom ( 1,’ t ) <v<C,,,(j,t) on the site (i,j) at time t. And
as Lright(i,t)=Lright(i+l,t-1)-l, ~l,tt(i,t)=~l,tt(i+l,t-l)-l, Cbottom(j~t)=~b&m
(j + 1, t - 1) - 1, Ctop(j, t) = C,,( j + 1, t - 1) - 1, we are able to localize the relevant
states A(u, u, t) with L&i, t) <u <L+ht(i, t) and C,,( j, t) < u < Cboaom(j,t) among all
the states A(u,u,t) with .&(i- 1,t - l)+ l<u<Lright(i+ 1,t - l)- 1 and Ctop(j-
1,t - 1) + 1 <U<Cboaom(j + l,t - 1) - 1 we may compute.
At times t with min(m,n)< t <max(m,n), for symmetry reasons we can suppose
without loss of generality that m Gn. Observe that as L&i, t) - 12Ll,B(i - 1, t -
11, Light(i, t) + 1 dLight(i + 1, t - l), G,( j, t) - 12 Gop(j - 1, t - l), ~bottom(j~ t) +
1 < CboEom(j + 1, t - 1 ), we have the required information to compute all the states
A(u,u,t) with Lleft(i,t)QuQLright(i,t) and C,,(j,t)<u<Cbottom(j,t) on the site (i,j)
at time t. And asLrisht(i,t)=Lrisht(i,t-1)-l, Ll,ft(i,t)=Ll,tt(i,t-1)-l, Cb&&,t)=
330 V. Terrier I Theoretical Computer Science 218 (1999) 325-346

Cbottom(j + 1,t - 1) - 1, Ctop(j,t)=Ctop(j + 1,t - 1) - 1, we are able to determine,

provided the synchronization at time m, the new localization of the relevant states.
From the time t >max(m, n),Ll&i, t) - k =Ll,*(i - 1, t - l), &&(i, t) +k =L+ht(i+
Lt- 1), C,,,(j,t)-k=C,,(j- l,t- 1), Chotto&, t) + k = ~bottdj + 1, t - 1). Thus
we have the required information to compute k steps of the CA A in one step on the
CA B. And the synchronization at time max(m,n) allows B to enter a new behavior.

3.2. The Von Neumann neighborhood case

See Figs. 2-5. For Von Neumann neighborhood the grouping process is performed by
compacting not the lines and the columns but the diagonals. Precisely three grouping
processes will interact: from the cell (m, 1) toward the diagonal i =j, the diagonals
i-j=m-t for t=l,... , m will be grouped by k in m steps; from the cell (1, n)
toward the diagonal i = j, the diagonals j - i = n - t for t = 1, . . . , n will be grouped
by k in n steps; from the cell (m,n) toward the diagonal i + j = 2, the diagonals
i+j=m+n-t+l for t=l,..., m+n-1 willbegroupedbykinm+n-1 steps.
In order to compute at the same speed than the initial CA A, the grouping CA B will
pack together only cells of same parity (cells (i,j) with i+j of same parity). Actually
the grouped cells will overlap. We choose also k odd.
To stop these grouping processes, synchronizations will be required at times m,n
and m + n - 1. For that purpose we synchronize each column in order to synchronize
all cells at time m, each line in order to synchronize all cells at time n and in addition
from time m we synchronize each line in order to synchronize all cells at time m+n- 1.
We will now focus on the grouping process of the diagonals i - j = m - t for
t=l,... ,m without dealing with the other grouping processes. This grouping process
is initiated from the cell (m, l), propagates to the Northeast reaching at time t the
diagonal i-j = m - t and stops at time m on the diagonal i = j. At time t the grouping
process works only on the diagonals i - j = G(with tl of same parity than m - t in
shifting k - 1 diagonals of each k-grouped diagonals to the next one of same parity.
To describe more precisely the process we need the following notations. We denote by
A(i, j, t) the state of the cell (i, j) at time t on the initial CA A; we denote by B(i,j, t)
the state of the cell (i, j) at time t on the grouping CA B. G(i, j, t) denotes A(i, j, t)
if i - j < m - t else the sequence of the k sites A(u, v, t) such that u + u = i + j and
i-j+2~f[i-j-(m-t)]J(k-l)du-vdi-j+2~~[i-j-(m-t)]~(k-l)+
2(k - 1); H(i, j, t) denotes the sequence of the k sites A(u, v, t) such that u + u = i + j
andi-j+2~~[i-j-(m-(t+l))]J(k-l)~u-v~i-j+2~~[i-j-(m-(t+
l))](k- 1)+2(k- 1).

Proposition 2. For any CA A there exists a CA B such that ifat time 0 the two CAs
A and B are in the same conjiguration then at times t <m, B(i, j, t) contains A(i, j, t)
ifi-j<m-t, G(i,j,t) ifi-jam-t and i+j+m+t is odd, G(i,j,t), G(i+l,j,t-
l), H(i,j,t- 1) ifi-jam-t and i+j+m+t is even andfrom time tarn, B(i,j,t)
contains the sites A(u,v, t) with u + v= i +j, max(O,(i -j)k - (k - 1))Qu - u<(i -
j)k + k - 1.
 V. Terrier I Theoretical Computer Science 218 (1999) 325-346

Il. 1) (1. n-t+11 Cl. n

(m-l

(m, 1) (m, n-t+l) (m, t) Cm. n)

Fig. 2. Time t-c min(n,m).

Proof. At time 1 on the site (m, 1) whose both west and south neighbors are in border
state # a wave is initiated which spreads at maximal speed to the north and the east.
So this wave proceeds at time t on the cells (i,j) such that i - j 3 rn - t and is able to
discriminate the parity of i + j + m + t. Then in the case of i - j cm - t the behavior of
the CAB is the same one of the CAA. In the case of i-jam-t+1 and i+j+m+t+l
odd, note that G(i, j, t + 1) deals with the same cells as G(i, j, t). And clearly G(u, 0, t)
with (U - i, u - j) d 1 contain all the required states to compute G(i, j, t + 1). In the case
ofi-jam--t+1 andi+j+m+t+l even, fromH(i,j-l,t-l),G(i+l,j-l,t-1)
and H(i + 1, j, t - 1) we can compute on the cell (i,j) at time t + 1 the sites A(u, u, t)
with u+v=i+j and i-j+2+2[i(i-j-(m-t))J(k-l)<u---<iij+2+
332 V. Terrier I Theoretical Computer Science 218 (1999) 325-346

(1.1) (1. n)

h -1

b-n, 1) (m, n)

Fig. 3. min(n, m) C time t < max(m, n)

2[i(i - j - (m - t))J(k - 1) + 2(k - 1); in addition G(i,j,t) contains the state of the
siteA(u,u,t) with u+v=i+j and u-u=i-j+21i(i-j-(m-t))J(k- 1). So we
get H(i,j,t). Moreover from H(i,j,t) and G(u,u,t) with (U - i,u -j) d 1 we have all
the required states to compute G(i,j, t + 1). Besides G(i + l,j, t - 1) comes from the
south neighbor.
At time m when the synchonization occurs, the process works as before on the cell
(i,j) of odd parity. But on the cells (i,j) of even parity which contain k sites of
the CA A, only (k - 1)/2 (instead k - 1 as before) sites of the CA A are shifted
to the even cells (i - 1,j + 1). Therefore B(i,j,m) contains the sites A(u,u,m) with
 V. Terrier1 Theoretical Computer Science 218 (1999) 325-346 333

(1. m+n-t) (1,n)

(m+n-t,

Fig. 4. max(m,n)<timet<m + n - 1.

u+u=i+j, (i-j)k-(k-l)<u-v<(i-j)k+k-1 ifu-u>OorO<u-u<k-1

if u = v. And after the step m the grouping process stops.

Actually the same process is achieved on the diagonals j - i = n - t for t = 1,. . . , n

from the cell (1, n) toward the diagonal i =j in n steps and on the diagonals i+j = m+
n-t+1 for t=l,... , m + n - 1 from the cell (m, n) toward the diagonal i + j = 2 (cf.
Figs. 2-5). Moreover, a composition (which we do not detail) of the grouping processes
of the diagonals i-j=m-t (t= l,...,m) and i+j=m+n-t+l (t= l,...,m+n-1)
occurs on the sites B(i,j,t) with i-jam-t and i+jam+n-t+l at times t<m, and
another composition of the grouping processes of the diagonals j-i = n-t (t = 1,. . . , n)
334 K Terrier I Theoretical Computer Science 218 (1999) 325-346

b, 1) (m, n)

Fig. 5. time t>m+n- 1

and i+j=m+n-t+l (t= l,..., m+n-1) occurs on the sites B(i,j,t) withj-i>n-t
and i+jam+n--t+l at times t<n.
Consequently, at time m + IZ- 1 B(i,j, t) contains the sites A(u, O,t) such that u + v
and i +j have the same parity, (i -j)k - (k - l)<u - vb(i -j)k + k - 1 and
(i+j-2)k-(k- l)<u+v-2d(i+j-2)k+k- 1. In other words B(i,j,t) contains
the sequence of k2 sites A( 1 + (i - 1)k + LX,1 + (j - 1)k + B,t) with Il(a,P)IIi <k - 1
and a + /3 even. Therefore the site B(i + a, j + p, t) with /l(a, p)II 1<2 contains the sites
A(1 + (i - 1)k + c1,l + (j - 1)k + p,t) with (II(c(,p)IIi 63k - 1 and a + P even) or
(il(a,fi)\\,<2k- 1 and a+8 odd) in particular the sites&l +(i- l)k+ol,l+(j-
l)k + B,t) with II(~I,B)III <2k. H ence from this time, k + 1 steps of the CA A can be
 V. Terrier/ Theorerical Compuier Science 218 (1999) 325-346 335

simulated in 2 steps on the CA B. Actually for any integer s,sk + 1 steps of the CA
A can be simulated in s + 1 steps on the CA B.

Corollary 1. Zf T(m,n)>c(m + n) for any c>l, then CA&T(m,n))=

CA Moore(T(m,n)).

Proof. CA& r(m, n) C CAM,,~~~ (T(m, n)) indeed the Von Neumann neighborhood is
contained in the Moore neighborhood.
CA Moore(T(m, n)) c CAv~(2T(rn, n)) since one step on a Moore CA can be simulated
in two steps on a Von Neumann CA. Let k be an odd integer such that k 3 4c/(c - 1),
it exists since c > 1.
We have

CAv~(2T(m,n)) c CAVN(~ + n + 2)[(2T(m,n) -m - n)/(k + l>l)

according to Section 3.2

c CAm(T(m,n)/c + 4T(m,n)/k) as T(m,n)>c(m + n)

c CAw(T(m,n)) by choice of k.

4. Comparison with one-dimensional CAs

Note that the way the input words are supplied into two-dimensional array will be
determining in the comparison of one- and two-dimensional CAs. Recall that here we
consider the words are written in a square in a snakelike order manner. The following
propositions depend closely on this choice.

4.1. Simulation of a one-dimensional CA by a two-dimensional CA

Proposition 3. Zf the language L is recognized by a one-dimensional CA in time f(n)

then L is recognized by a two-dimensional CA with Von Neumann neighborhood in
time [J7;1 + f(n).

Proof. As the input words are written in a snakelike order, to identify the relevant
neighborhood of each site of the square is simple. For that purpose each site will be
marked with a state indicating its respective left and right neighbors (NW for the sites
with the left neighbor on the north and the right neighbor on the west, and in the same
way EW, ES, WS, WE, NE) (Fig. 6).
This marking process propagates downwards one line by step in the following way.
At time 1, the site (1,l) whose north and east neighbors are in state #, enters in
state NW; the site (1, Ifi] ) whose north and west neighbors are in state #, enters in
state ES; the sites (1, i) with 1 <i < [@I whose north neighbor but not their east or
their west neighbors are in state #, enter in state EW.
336 V. Terrier/ Theoretical Computer Science 218 (1999) 325-346

Fig. 6.

At time i > 1, the sites not marked enter in state WS, WE, NE, NW, EW, ES,
respectively if their north neighbor is in state NW, EW, ES, WS, WE, NE, respectively.
Therefore at time [J;;l all sites are marked.
Parallely at time 1 a synchronization process starts from both ends of each line. So
all cells are synchronized at time [fil. Then from this time the two-dimensional CA
operates as in one-dimensional case.

Corollary 2. If the language L is recognized by a one-dimensional CA in tinze f(n)

then L is recognized by a two-dimensional CA with Von Neumann neighborhood in
time j’(n)/k.

Proof. Indeed in one-dimensional case the minimal time is n, therefore of greater order
than [fil. And according to Section 3.2, we have the desired linear acceleration.

Corollary 3. If the language L is recognized by a one-dimensional CA in time f(n)

then L is recognized by a two-dimensional CA with Moore neighborhood in time
f (n)lk.

4.2. Simulation of a two-dimensional CA by a one-dimensional CA

The following proposition is a special case of a result in [l].

Proposition 4. If the language L is recognized by a two-dimensional CA A (with

Moore or Von Neumann neighborhood) in time f(n) then L is recognized by a
one-dimensional CA B in time 0( ,,hif (n)).

Proof. On the two-dimensional CA A an input word of length n is supplied in a

snakelike order as a picture of size ([fil, [fi]). So the initial phase of the simulation
consists in dividing the working area of the one-dimensional CA B in [+,/6’1 segments
 V. Terrier I Theoretical Computer Science 218 (I 999) 325-346 331

of length [J;zj so that the ith segment of B corresponds to the ith line of A if i
is odd, the reverse of the ith line of A if i is even. For that purpose we distinguish
the leftmost cells of each segments i.e. the cells 1 + i[fil with i = 0,. . . , r&l - 1.
Precisely we construct a CA which distinguishes the sites ( 1 + i r&l, (i - 1)2 + i [J&l ).
The construction is displayed by the Figs. 7 and 8. In parallel a signal end of line is sent
from the leftmost cell n at time 0, it meets the signal P on the section corresponding
to the diagonal t = c - 1 + ( [fil - 1)2. Therefore among the distinguished sites (1 +
i[fil,(i- l)‘+i[fil) we can select the sites on the diagonal t = c- 1 +( [,,/Kl - 1)’
i.e. the sites (1 + irfil,( r&l - 1 )2 + i[fil ). F rom these sites vertical signals are
initiated, they mark the cells 1 + i [fil with i = 0,. . . , r&l - 1. During this initial
phase each input bit remains on its cell and a synchronization process is initiated on
the cell 1 at time 0, in this way the cells are synchronized at time 2n - 1. From this
time the simulation of the step k of the CA A will be done at time 2n - 1-t k( [+I+ 1)
on the CA B in this following way (cf. Fig. 8):
(1) at time 2n - 1 + k( [Jt;l + 1) providing the step k of the CA A is computed the
new states are propagated at maximal speed to the left and to the right;
(2) at the next step 2n+k( [,/El + 1) m
. order to reverse each segment the digits are
sent at maximal speed to the right, bounce on the rightmost cell of the segment and
return at maximal speed to the left, in parallel a synchronization process is initiated
from both ends of each segment;
(3) in this way at time 2n + k( Ifi + 1) + [fil - 1 the synchronization occurs.
Moreover, the ith cell of the jth segment receives the ith states of the (j - 1 )th and
(j + 1)th segments and the (r&i] - i)th state of the jth segment which correspond
to the states of the cells (i,j - l),(i,j),(i,j + 1) (resp. ([fil - i,j - l),( [fil -
i,j), ([fil - i, j + 1)) of the CA A if j + k is even (resp. odd).
Thus at the next step 2n- 1+(k+ 1)( [fi] + 1) we know all the required neighborhood
to compute the new states corresponding to the step k + 1 of the CA A.
In fact the computation of the last n - ([Jill - 1)2 cells are performed on the
segment [fil - 1.

5. Comparison with Turing machine

Here as two-dimensional CAs are restricted to bounded computation, two-dimensional

CAs will have the same power than Turing machines bounded in space n. Now we
describe direct simulations.

5.1. Simulation of a Turing machine working in space n by a two-dimensional CA

Proposition 5. If L is recognized by a Turing machine which works in time f(n) and
space n then L is recognized in time [,,IG] + f(n) by a two-dimensional CA.

Proof. The construction of the two-dimensional CA is based on the usual techniques

[9] where the simulated heads cells remain fixed on the site ( 1,1) and the simulated
tapes are shifted. In order that the simulation is performed in real time, the simulated
 V. Terrier /Theoreticul Computer Science 218 (1999) 325-346

Time

36

Signal P with marks the cell I at times i ’

initialized on the site (1 ,I)
repeats the following moves :
- runs rightwards at maximal speed to Q
- goes to the right cell in one step
- remains one step on the same cell
- returns at maximal speed to the cell I

run at maximal speed to the right

Signal D initialized on the site (3.3)

repeats the following moves :
- goes to the right cell in one step
runs with a slope 2 co rhe next signal C

/ Si nals E initialized on the sites

(i, if I) mtersections of signals P and Q
repeat the following moves :
- remain one step on the same cell
run at maximal speed to the next signal F

Signals F initialized on the sites (i2 i f I,

2i2 3i +I) intersections of the signal C and
signals D, repeat the following moves :
runs with a slope 2 lo rhe next signal E
runs vertically to the next signal C
v

I Space

Fig. 7. Construction of the sites (1 + ik, (i - 1)2 + ik) intersections of the signals C and F.
 V Terrier I Theoretical Computer Science 218 (1999) 325-346 339

computation
of the step 2
synchronization

computation
of the step I
synchronization

jynchronization

I I I I

I I

I1 vertical signals

g
=_ the sites (I+i dn, (i-l)‘+i dn)

0 the diagonal t = c-l + (dn- I)’

I6

Fig. 8
340 V. Terrier I Theoretical Computer Science 218 (1999) 325-346

squares must be grouped. So an initial phase of [,,/Gl steps is required to group the
columns by two to the left and also to exhibit, as in Section 4.1, the trace of the
simulated tapes. As the Turing machine works in space n, this trace is contained in
the bounded area.
Proposition 5 can also be obtained as a consequence of Proposition 3.

5.2. Simulation of a two-dimensional CA by a Turing machine

Proposition 6. Let L be a one-dimensional language recognized in time f(n) by a

two-dimensional CA then L is recognized in time O(nf (n)) and space n by a Turing
machine with two tapes.

Proof. We construct a Turing machine with two tapes, the second tape with two tracks.
On the CA an input word of length n is supplied in a snakelike order as a picture of
size ([&I, [fil ). So the initial phase of the simulation consists in dividing the input
word of length n into [fil blocks of length [Jj n so that the ith block corresponds to
the ith line if i is odd, the reverse of the ith line if i is even. A first scan of the input
permits to compute [J-ln on the second tape. A second scan of the input is required
to mark each i. [fij th letters (for i = 1,. . . , [,,hl ) of the input by *.
So the initial phase takes O(n) steps.
Then the simulation of one step of the CA goes as follows. See Fig. 9. On the
first tape the head scans the input one square by step. On the second tape the head
scans [fil squares successively from left to right and from right to left. During the
left-to-right sweeps it records on the first track the odd blocks (red on the first tape)
and during the right-to-left sweeps it records on the second track the even blocks (red
on the first tape).
By this way at the end of the scan of the ith block on the first tape, we have the
ith line on the upper (resp. lower) track, the (i - I)th line on the lower (resp. upper)
track and the head points to the rightmost (resp. leftmost) square if i is even (resp.
odd). So simultaneously the heads will point to the (j+ 1)th elements of the (i - l)th,
ith, (i + 1)th lines; and if in the state the contents of the squares scanned during the
two last steps (the (j - 1)th and the jth elements of the (i - l)th, ith, (i + 1)th lines)
are recorded we know all the relevant information to compute the jth element of the
ith line at the next step of the CA.
Thus simulating one step of the CA requires n + [fil + 1 steps on the TM and the
lines are shifted [Jt;l + 1 squares rightward. Now it is the odd line which are written
in reverse. So the simulation of the next step is made in the same way but in reverse.

6. Real-time recognition

In this section we will exploit methods, developed before in one-dimensional case

[2, lo] which used equivalence classes and counting arguments to show that some
languages are not real time recognizable.
 V. Terrier I Theoretical Computer Science 218 (1999) 325-346

the even lines in reverse order

$Li-z,l,t+l)(-‘-l(
i, j-2,t+l) (ij-l,t+l) i+lj+l,t) /~--\~[“‘\ (i+2,l,t) i (i+3,l,t) 1 3

1(i+l,l,t) I___f
i+l, j-1,t) (i+lj,t) (i-lj+l,t) /___~i-l,4n,t)l

1 (i,l,t) I___] (i,j-1.0 1 (i&t) 1 (ij+l,t) I___1 (i,+i,t) 1

Fig. 9. Simulation of the line i.

6.1. The Moore neighborhood case

A characteristic of 2-CAs in real time with Moore neighborhood is that on picture of

size (n, n) the input element of the cell (n, n) has only one way (the diagonal) to reach
the distinguished cell( 1,l) and then this element interacts with only O(n) elements
among the n2 elements of the input array. This feature allow us to express a relation
of equivalence. Then we will present a language which will be shown by counting
arguments not to be a real time language for CAs with Moore neighborhood. Finally
we will define a CA with Von Neumann neighborhood able to recognize it in real
time.

Notation. See Fig. 10. Let A4 be a 2-CA with Moore neighborhood with (1,1) as
distinguished cell. We consider the behavior of the CA working in real time on input
pictures of size (m, n). We will use the following notations. For any set U c Z* we
denote by Neig(U) the Moore neighborhood of U and Neig’(U) its tth iterate. Let
A be the set {(x,y):ldx<m,ldy<n} andE,=Neigma”(“*“)-‘-‘({(l,l)})flA denote
the set of the cells at step t which can have an effect on the result of the computation,
i.e. which can affect the cell (1,l) at time max(m, n) - 1.
Let R,(U) = Neig’( U) n Et represent the set of cells which contain at time t the
relevant information regarding the input bits supplied at initial time in U.
A portion of picture p on a set U consists in the elements p(i,j) such that (i,j) E 0:
We denote by p $ c the picture resulting of the concatenation of a portion of picture
p on A/U and a portion of picture c on U.
342 V. Terrier I Theoretical Computer Science 218 (1999) 325-346

(1.11-t)

(u-td

(m-sl)

(m,v-t> (m,n>
Fig. IO.

1 j n/2 n..
I
1

InI2
0
u
L.
5
z
da.
m 0 . . . 0 bin(m-ijf

Fig. 11.The language L.

The relation of equivalence. Note that by definition of R,( U) the states of Neig(R,+t
(U))/R,(U) at time t=O,... ,max(m, n) - 1 are independent of the input bits supplied
in U at time 0. So we could define the following relation of equivalence: two portions
of picture p, pf on A/U are U-equivalent if the two states sequences of the cells
Neig(R,+t (U))/R,( U) at time t = 0,. . , max(m, n) - 2 during the evolution of the CA
on the inputs p and p’ are equal.

Fact 1. If p and p’ are U-equivalent then for all portions of picture c on U, p @ c is

accepted by the CA if and only if pi @c is accepted b_y the CA.

Proof. As the states of R, at time t are function of the states of Neig(R,(U))/R,_I( U)

and the states of Rt_1(U) at time t- 1, if p and p’ are U-equivalent then for all portions
of picture c on U the sequences of states of R,(U) at time t = 1,. . . ,max(m, n) -
1 generated by the CA on the inputs p @ c and p’ @c are equal. In particular, as
R max(m,n)-,
(U) = {( 1, l)} if p and p’ are U-equivalent then for all portions of picture
c on U we have p@c is accepted by the CA if and only if p’@c is accepted by the
CA.
 V. Terrier I Theoretical Computer Science 218 (I 999) 325-346 343

LetL={pE{O,l}**: p is of size (m,n) with m82 (log(n)+2) and n>2 (log(m)+

2) and it exists i, j such that 1 <i <m/2,1 <j <n/2, p(i,j) = 1, p(m, Lzj +
l)= ... = p(m,n-Llog(m-i)]-2)=0,p(m,n-[log(m-i)]-l)... p(m,n-
l)isthebinarynotationofm-i,p([y]+l,n)= ... =p(m-Llog(n-j)J-2,
n) = 0, p(m - llog(n - j)J - 1, n) . . . p(m - 1, n) is the binary notation of
n-j}. See Fig. 11.

Proposition 7. L is not recognizable in real time by 2-CA.9 with Moore neighborhood.

Proof. We consider pictures A of size (n,n) and the set U = {(x,n):x = n - llog(n -
l)] - l,...,n - l}U{(n,y):y=n - llog(n - l)] - l,...,n - l}. Note that the cardi-
nality of Neig(R,( U))/R,_t(U) is lower than 4Llog(n - 1)J + 8. Thus the cardinality
of U:~~Neig(R,(U))/R,-l(U) is lower than (n - 1)(4[log(n - 1)j + 8). So if L is
recognized by a Moore CA in real time whose the number of states is s then there is
at most S(“-t)(4tos(n--1)+s) =2O(“‘%(“))U _equivalence classes for the portions of picture
on AfU.
At each subset E of {(x, y): 1 Gx, y d n/2} we associate the portion of picture pE on
A/U defined by p~(x, y) = 0 if x > n/2 or y > n/2 and for 1 < x, y < n/2 pE(x, y) = 1 if
(x, y) E E, else p~(x, y) = 0. Observe that for all distinct subsets E, F of {(x, y): 1 < X,
y d n/2} there exists integers x, y such that (x, y) belongs to E/F or F/E. Now consider
the portion of picture c on U such that c(n, n - [log(n - l)] - 1) = . . = c(n, n -
llog(n - i)J - 2) = 0, c(n, n - jlog(n - i)J - 1) . . . c(n, n - 1) is the binary notation of
n-i, c(n-llog(n-l)J-l,n)=...=c(n-[log(n-j)]-2,n)=O, c(n-jlog(n-
j)J - 1, n) . . . c(n - 1, n) is the binary notation of n -j. Thus pi $ c belongs to L if and
only if pF $ c does not belong to L. In other words pE and pF are not equivalent. To
conclude note that the number of subsets of {(x, y): 1 d x, y < n/2} is 2”2!4.Hence it
is of order greater than 2°(“‘os(n)).

Proposition 8. L is recognizable in real time by a 2-CA with Von Neumann neigh-

borhood.

Proof. See Fig. 12. From p(m, 151 + l),. . ., p(m,n - 1) = 0.. .O bin(m - i), if 1 < i d
m/2 we have to select the line i. For that purpose we compute bin(m -k) on the right
of the kth line for all k=m - l,..., 1 in the usual way. We consider that initially all
cells are in a quiescent state /?. The process begins on the cell (m - 1, n - 1) which
can be distinguished at time 2 and enters in state 1. Then the CA evolves according
this rules:

n 1 if s=e=l or (e=O’ and s=O, /I),

wce-+c= 0 if e= 1 and s=O, 0’,
s 0’ if s=l and e=O’, /?.

So the tth bit of bin(m - k) is computed on the cell (k,n - t) at time m - k + t.

Simultaneously from the step 1 the lowest line is sent upward, so the element p(m, t)
344 V. Terrier I Theoretical Computer Science 218 (1999) 325-346

i=4

! i-i-i-l

m= 14

Fig. 12.

is known by the cell (k, t) at time m - k + 1. In addition we can distinguish the line
1+ [m/2] and the column 1+ jn/2J by sending signals from both ends of each line and
each column. Thus a comparison process can start on each line k with k < n/2 at time
m - k + 1 from the cell (k, n - 1) and propagates to the right until reaching the column
1 + [n/2]. The comparison succeeds on the line u. And from the site (i, 1 + [n/2] ) a
signal of selection is sent to the right. Inverting the roles of the lines and the columns
the same process is achieved in order to select the column j. In this way the cell (i,j)
is selected at time m - i + n - j. To sent its content to the cell (1,l) requires i + j - 2
steps, hence this content reaches the cell (1,1) at time m + n - 2.

6.2. The Von Neumann case

Here we will restrict to a particular case where the distinguished cell is the cell
(m, 1) for pictures of size (2m - 1, n). We consider the behavior of a 2-CA with Von
Neumann neighborhood working in real time on input pictures of size (2m - 1, n). We
need the following notations.
Let t be an integer less than n. We denote by A the set {(x, y): 1 < x < 2m -
1, 1 < y < n}, by U the set of t cells {( 1, y): n - t < y < n}, by I’ the set of t cells
((2m - 1,~): n - t <y < n}, We focus on the step m - 2. Em_2 =Neig”({(m, l)})=
{(x,y): 1~y,x-y~m-n-l,x+y~m+n+1}denotesthesetofcellsatstep
m - 2 which can have an effect on the result of the computation (i.e. the cell (m, 1) at
time m + n - 2).
 V. Terrier1 Theoretical Computer Science 218 (1999) 325-346 345

Neigme2(U) = {(x, y): 1 < x < m- 1,1 d y < n,n-y < m-n+t-2) (resp. NeigmP2
(V)={(x,y):m+l <x<dm-1,l <y<n,x+y>m+n-t+2})representstheset
of cells at time m - 2 depending on the input bits supplied at time 0 in U (resp. V).
Note that at time m - 2, E,,,_2/Neigm-2(U U V) is independent of the input bits
supplied at initial time in U and V, Neigmu2 (U) is independent of V and Neig. m-2(v)
of U. So we could define the following relation of equivalence: two portions of picture
p, p’ on A/( U U V) are (U, V)-equivalent if
(i) the states at time m - 2 of E,_2/Neig”-2(U U V) of the CA on the inputs p
and p’ are equal;
(ii) for all portions of picture u on U, the states at time m-2 of Em-2 n Neigmw2( U)
of the CA on the inputs p @ u and p’ 6~ u are equal;
(iii) for all portions of picture v on V, the states at time m-2 of Em___2
flNeigmP2( V)
of the CA on the inputs p @ v and p’ @ v are equal.

Fact 2. The number of (U, V)-equivalence classes of portions of pictures on

A/( U U V) is bounded by 2’cn2’).

Proof. Let s be the number of states of the CA. (i) As the cardinal@ of E,,,_JNeigmP2
(U U V) is n + (n - t)(n - t + 1) there is at most s”~(~-~)(~-~~‘) distinguishable pictures
on E,,_2/Neigm-*(U U V). (ii) Note that Neigmm2(U) n Em_2 is composed first for
i=l ,. . . , t of the (n-t+i/2) sites {(y+m-n+t- 1, y): 1 < y < n-t+(i+l)/2) which
depends on the bits supplied at initial time on the i cells ( 1, n - t + 1), . . . , ( 1, n - t + i)
but not on the t-i cells (l,n-t+i+l),..., (l,n), second for 2 < i < j < t and i +j
even of the sites (m - 1 + (j - i)/2,n - t + (i + j)/2) which depend exactly on the
bits supplied at initial time on the j - if 1 cells (1,n - t + i),...,(l,n - t + j). So
the number of distinguishable pictures on Neigmm2 (U) fl Em__2at time m - 2 is at most
n, Si4j s(~-‘+~~‘~J)~’. “;;;:;z s’+jpi = 2c(n2’-tt3). (iii) In the same way the number

of distinguishable pictures on Neigmv2 (U) n Em_-2 at time m - 2 is at most 2c(n2’+t3).

Thus the number of (U, V)-equivalence classes is at most 2c(“+(“-‘)(“-‘+‘). 2c(n2’+r3).
2c(n2’+t3) i.e. 20(“21)+
We present now a language not real-time recognizable.
Let a = [log nl, b = [log 2ml and t = [(a + b)/2].

Let L={pE{O,l}**: p is of size (2m - 1, n) and there exist i, j

such that 1 <i<2m - 1,1 <j<n,

p(i,j)=l,p(l,n-t+l)...p(l,n-t+a) is the binary notation of j,

p(l,n-t+a+l)...p(l,n)p(2m-1,n-t+1)...p(2m-1,n)
is the binary notation of i}.

Proposition 9. L is not recognizable in real time by a 2-CA with Von Neumann

neighborhood whose cell (m, 1) is the distinguished cell.
346 Y. Terrier I Theoretical Computer Science 218 (1999) 325-346

Proof. At each subset E of {(x, y): 1 <x < 2m - 1,1 < y < TZ}we associate the portion
of picture PE on A/(U U V) defined by p~(x, y) = 1 if (x, y) E E else p&x, y) = 0. As
a = [log nj and b = [log 2ml all lines and columns could be encoded. Hence for all
distinct subsets E and F of {(x, y): 1 <x<2m - 1,1 < y 6 n}, PE and pi are not
(U, V)-equivalent. Note that as t = (a + b)/2 the number of (U, V)-equivalence classes
for portions of pictures on A/(U U V) is bounded by 2°(n2’U+b”2).In other part, the
number of subsets of {(x, y): 1 < x < n, 1~ y <2m - 1) is 2”(2m-3). Hence, provided
m = 0(26) is of greater order than n = 0(2a), 2”(2m-3) is of order greater than 2°(n2”+b)‘Z).

References

[1] A.C. Achilles, M. Kutrib, T. Worsch, On relations between arrays of processing elements of different
dimensionality, Parcella 96, Akademie Verlag, Berlin, 1996, pp. 13-20.
[2] S.N. Cole, Real-time computation by n-dimensional iterative arrays of finite-state machine, IEEE Trans.
Comput. C-18 (1969) 349-365.
[3] O.H. Ibarra, S.M. Kim, S. Moran, Sequential machine characterization of trellis and cellular automata
and application, SIAM J. Comput. 14 (1985) 426-447.
[4] O.H. Ibarra, M.A. Palis, Two-dimensional iterative arrays: characterizations and applications, Theoret.
Comput. Sci. 56 (1988) 47-86.
[5] K. moue, A. Nakamura, Some properties of two-dimensional on-line tessalation acceptors, Inform. Sci.
13 (1977) 95-121.
[6] J. Kari, Reversibility of 2D cellular automata is undecidable, Physica D 45 (1990) 379-385.
[7] J. Mazoyer, N. Reimen, A linear speed-up theorem for cellular automata, Theoret. Comput. Sci. 101
(1992) 59-98.
[8] Zs. Roka, Simulations between cellular automata on Cayley graphs, Theoret. Comput. Sci. (1999) to
appear.
[9] A.R. Smith, Real-time language recognition by one-dimensional cellular automata, J. ACM 6 (1972)
233-253.
[IO] V. Terrier, Language not recognizable in real time by one-way celular automata, Theoret. Comput. Sci.
156 (1996) 281-287.