Information Technology Reference
In-Depth Information
such that
g
i
↔ C
i
, where 1
≤ i ≤ m
+
n−
1 (see Fig. 2). We can construct a 2-D
CA
N
=(
Q, δ
2
,w
) such that all cells in
g
i
simulate the
i
th cell
C
i
in real-time
and
N
can fire any
m×n
arrays at time
t
=
T
(
m
+
n−
1) if and only if
M
fires
1-D arrays of length
m
+
n −
1 at time
t
=
T
(
m
+
n −
1), where
δ
2
:
Q
5
→ Q
is the transition function, and
w ∈ Q
is the border state of the array. Note that
the set of internal states of
N
is the same as
M
. The transition function
δ
2
is
constructed as follows:
Type (II):
U
pper-left corner cell
For any state b,c,d
Type (I):
Inner cell
For any state a,b,c,d
2
{Q-{w}}
2
{Q-{w}}
such that
δ
1
(w, b, c) = d :
w
such that
δ
1
(a, b, c) = d :
a
(1)
w
b
c
d
(1)
a
b
c
d
c
c
w
w
w
b
c
d
(2)
(2)
a
b
c
d
w
c
w
a
w
b
w
d
(3)
(3)
a
b
c
d
c
w
a
(4)
w
b
c
d
Type (III):
Lower-right corner cell
For any state a, b, d
c
2
{Q-{w}}
such that
δ
1
(a, b, w) = d:
a
(5)
a
b
w
d
a
c
(1)
a
b
w
d
w
a
(6)
w
b
c
d
w
w
a
b
w
d
(2)
w
w
(7)
a
b
w
d
a
c
w
b
w
d
(3)
w
w
(8)
a
b
c
d
w
a
(9)
w
b
w
d
c
Fig. 3.
Construction of transition rules for 2-D firing squad synchronization algorithm
Let
δ
1
(
a, b, c
)=
d
be any transition rule of
M
, where
a, b, c, d ∈{Q−{w}}
.
Then,
N
has nine transition rules, as shown in Fig. 3 Type (I). The first rule (1)
in Type (I) is used by an inner cell that does not include border cells amongst
its four neighbors. Rules (2)-(7) are used by an inner cell that has a border cell
as its upper, lower, left, right, lower left, or upper right neighbor, respectively.
