An Efficient Mapping Scheme for Embedding Any One-Dimensional Firing Squad Synchronization Algorithm onto Two-Dimensional Arrays - Cellular Automata - page 74

3. Case x = i, y = 1: The cell C i, 1 has a border cell as its left neighbor. It can
be seen that C 1 ,i− 1 ∈ g i− 1 and C i, 2 ,C i +1 , 1 ∈ g i +1 . From the assumption,
S 1 ,i− 1 = a , S i, 1 = b , S i, 2 = S i +1 , 1 = c . Following rule (4) in Type (I), we
have that S k +1

i, 1 = d . In addition, from the assumptions S i− 1 = a , S i = b ,
S i +1 = c , and δ 1 ( a, b, c )= d , we obtain S k +1 = d . Thus, we have S k +1

i, 1

=

i

S k +1
i

.

Other cases such as i =1, i = n , n +1 ≤ i ≤ m − 1, i = m , m +1 ≤ i ≤
m + n− 2, and i = m + n− 1 can be treated similarly. Thus, we have proved the
lemma.
We see that any configuration on a 1-D CA consisting of m + n − 1 cells
can be mapped onto 2-D m× n arrays. Therefore, when the embedded 1-D CA
fires m + n − 1 cells in T ( m + n − 1) steps, the corresponding 2-D CA fires the
m×n array in T ( m + n− 1) steps. Thus, we can embed any 1-D synchronization
algorithm on 2-D arrays without increasing the number of internal states. We
complete the lemma in the next theorem.

Step:0
1234567

Step:1
1234567

Step:2
1234567

Step:3
1234567

Step:4
1234567

1 G L L L L L L 1 A C L L L L L 1 G B A L L L L 1 G C G G L L L 1 G B A B C L L

2 L L L L L L L 2 C L L L L L L 2 B A L L L L L 2 C G G L L L L 2 B A B C L L L

3 L L L L L L L 3 L L L L L L L 3 A L L L L L L 3 G G L L L L L 3 A B C L L L L

4 L L L L L L L 4 L L L L L L L 4 L L L L L L L 4 G L L L L L L 4 B C L L L L L

5 L L L L L L L 5 L L L L L L L 5 L L L L L L L 5 L L L L L L L 5 C L L L L L L

Step:5
1234567

Step:6
1234567

Step:7
1234567

Step:8
1234567

Step:9
1234567

1 G C G L C A L 1 G B A L A A G 1 G C G L A B B 1 G B A L L B C 1 G C G G L L C

2 C G L C A L L 2 B A L A A G L 2 C G L A B B C 2 B A L L B C C 2 C G G L L C A

3 G L C A L L L 3 A L A A G L L 3 G L A B B C L 3 A L L B C C A 3 G G L L C A A

4 L C A L L L L 4 L A A G L L L 4 L A B B C L L 4 L L B C C A L 4 G L L C A A G

5 C A L L L L L 5 A A G L L L L 5 A B B C L L L 5 L B C C A L L 5 L L C A A G L

Step:10
1234567

Step:11
1234567

Step:12
1234567

Step:13
1234567

Step:14
1234567

1 G B A B C L A 1 G C G L C L A 1 G B A L C L L 1 G C G L C A L 1 G B A L A A C

2 B A B C L A A 2 C G L C L A B 2 B A L C L L B 2 C G L C A L G 2 B A L A A C G

3 A B C L A A B 3 G L C L A B B 3 A L C L L B A 3 G L C A L G C 3 A L A A C G B

4 B C L A A B B 4 L C L A B B A 4 L C L L B A C 4 L C A L G C B 4 L A A C G B L

5 C L A A B B A 5 C L A B B A C 5 C L L B A C B 5 C A L G C B L 5 A A C G B L L

Step:15
1234567

Step:16
1234567

Step:17
1234567

Step:18
1234567

Step:19
1234567

1 G C G L A C B 1 G B A L G B L 1 G C G C G C L 1 G B G B G B G 1 G G G G G G G

2 C G L A C B G 2 B A L G B L G 2 C G C G C L G 2 B G B G B G G 2 G G G G G G G

3 G L A C B G C 3 A L G B L G B 3 G C G C L G C 3 G B G B G G B 3 G G G G G G G

4 L A C B G C L 4 L G B L G B A 4 C G C L G C G 4 B G B G G B G 4 G G G G G G G

5 A C B G C L L 5 G B L G B A L 5 G C L G C G C 5 G B G G B G B 5 G G G G G G G

Step:20
1234567

1 F F F F F F F

2 F F F F F F F

3 F F F F F F F

4 F F F F F F F

5 F F F F F F F

Fig. 4. Snapshots of the proposed 6-state linear-time firing squad synchronization al-
gorithm on rectangular arrays

[Theorem 2] LetAbeany s -state firing synchronization algorithm operating
in T ( n ) steps on 1-D n cells. Then, there exists a 2-D s -state cellular automaton
that can synchronize any m × n rectangular array in T ( m + n − 1) steps.