Information Technology Reference
In-Depth Information
same time and for the first time. The set of states must be independent of
m
and
n
.
C
1
n
C
2
n
C
14
C
3
n
C
24
C
13
C
mn
C
12
C
23
C
34
g
m
+
n
-1
C
22
C
11
C
33
C
m
4
g
1
g
m
+3
C
21
C
32
C
m
3
g
2
g
m
+2
C
31
C
m
2
g
3
g
m
+1
C
m
1
g
m
C
1
C
2
C
3
C
m
C
m
+1
C
m
+2
C
m
+3
C
m+
n
-1
Fig. 2.
Correspondence between 1-D and 2-D cellular arrays
3 Mapping Scheme for Embedding Any One-Dimensional
Firing Squad Synchronization Algorithm onto
Two-Dimensional Arrays
The proposal is a simple and e
;
cient mapping scheme that enables us to
embed any one-dimensional firing squad synchronization algorithm onto two-
dimensional arrays without introducing additional states. We consider a 2-D ar-
ray of size
m×n
. We divide
mn
cells into
m
+
n−
1 groups
g
k
,1
≤ k ≤ m
+
n −
1,
defined as follows.
g
k
=
{C
i,j
|
(
i −
1)+(
j −
1) =
k −
1
}
, i.e.,
g
1
=
{C
1
,
1
}
,
g
2
=
{C
1
,
2
,C
2
,
1
}
,
g
3
=
{C
1
,
3
,C
2
,
2
,C
3
,
1
}
,...,
g
m
+
n−
1
=
{C
m,n
}
.
Figure 2 shows the division into
m
+
n −
1 groups. For convenience, we define
g
0
=
{C
0
,
0
}
and
g
m
+
n
=
{C
m
+1
,n
+1
}
.
Let
M
=(
Q, δ
1
,w
) be any one-dimensional CA that fires
cells in
T
(
) steps,
where Q is the finite state set of M,
δ
1
:
Q
3
→ Q
is the transition function, and
w ∈ Q
is the state of the right and left ends. We assume that
M
has
m
+
n −
1
cells, denoted by C
i
, where 1
≤ i ≤ m
+
n −
1. For convenience, we assume
that
M
has a left and right end cells, denoted by C
0
and C
m
+
n
, respectively.
Both end cells C
0
and C
m
+
n
always take the end state
w
(
∈ Q
). We consider the
one-to-one correspondence between the
i
th group
g
i
and the
i
th cell
C
i
on
M
