Original article Biomath 1 (2012), 1209022, 1–6 B f Volume ░, Number ░, 20░░ BIOMATH ISSN 1314-684X Editor–in–Chief: Roumen Anguelov B f BIOMATH h t t p : / / w w w . b i o m a t h f o r u m . o r g / b i o m a t h / i n d e x . p h p / b i o m a t h / Biomath Forum A State-Efficient Zebra-Like Implementation of Synchronization Algorithms for 2D Rectangular Cellular Arrays Hiroshi Umeo∗ and Akira Nomura∗ ∗ Univ. of Osaka Electro-Communication Neyagawa-shi, Hatsu-cho, 18–8, Osaka, 572–8530, Japan Emails: umeo@cyt.osakac.ac.jp, nomura@cyt.osakac.ac.jp Received: 15 July 2012, accepted: 2 September 2012, published: 12 October 2012 Abstract—The firing squad synchronization problem on cellular automata has been studied extensively for more than forty years, and a rich variety of synchronization al- gorithms have been proposed for not only one-dimensional (1D) but two-dimensional (2D) arrays. In the present paper, we propose a simple and state-efficient mapping scheme: zebra-like mapping for implementing 2D synchronization algorithms for rectangular arrays. The zebra-like mapping we propose embeds two types of configurations alternately onto a 2D array like a zebra-like pattern, one configuration is a synchronization configuration of 1D arrays and the other is a stationary configuration which keeps its state unchanged until the final synchronization. It is shown that the mapping gives us a smallest, known at present, implementation of 2D FSSP algorithms for rectangular arrays. The implementation itself has a nice property that the correctness of the constructed transition rule set is clear and transparent. It is shown that there exists a nine- state 2D cellular automaton that can synchronize any (m x n) rectangle in (m+n+max(m,n)-3) steps. Keywords-cellular automaton; FSSP; firing squad syn- chronization problem I. INTRODUCTION We study a synchronization problem that gives a finite-state protocol for synchronizing large scale cellular automata. The synchronization in cellular automata has been known as the firing squad synchronization problem (FSSP, for short) which was originally proposed by J. Myhill in Moore [1964] to synchronize all/some parts of a self-reproducing cellular automaton. The problem has been studied extensively for more than forty years. 1 2 3 n 1 2 3 ... ... ... C11 C12 C13 C1n C21 C22 C23 C31 C32 C2n C33 C3n 4 C14 C24 C34 m ... Cm1 Cm2 Cm3 CmnCm4 .. . .. . .. . .. . .. . ... Fig. 1. A 2D rectangle cellular automaton. In the present paper, we propose a simple and state- efficient mapping scheme: zebra-like mapping for imple- menting 2D synchronization algorithms. The zebra-like mapping we propose embeds two types of configurations alternately onto a 2D array like a zebra-like pattern, one configuration is a synchronization configuration of 1D arrays and the other is a stationary configuration which keeps its state unchanged until the final synchronization. The mapping gives us a smallest, known at present, implementation of 2D FSSP algorithms. Not only the number of states in the implementation is smaller, but the correctness of the constructed transition function with Citation: H. Umeo, A. Nomura, A State-Efficient Zebra-Like Implementation of Synchronization Algorithms for 2D Rectangular Cellular Arrays, Biomath 1 (2012), 1209022, http://dx.doi.org/10.11145/j.biomath.2012.09.022 Page 1 of 6 http://www.biomathforum.org/biomath/index.php/biomath http://dx.doi.org/10.11145/j.biomath.2012.09.022 H. Umeo et al., A State-Efficient Zebra-Like Implementation of Synchronization Algorithms... 2561 rules is clear and transparent. II. FIRING SQUAD SYNCHRONIZATION PROBLEM A. FSSP on 2D Arrays Figure 1 shows a finite two-dimensional (2D) rectan- gular array consisting of m × n cells. Each cell is an identical (except the border cells) finite-state automaton. The array operates in a lock-step mode in such a way that the next state of each cell (except border cells) is determined by both its own present state and the present states of its north, south, east and west neighbors. Thus, we assume the von Neumann-type four nearest neighbors. All cells (soldiers), except the north-west corner cell (general), are initially in the quiescent state at time t = 0 with the property that the next state of a quiescent cell with quiescent neighbors is the quiescent state again. At time t = 0, the north-west corner cell C11 is in the fire-when-ready state, which is the initiation signal for synchronizing the array. The firing squad synchronization problem is to determine a description (state set and next-state function) for cells that ensures all cells enter the fire state at exactly the same time and for the first time. The tricky part of the problem is that the same kind of soldier having a fixed number of states must be synchronized, regardless of the size m × n of the array. The set of states and next state function must be independent of m and n. The problem was first solved by J. McCarthy and M. Minsky who presented a 3n-step algorithm for 1D cellular array of length n. In 1962, the first optimum- time, i.e. (2n − 2)-step, synchronization algorithm was presented by Goto [1962], with each cell having several thousands of states. Mazoyer [1987] developed a six- state synchronization algorithm which, at present, is the algorithm having the fewest states for 1D arrays. On the other hand, a rich variety of synchronization algorithms for 2D rectangular arrays has been proposed. The first optimum-time rectangle synchronization al- gorithm was proposed by Beyer [1969] and Shinahr [1974], independently. Concerning the time optimality of the 2D rectangle synchronization algorithms, the following theorems have been shown. Theorem 1Beyer [1969], Shinahr [1974] There exists no cel- lular automaton that can synchronize any 2D rectangle array of size m×n in less than m + m + max(m, n)−3 steps, where the general is located at one corner of the array. Theorem 2Shinahr [1974] There exists a 28-state cellular automaton that can synchronize any 2D rectangle array of size m×n at exactly m+m+max(m, n)−3 optimum steps, where the general is located at one corner of the array. B. Optimum-Time L-Shaped Mapping Algorithm 1 2 3 4 n 1 2 3 4 m m 1 2 3 4 nm 1 2 3 4 m 3 4 nm 3 4 m nm m 4 nm 4 m 2 3 4 nm 2 3 4 m 1/1 1/11/1 1/15 1/7 1/3 1/31/3 1/1 1/3 1/7 1/1 t = 2m-2 Time t = 0 1/1 t = n -1 t = m-1 1/11/1 m m Gm n t = 2n+m -3 n Fig. 2. L-shaped decomposition of an m × n rectangle cellular automaton and a space-time diagram for the L-shaped base syn- chronization algorithm. A black circle • in a shaded small square represents a general on each Li and a wake-up signal for the synchronization generated by the general is indicated by a horizontal and vertical arrow. The first optimum-time synchronization algorithm de- veloped by Beyer [1969] and Shinahr [1974] for rectan- gle arrays operates as follows: We assume that an initial general is located on C11 on a rectangular array of size m×n. By dividing the entire rectangle array of size m×n into min(m, n) rotated L-shaped 1D arrays, shown in Fig. 2, one treats the rectangle synchronization problem Biomath 1 (2012), 1209022, http://dx.doi.org/10.11145/j.biomath.2012.09.022 Page 2 of 6 http://dx.doi.org/10.11145/j.biomath.2012.09.022 H. Umeo et al., A State-Efficient Zebra-Like Implementation of Synchronization Algorithms... as min(m, n) independent 1D generalized synchroniza- tions with the general located at the bending cell of the L-shaped array. All cells on each L-shaped array fall into a pre-specified synchronization state, simultaneously. We denote the ith (from outside) L-shaped array by Li and its horizontal and vertical segment is denoted by Lhi and Lvi , 1 ≤ i ≤ min(m, n), respectively. See Fig. 2. Concerning the synchronization of Li, it can be easily seen that each general is generated at the cell Cii at time t = 3i − 3, and the general initiates the horizontal (row) and vertical (column) synchronizations on Lhi and Lvi , via a 1D generalized optimum-time synchronization algorithm which can synchronize arrays of length ` with a general on kth cell from left end (from bottom in the L-shaped decomposition) in ` − 2 + max(k, ` − k + 1) optimum steps, where 1 ≤ k ≤ `. Note that the length of Li is `i = m + n − 2i + 1 and the general is on ki = (m − i + 1)th cell from left (bottom) end. For any i, 1 ≤ i ≤ min(m, n), all cells on Li can be synchronized at time t = 3i−3+`i−2+max(ki, `i−ki +1) = m+n+ i−4+max(m−i+1, n−i+1) = m+n+max(m, n)−3. Thus, the rectangle array of size m × n can be synchro- nized at time t = m + n + max(m, n) − 3 in optimum- steps. In Fig. 2 (top), each general is represented by a black circle • in a shaded square and a wake-up signal for the synchronization generated by the general is indicated by a horizontal and vertical arrow. The algorithm itself is very simple and now we are going to discuss its implementation in terms of a 2D cellular automaton. The question is: how many states are required for its realization? Let Q be a set of internal states for the 1D optimum- time generalized synchronization algorithm which is embedded onto a 2D array as a base algorithm. When we implement the algorithm on rectangle arrays based on the scheme above, we usually have to add a direc- tion information to each state in order to simulate the embedded synchronization operations on each horizontal and vertical segment. Thus, approximately, 2 | Q | −1 states are usually required for its independent row and column synchronization operations in order to avoid state mixing. Only a firing state is shared by the two areas. Shinahr [1974] gave a 28-state implementation based on the idea above. C. Zebra-Like Mapping on Square Arrays The proposed mapping for square arrays is basically based on the rotated L-shaped mapping scheme pre- sented in the previous section, however, the mapping onto square arrays consists of two types of configura- tions: one is a one-cell smaller synchronized configu- ration and the other is a filled-in configuration with a stationary state. The stationary state remains unchanged once filled-in by the time before the final synchroniza- tion. Each configuration is mapped alternatively onto an L-shaped array in a zebra fashion. The mapping is referred to as zebra-like mapping. A key idea of the small-state implementation is: • Alternative mapping of two types of configura- tions: A stationary layer separates two consecutive synchronization layers and it allows us to use the same state set for the vertical and horizontal syn- chronization on each layer, helping us to construct a small-state transition rule set for the synchroniza- tion layers. • A one-cell smaller synchronization configura- tion embedded: A one-cell smaller synchronization configuration than the classical L-shaped mapping (Shinahr [1974]) is embedded, where we can save synchronization time by two steps. • A shared pre-firing state: A single state X is shared between an initial general state of the square synchronizer, the stationary state in the stationary layer, and a pre-firing state of the embedded 1D synchronization algorithm used. The state X itself acts as a pre-firing state of the square synchronizer to be constructed. • A simple condition for final synchronization: Any cell in state X, except Cn,n, enters the final synchronization state at the next step if all its neighbors are in state X or the boundary state of the square. The cell Cn,n enters the synchronization state if and only if its north and west cells are in state X and its east and south cells are in the boundary state. A cell in state X that is adjacent to the cell Cn,n is also an exception. These are the only conditions that make cells fire. In our construction we take the Mazoyer’s 6-state 1D synchronization rule as an embedded synchronization algorithm. The set of the 6-states is {G, Q, A, B, C, X}, where G is a general, Q is a quiescent, and X is a firing state, respectively. The other three states A, B and C are auxiliary states, respectively. The seven-state square synchronizer that we construct has the following state set: {G, Q, A, B, C, X, F}, where F is a newly introduced firing state, X is a Biomath 1 (2012), 1209022, http://dx.doi.org/10.11145/j.biomath.2012.09.022 Page 3 of 6 http://dx.doi.org/10.11145/j.biomath.2012.09.022 H. Umeo et al., A State-Efficient Zebra-Like Implementation of Synchronization Algorithms... t = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 1 X Q Q Q Q Q Q Q Q Q Q Q Q 2 Q Q Q Q Q Q Q Q Q Q Q Q Q 3 Q Q Q Q Q Q Q Q Q Q Q Q Q 4 Q Q Q Q Q Q Q Q Q Q Q Q Q 5 Q Q Q Q Q Q Q Q Q Q Q Q Q 6 Q Q Q Q Q Q Q Q Q Q Q Q Q 7 Q Q Q Q Q Q Q Q Q Q Q Q Q 8 Q Q Q Q Q Q Q Q Q Q Q Q Q 9 Q Q Q Q Q Q Q Q Q Q Q Q Q 10 Q Q Q Q Q Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q Q Q Q Q t = 1 1 2 3 4 5 6 7 8 9 10 11 12 13 1 X G Q Q Q Q Q Q Q Q Q Q Q 2 G Q Q Q Q Q Q Q Q Q Q Q Q 3 Q Q Q Q Q Q Q Q Q Q Q Q Q 4 Q Q Q Q Q Q Q Q Q Q Q Q Q 5 Q Q Q Q Q Q Q Q Q Q Q Q Q 6 Q Q Q Q Q Q Q Q Q Q Q Q Q 7 Q Q Q Q Q Q Q Q Q Q Q Q Q 8 Q Q Q Q Q Q Q Q Q Q Q Q Q 9 Q Q Q Q Q Q Q Q Q Q Q Q Q 10 Q Q Q Q Q Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q Q Q Q Q t = 2 1 2 3 4 5 6 7 8 9 10 11 12 13 1 X A C Q Q Q Q Q Q Q Q Q Q 2 A X Q Q Q Q Q Q Q Q Q Q Q 3 C Q Q Q Q Q Q Q Q Q Q Q Q 4 Q Q Q Q Q Q Q Q Q Q Q Q Q 5 Q Q Q Q Q Q Q Q Q Q Q Q Q 6 Q Q Q Q Q Q Q Q Q Q Q Q Q 7 Q Q Q Q Q Q Q Q Q Q Q Q Q 8 Q Q Q Q Q Q Q Q Q Q Q Q Q 9 Q Q Q Q Q Q Q Q Q Q Q Q Q 10 Q Q Q Q Q Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q Q Q Q Q t = 3 1 2 3 4 5 6 7 8 9 10 11 12 13 1 X G B A Q Q Q Q Q Q Q Q Q 2 G X G Q Q Q Q Q Q Q Q Q Q 3 B G Q Q Q Q Q Q Q Q Q Q Q 4 A Q Q Q Q Q Q Q Q Q Q Q Q 5 Q Q Q Q Q Q Q Q Q Q Q Q Q 6 Q Q Q Q Q Q Q Q Q Q Q Q Q 7 Q Q Q Q Q Q Q Q Q Q Q Q Q 8 Q Q Q Q Q Q Q Q Q Q Q Q Q 9 Q Q Q Q Q Q Q Q Q Q Q Q Q 10 Q Q Q Q Q Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q Q Q Q Q t = 4 1 2 3 4 5 6 7 8 9 10 11 12 13 1 X G C G G Q Q Q Q Q Q Q Q 2 G X X C Q Q Q Q Q Q Q Q Q 3 C X X Q Q Q Q Q Q Q Q Q Q 4 G C Q Q Q Q Q Q Q Q Q Q Q 5 G Q Q Q Q Q Q Q Q Q Q Q Q 6 Q Q Q Q Q Q Q Q Q Q Q Q Q 7 Q Q Q Q Q Q Q Q Q Q Q Q Q 8 Q Q Q Q Q Q Q Q Q Q Q Q Q 9 Q Q Q Q Q Q Q Q Q Q Q Q Q 10 Q Q Q Q Q Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q Q Q Q Q t = 5 1 2 3 4 5 6 7 8 9 10 11 12 13 1 X G B A B C Q Q Q Q Q Q Q 2 G X X X C Q Q Q Q Q Q Q Q 3 B X X G Q Q Q Q Q Q Q Q Q 4 A X G Q Q Q Q Q Q Q Q Q Q 5 B C Q Q Q Q Q Q Q Q Q Q Q 6 C Q Q Q Q Q Q Q Q Q Q Q Q 7 Q Q Q Q Q Q Q Q Q Q Q Q Q 8 Q Q Q Q Q Q Q Q Q Q Q Q Q 9 Q Q Q Q Q Q Q Q Q Q Q Q Q 10 Q Q Q Q Q Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q Q Q Q Q t = 6 1 2 3 4 5 6 7 8 9 10 11 12 13 1 X G C G Q C A Q Q Q Q Q Q 2 G X X X C A Q Q Q Q Q Q Q 3 C X X A C Q Q Q Q Q Q Q Q 4 G X A X Q Q Q Q Q Q Q Q Q 5 Q C C Q Q Q Q Q Q Q Q Q Q 6 C A Q Q Q Q Q Q Q Q Q Q Q 7 A Q Q Q Q Q Q Q Q Q Q Q Q 8 Q Q Q Q Q Q Q Q Q Q Q Q Q 9 Q Q Q Q Q Q Q Q Q Q Q Q Q 10 Q Q Q Q Q Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q Q Q Q Q t = 7 1 2 3 4 5 6 7 8 9 10 11 12 13 1 X G B A Q A A G Q Q Q Q Q 2 G X X X X X B Q Q Q Q Q Q 3 B X X G B A Q Q Q Q Q Q Q 4 A X G X G Q Q Q Q Q Q Q Q 5 Q X B G Q Q Q Q Q Q Q Q Q 6 A X A Q Q Q Q Q Q Q Q Q Q 7 A B Q Q Q Q Q Q Q Q Q Q Q 8 G Q Q Q Q Q Q Q Q Q Q Q Q 9 Q Q Q Q Q Q Q Q Q Q Q Q Q 10 Q Q Q Q Q Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q Q Q Q Q t = 8 1 2 3 4 5 6 7 8 9 10 11 12 13 1 X G C G Q A B B C Q Q Q Q 2 G X X X X X X C Q Q Q Q Q 3 C X X G C G G Q Q Q Q Q Q 4 G X G X X C Q Q Q Q Q Q Q 5 Q X C X X Q Q Q Q Q Q Q Q 6 A X G C Q Q Q Q Q Q Q Q Q 7 B X G Q Q Q Q Q Q Q Q Q Q 8 B C Q Q Q Q Q Q Q Q Q Q Q 9 C Q Q Q Q Q Q Q Q Q Q Q Q 10 Q Q Q Q Q Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q Q Q Q Q t = 9 1 2 3 4 5 6 7 8 9 10 11 12 13 1 X G B A Q Q B C C A Q Q Q 2 G X X X X X X C A Q Q Q Q 3 B X X G B A B C Q Q Q Q Q 4 A X G X X X C Q Q Q Q Q Q 5 Q X B X X G Q Q Q Q Q Q Q 6 Q X A X G Q Q Q Q Q Q Q Q 7 B X B C Q Q Q Q Q Q Q Q Q 8 C C C Q Q Q Q Q Q Q Q Q Q 9 C A Q Q Q Q Q Q Q Q Q Q Q 10 A Q Q Q Q Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q Q Q Q Q t = 10 1 2 3 4 5 6 7 8 9 10 11 12 13 1 X G C G G Q Q C A A G Q Q 2 G X X X X X X X X B Q Q Q 3 C X X G C G Q C A Q Q Q Q 4 G X G X X X C A Q Q Q Q Q 5 G X C X X A C Q Q Q Q Q Q 6 Q X G X A X Q Q Q Q Q Q Q 7 Q X Q C C Q Q Q Q Q Q Q Q 8 C X C A Q Q Q Q Q Q Q Q Q 9 A X A Q Q Q Q Q Q Q Q Q Q 10 A B Q Q Q Q Q Q Q Q Q Q Q 11 G Q Q Q Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q Q Q Q Q t = 11 1 2 3 4 5 6 7 8 9 10 11 12 13 1 X G B A B C Q A A B B C Q 2 G X X X X X X X X X C Q Q 3 B X X G B A Q A A G Q Q Q 4 A X G X X X X X B Q Q Q Q 5 B X B X X G B A Q Q Q Q Q 6 C X A X G X G Q Q Q Q Q Q 7 Q X Q X B G Q Q Q Q Q Q Q 8 A X A X A Q Q Q Q Q Q Q Q 9 A X A B Q Q Q Q Q Q Q Q Q 10 B X G Q Q Q Q Q Q Q Q Q Q 11 B C Q Q Q Q Q Q Q Q Q Q Q 12 C Q Q Q Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q Q Q Q Q t = 12 1 2 3 4 5 6 7 8 9 10 11 12 13 1 X G C G Q C Q A B B C C G 2 G X X X X X X X X X C A Q 3 C X X G C G Q A B B C Q Q 4 G X G X X X X X X C Q Q Q 5 Q X C X X G C G G Q Q Q Q 6 C X G X G X X C Q Q Q Q Q 7 Q X Q X C X X Q Q Q Q Q Q 8 A X A X G C Q Q Q Q Q Q Q 9 B X B X G Q Q Q Q Q Q Q Q 10 B X B C Q Q Q Q Q Q Q Q Q 11 C C C Q Q Q Q Q Q Q Q Q Q 12 C A Q Q Q Q Q Q Q Q Q Q Q 13 G Q Q Q Q Q Q Q Q Q Q Q Q t = 13 1 2 3 4 5 6 7 8 9 10 11 12 13 1 X G B A Q C Q Q B C C B A 2 G X X X X X X X X X X X X 3 B X X G B A Q Q B C C A Q 4 A X G X X X X X X C A Q Q 5 Q X B X X G B A B C Q Q Q 6 C X A X G X X X C Q Q Q Q 7 Q X Q X B X X G Q Q Q Q Q 8 Q X Q X A X G Q Q Q Q Q Q 9 B X B X B C Q Q Q Q Q Q Q 10 C X C C C Q Q Q Q Q Q Q Q 11 C X C A Q Q Q Q Q Q Q Q Q 12 B X A Q Q Q Q Q Q Q Q Q Q 13 A X Q Q Q Q Q Q Q Q Q Q Q t = 14 1 2 3 4 5 6 7 8 9 10 11 12 13 1 X G C G Q C A Q Q C B A C 2 G X X X X X X X X X X X X 3 C X X G C G G Q Q C A A C 4 G X G X X X X X X X X B Q 5 Q X C X X G C G Q C A Q Q 6 C X G X G X X X C A Q Q Q 7 A X G X C X X A C Q Q Q Q 8 Q X Q X G X A X Q Q Q Q Q 9 Q X Q X Q C C Q Q Q Q Q Q 10 C X C X C A Q Q Q Q Q Q Q 11 B X A X A Q Q Q Q Q Q Q Q 12 A X A B Q Q Q Q Q Q Q Q Q 13 C X C Q Q Q Q Q Q Q Q Q Q t = 15 1 2 3 4 5 6 7 8 9 10 11 12 13 1 X G B A Q A A G Q G A C B 2 G X X X X X X X X X X X X 3 B X X G B A B C Q A A C B 4 A X G X X X X X X X X X X 5 Q X B X X G B A Q A A G Q 6 A X A X G X X X X X B Q Q 7 A X B X B X X G B A Q Q Q 8 G X C X A X G X G Q Q Q Q 9 Q X Q X Q X B G Q Q Q Q Q 10 G X A X A X A Q Q Q Q Q Q 11 A X A X A B Q Q Q Q Q Q Q 12 C X C X G Q Q Q Q Q Q Q Q 13 B X B X Q Q Q Q Q Q Q Q Q t = 16 1 2 3 4 5 6 7 8 9 10 11 12 13 1 X G C G Q A B B A G C B Q 2 G X X X X X X X X X X X X 3 C X X G C G Q C Q A C B Q 4 G X G X X X X X X X X X X 5 Q X C X X G C G Q A B B A 6 A X G X G X X X X X X C Q 7 B X Q X C X X G C G G Q Q 8 B X C X G X G X X C Q Q Q 9 A X Q X Q X C X X Q Q Q Q 10 G X A X A X G C Q Q Q Q Q 11 C X C X B X G Q Q Q Q Q Q 12 B X B X B C Q Q Q Q Q Q Q 13 Q X Q X A Q Q Q Q Q Q Q Q t = 17 1 2 3 4 5 6 7 8 9 10 11 12 13 1 X G B A Q Q B A C G B Q Q 2 G X X X X X X X X X X X X 3 B X X G B A Q C Q G B Q Q 4 A X G X X X X X X X X X X 5 Q X B X X G B A Q Q B A C 6 Q X A X G X X X X X X C Q 7 B X Q X B X X G B A B C Q 8 A X C X A X G X X X C Q Q 9 C X Q X Q X B X X G Q Q Q 10 G X G X Q X A X G Q Q Q Q 11 B X B X B X B C Q Q Q Q Q 12 Q X Q X A C C Q Q Q Q Q Q 13 Q X Q X C Q Q Q Q Q Q Q Q t = 18 1 2 3 4 5 6 7 8 9 10 11 12 13 1 X G C G G Q G C B G C Q Q 2 G X X X X X X X X X X X X 3 C X X G C G Q C G G C Q Q 4 G X G X X X X X X X X X X 5 G X C X X G C G G Q G C B 6 Q X G X G X X X X X X X X 7 G X Q X C X X G C G Q C G 8 C X C X G X G X X X C A Q 9 B X G X G X C X X A C Q Q 10 G X G X Q X G X A X Q Q Q 11 C X C X G X Q C C Q Q Q Q 12 Q X Q X C X C A Q Q Q Q Q 13 Q X Q X B X G Q Q Q Q Q Q t = 19 1 2 3 4 5 6 7 8 9 10 11 12 13 1 X G B A B A G B Q G B A Q 2 G X X X X X X X X X X X X 3 B X X G B A Q G A G B A Q 4 A X G X X X X X X X X X X 5 B X B X X G B A B A G B Q 6 A X A X G X X X X X X X X 7 G X Q X B X X G B A Q G A 8 B X G X A X G X X X X X X 9 Q X A X B X B X X G B A Q 10 G X G X A X A X G X G Q Q 11 B X B X G X Q X B G Q Q Q 12 A X A X B X G X A Q Q Q Q 13 Q X Q X Q X A X Q Q Q Q Q t = 20 1 2 3 4 5 6 7 8 9 10 11 12 13 1 X G C G B C G C Q G C G C 2 G X X X X X X X X X X X X 3 C X X G C G C G C G C G C 4 G X G X X X X X X X X X X 5 B X C X X G C G B C G C Q 6 C X G X G X X X X X X X X 7 G X C X C X X G C G C G C 8 C X G X G X G X X X X X X 9 Q X C X B X C X X G C G C 10 G X G X C X G X G X X C Q 11 C X C X G X C X C X X Q Q 12 G X G X C X G X G C Q Q Q 13 C X C X Q X C X C Q Q Q Q t = 21 1 2 3 4 5 6 7 8 9 10 11 12 13 1 X G B G B G G B G G B G B 2 G X X X X X X X X X X X X 3 B X X G B G B G B G B G B 4 G X G X X X X X X X X X X 5 B X B X X G B G B G G B G 6 G X G X G X X X X X X X X 7 G X B X B X X G B G B G B 8 B X G X G X G X X X X X X 9 G X B X B X B X X G B G B 10 G X G X G X G X G X X X X 11 B X B X G X B X B X X G Q 12 G X G X B X G X G X G Q Q 13 B X B X G X B X B X Q Q Q t = 22 1 2 3 4 5 6 7 8 9 10 11 12 13 1 X G G G G G G G G G G G G 2 G X X X X X X X X X X X X 3 G X X G G G G G G G G G G 4 G X G X X X X X X X X X X 5 G X G X X G G G G G G G G 6 G X G X G X X X X X X X X 7 G X G X G X X G G G G G G 8 G X G X G X G X X X X X X 9 G X G X G X G X X G G G G 10 G X G X G X G X G X X X X 11 G X G X G X G X G X X A A 12 G X G X G X G X G X A X Q 13 G X G X G X G X G X A Q Q t = 23 1 2 3 4 5 6 7 8 9 10 11 12 13 1 X X X X X X X X X X X X X 2 X X X X X X X X X X X X X 3 X X X X X X X X X X X X X 4 X X X X X X X X X X X X X 5 X X X X X X X X X X X X X 6 X X X X X X X X X X X X X 7 X X X X X X X X X X X X X 8 X X X X X X X X X X X X X 9 X X X X X X X X X X X X X 10 X X X X X X X X X X X X X 11 X X X X X X X X X X X X X 12 X X X X X X X X X X X X X 13 X X X X X X X X X X X X Q t = 24 1 2 3 4 5 6 7 8 9 10 11 12 13 1 F F F F F F F F F F F F F 2 F F F F F F F F F F F F F 3 F F F F F F F F F F F F F 4 F F F F F F F F F F F F F 5 F F F F F F F F F F F F F 6 F F F F F F F F F F F F F 7 F F F F F F F F F F F F F 8 F F F F F F F F F F F F F 9 F F F F F F F F F F F F F 10 F F F F F F F F F F F F F 11 F F F F F F F F F F F F F 12 F F F F F F F F F F F F F 13 F F F F F F F F F F F F F Fig. 3. Snapshots of the optimum-time synchronization process on a 13 × 13 square array. general, and Q is a quiescent state, respectively. The state G is the general state of the embedded synchro- nization. Those states A, B and C are also auxiliary states, respectively. The transition rule set is constructed in such a way that: The initial general on C1,1 in state X generates a new general in state G on the cell C1,2 and C2,1 at time t = 1. The general in state G initiates a synchronization for the following cells {C1,2, C1,3, ..., C1,n} and {C2,1, C3,1, ..., Cn,1}, each of length n − 1. Note that the length of the array where optimum-time synchronization operations are embedded is shorter by one than the usual embedding in section 2. The cells on the segments are constructed to operate so that they simulate the Mazoyer’s optimum-time synchronization operations. All cells on the two horizontal and vertical segments of length n − 1 enter the pre-firing state X at time t = 1 + 2(n − 1) − 2 = 2n − 3. In this way, the first L1 acts as a synchronization layer. At time t = 2, the cell C2,2 takes the state X and it extends an X-arm (a cell segment in state X) in the right and lower direction, respectively, towards the cells {C2,3, C2,4, ..., C2,n} and {C3,2, C4,2, ..., Cn,2}, respectively, each of length n−2. Every cell once entered in state X remains unchanged by the time before it meets a local condition for the synchronization given later. At time t = 2 + n − 2 = n, the filled-in operation with the stationary state X on the second layer is finished. In this way, the second L2 acts as a stationary layer. Concerning the embedding on the odd ith layer, the cell Ci,i takes the stationary state X time t = 2i − 2 and generates a new general in state G on the cell Ci,i+1 and Ci+1,i at time t = 2i − 1. The general in state G initiates a synchronization for the following cells {Ci,i+1, Ci,i+2, ..., Ci,n} and {Ci+1,i, Ci+2,i, ..., Cn,i}, each of length n − i. All cells on the two horizontal and vertical segments of length n − i enter the pre-firing state X at time t = 2i − 1 + 2(n − i) − 2 = 2n − 3. In this way, for odd i, the ith Li acts as a synchronization layer. As for the even ith layer, at time t = 2i − 2, the cell Ci,i takes the state X and it extends the X-arm in the right and lower direction, respectively, towards the cells {Ci,i+1, Ci,i+2, ..., Ci,n} and {Ci+1,i, Ci+2,i, ..., Cn,i}, each of length n − i. Every cell once entered in state X remains unchanged by the time before synchronization. At time t = 2i − 2 + n − i = n + i − 2, the filled-in operation on the ith layer for even i is finished. At time t = 2n − 3, all of the cells, except Cn,n, on the square of size n × n enter the state X, which is a pre-firing state. Thus we have seen: Theorem 3Umeo and Kubo [2010] There exists a seven- state 2D CA that can synchronize any n×n square array in 2n − 2 steps. Figure 3 shows some snapshots of the synchronization process operating in optimum-steps on a 13 × 13 square array. III. ZEBRA-LIKE MAPPING ON RECTANGLE ARRAYS In this section we give three implementations for rectangle synchronization algorithms. As is shown in Fig. 2, a 1D generalized FSSP algorithm is mapped on an L-shaped 1D array, where the cells on the horizontal and vertical segments have to cooperate with each other. Thus, in contrast to the square implementation, two independent, small-size synchronization configurations cannot be implemented on the horizontal and vertical segment on a single synchronization layer in the rectan- gle case. All the implementations given are variants of the zebra-like mapping. The first ten-state implementa- tion is a straightforward implementation of the zebra- like mapping, which yields a non-optimum algorithm. The second 11-state implementation is a variant of the zebra-like mapping where the first synchronization layer L1 and the thereafter layers Li, i ≥ 3 take a different set of synchronization rule set. The third one is a nine- state implementation which regards the marking symbol Biomath 1 (2012), 1209022, http://dx.doi.org/10.11145/j.biomath.2012.09.022 Page 4 of 6 http://dx.doi.org/10.11145/j.biomath.2012.09.022 H. Umeo et al., A State-Efficient Zebra-Like Implementation of Synchronization Algorithms... t = 0 1 2 3 4 5 6 7 8 9 1 G Q Q Q Q Q Q Q Q 2 Q Q Q Q Q Q Q Q Q 3 Q Q Q Q Q Q Q Q Q 4 Q Q Q Q Q Q Q Q Q 5 Q Q Q Q Q Q Q Q Q 6 Q Q Q Q Q Q Q Q Q 7 Q Q Q Q Q Q Q Q Q 8 Q Q Q Q Q Q Q Q Q 9 Q Q Q Q Q Q Q Q Q 10 Q Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q t = 1 1 2 3 4 5 6 7 8 9 1 Q ] Q Q Q Q Q Q Q 2 [ Q Q Q Q Q Q Q Q 3 Q Q Q Q Q Q Q Q Q 4 Q Q Q Q Q Q Q Q Q 5 Q Q Q Q Q Q Q Q Q 6 Q Q Q Q Q Q Q Q Q 7 Q Q Q Q Q Q Q Q Q 8 Q Q Q Q Q Q Q Q Q 9 Q Q Q Q Q Q Q Q Q 10 Q Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q t = 2 1 2 3 4 5 6 7 8 9 1 Q A ] Q Q Q Q Q Q 2 B TX Q Q Q Q Q Q Q 3 [ Q Q Q Q Q Q Q Q 4 Q Q Q Q Q Q Q Q Q 5 Q Q Q Q Q Q Q Q Q 6 Q Q Q Q Q Q Q Q Q 7 Q Q Q Q Q Q Q Q Q 8 Q Q Q Q Q Q Q Q Q 9 Q Q Q Q Q Q Q Q Q 10 Q Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q t = 3 1 2 3 4 5 6 7 8 9 1 Q A Q ] Q Q Q Q Q 2 B X TX Q Q Q Q Q Q 3 Q TX Q Q Q Q Q Q Q 4 [ Q Q Q Q Q Q Q Q 5 Q Q Q Q Q Q Q Q Q 6 Q Q Q Q Q Q Q Q Q 7 Q Q Q Q Q Q Q Q Q 8 Q Q Q Q Q Q Q Q Q 9 Q Q Q Q Q Q Q Q Q 10 Q Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q t = 4 1 2 3 4 5 6 7 8 9 1 Q Q A A ] Q Q Q Q 2 Q X X TX Q Q Q Q Q 3 B X Q Q Q Q Q Q Q 4 B TX Q Q Q Q Q Q Q 5 [ Q Q Q Q Q Q Q Q 6 Q Q Q Q Q Q Q Q Q 7 Q Q Q Q Q Q Q Q Q 8 Q Q Q Q Q Q Q Q Q 9 Q Q Q Q Q Q Q Q Q 10 Q Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q t = 5 1 2 3 4 5 6 7 8 9 1 Q A A A Q ] Q Q Q 2 B X X X TX Q Q Q Q 3 B X TX Q Q Q Q Q Q 4 B X Q Q Q Q Q Q Q 5 Q TX Q Q Q Q Q Q Q 6 [ Q Q Q Q Q Q Q Q 7 Q Q Q Q Q Q Q Q Q 8 Q Q Q Q Q Q Q Q Q 9 Q Q Q Q Q Q Q Q Q 10 Q Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q t = 6 1 2 3 4 5 6 7 8 9 1 Q A A Q A A ] Q Q 2 B X X X X TX Q Q Q 3 B X G Q Q Q Q Q Q 4 Q X Q Q Q Q Q Q Q 5 B X Q Q Q Q Q Q Q 6 B TX Q Q Q Q Q Q Q 7 [ Q Q Q Q Q Q Q Q 8 Q Q Q Q Q Q Q Q Q 9 Q Q Q Q Q Q Q Q Q 10 Q Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q t = 7 1 2 3 4 5 6 7 8 9 1 Q A Q A A A Q ] Q 2 B X X X X X TX Q Q 3 Q X Q ] Q Q Q Q Q 4 B X [ Q Q Q Q Q Q 5 B X Q Q Q Q Q Q Q 6 B X Q Q Q Q Q Q Q 7 Q TX Q Q Q Q Q Q Q 8 [ Q Q Q Q Q Q Q Q 9 Q Q Q Q Q Q Q Q Q 10 Q Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q t = 8 1 2 3 4 5 6 7 8 9 1 Q Q A A A Q A A C 2 Q X X X X X X TX Q 3 B X Q A ] Q Q Q Q 4 B X B TX Q Q Q Q Q 5 B X [ Q Q Q Q Q Q 6 Q X Q Q Q Q Q Q Q 7 B X Q Q Q Q Q Q Q 8 B TX Q Q Q Q Q Q Q 9 [ Q Q Q Q Q Q Q Q 10 Q Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q t = 9 1 2 3 4 5 6 7 8 9 1 Q A A A Q A A [ C 2 B X X X X X X X TX 3 B X Q A Q ] Q Q Q 4 B X B X TX Q Q Q Q 5 Q X Q TX Q Q Q Q Q 6 B X [ Q Q Q Q Q Q 7 B X Q Q Q Q Q Q Q 8 B X Q Q Q Q Q Q Q 9 Q TX Q Q Q Q Q Q Q 10 [ Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q t = 10 1 2 3 4 5 6 7 8 9 1 Q A A Q A A [ ] C 2 B X X X X X X X X 3 B X Q Q A A ] Q Q 4 Q X Q X X TX Q Q Q 5 B X B X Q Q Q Q Q 6 B X B TX Q Q Q Q Q 7 B X [ Q Q Q Q Q Q 8 Q X Q Q Q Q Q Q Q 9 B X Q Q Q Q Q Q Q 10 B TX Q Q Q Q Q Q Q 11 [ Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q t = 11 1 2 3 4 5 6 7 8 9 1 Q A Q A A [ B [ C 2 B X X X X X X X X 3 Q X TX A A A Q ] Q 4 B X B X X X TX Q Q 5 B X B X TX Q Q Q Q 6 B X B X Q Q Q Q Q 7 Q X Q TX Q Q Q Q Q 8 B X [ Q Q Q Q Q Q 9 B X Q Q Q Q Q Q Q 10 B X Q Q Q Q Q Q Q 11 Q TX Q Q Q Q Q Q Q 12 [ Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q t = 12 1 2 3 4 5 6 7 8 9 1 Q Q A A [ Q B [ C 2 Q X X X X X X X X 3 B X Q A A Q A A C 4 B X B X X X X TX Q 5 B X B X G Q Q Q Q 6 Q X Q X Q Q Q Q Q 7 B X B X Q Q Q Q Q 8 B X B TX Q Q Q Q Q 9 B X [ Q Q Q Q Q Q 10 Q X Q Q Q Q Q Q Q 11 B X Q Q Q Q Q Q Q 12 B TX Q Q Q Q Q Q Q 13 C Q Q Q Q Q Q Q Q t = 13 1 2 3 4 5 6 7 8 9 1 Q A A [ B B G [ C 2 B X X X X X X X X 3 B X Q A Q A A [ C 4 B X B X X X X X TX 5 Q X Q X Q ] Q Q Q 6 B X B X [ Q Q Q Q 7 B X B X Q Q Q Q Q 8 B X B X Q Q Q Q Q 9 Q X Q TX Q Q Q Q Q 10 B X [ Q Q Q Q Q Q 11 B X Q Q Q Q Q Q Q 12 ] X Q Q Q Q Q Q Q 13 C TX Q Q Q Q Q Q Q t = 14 1 2 3 4 5 6 7 8 9 1 Q A [ Q B B G [ C 2 B X X X X X X X X 3 B X Q Q A A [ ] C 4 Q X Q X X X X X X 5 B X B X Q A ] Q Q 6 B X B X B TX Q Q Q 7 B X B X [ Q Q Q Q 8 Q X Q X Q Q Q Q Q 9 B X B X Q Q Q Q Q 10 B X B TX Q Q Q Q Q 11 ] X [ Q Q Q Q Q Q 12 [ X Q Q Q Q Q Q Q 13 C X Q Q Q Q Q Q Q t = 15 1 2 3 4 5 6 7 8 9 1 Q [ B B Q B G [ C 2 B X X X X X X X X 3 Q X TX A A [ B [ C 4 B X B X X X X X X 5 B X B X Q A Q ] Q 6 B X B X B X TX Q Q 7 Q X Q X Q TX Q Q Q 8 B X B X [ Q Q Q Q 9 B X B X Q Q Q Q Q 10 ] X B X Q Q Q Q Q 11 A X Q TX Q Q Q Q Q 12 ] X [ Q Q Q Q Q Q 13 C X Q Q Q Q Q Q Q t = 16 1 2 3 4 5 6 7 8 9 1 [ Q B B B [ G [ C 2 Q X X X X X X X X 3 B X Q A [ Q B [ C 4 B X B X X X X X X 5 B X B X Q Q A A C 6 Q X Q X Q X X TX Q 7 B X B X B X Q Q Q 8 B X B X B TX Q Q Q 9 ] X B X [ Q Q Q Q 10 Q X Q X Q Q Q Q Q 11 A X B X Q Q Q Q Q 12 ] X B TX Q Q Q Q Q 13 C X C Q Q Q Q Q Q t = 17 1 2 3 4 5 6 7 8 9 1 B B Q B B [ B [ C 2 [ X X X X X X X X 3 B X Q [ B B G [ C 4 B X B X X X X X X 5 Q X Q X TX A A [ C 6 B X B X B X X X TX 7 B X B X B X TX Q Q 8 ] X B X B X Q Q Q 9 A X Q X Q TX Q Q Q 10 A X B X [ Q Q Q Q 11 G X B X Q Q Q Q Q 12 ] X ] X Q Q Q Q Q 13 C X C TX Q Q Q Q Q t = 18 1 2 3 4 5 6 7 8 9 1 B B B Q B [ B [ C 2 [ X X X X X X X X 3 B X [ Q B B G [ C 4 Q X Q X X X X X X 5 B X B X Q A [ ] C 6 B X B X B X X X X 7 ] X B X B X G Q Q 8 Q X Q X Q X Q Q Q 9 A X B X B X Q Q Q 10 A X B X B TX Q Q Q 11 G X ] X [ Q Q Q Q 12 ] X [ X Q Q Q Q Q 13 C X C X Q Q Q Q Q t = 19 1 2 3 4 5 6 7 8 9 1 B B B B G [ B [ C 2 [ X X X X X X X X 3 G X B B Q B G [ C 4 B X [ X X X X X X 5 B X B X Q [ B [ C 6 ] X B X B X X X X 7 A X Q X Q X Q ] Q 8 A X B X B X [ Q Q 9 Q X B X B X Q Q Q 10 A X ] X B X Q Q Q 11 G X A X Q TX Q Q Q 12 ] X ] X [ Q Q Q Q 13 C X C X Q Q Q Q Q t = 20 1 2 3 4 5 6 7 8 9 1 B B B B G Q B [ C 2 Q X X X X X X X X 3 G X B B B [ G [ C 4 B X [ X X X X X X 5 ] X B X [ Q B [ C 6 Q X Q X Q X X X X 7 A X B X B X Q A C 8 A X B X B X B TX Q 9 A X ] X B X [ Q Q 10 ] X Q X Q X Q Q Q 11 G X A X B X Q Q Q 12 ] X ] X B TX Q Q Q 13 C X C X C Q Q Q Q t = 21 1 2 3 4 5 6 7 8 9 1 Q B B B G B G [ C 2 B X X X X X X X X 3 G X B B B [ B [ C 4 ] X [ X X X X X X 5 A X G X B B G [ C 6 A X B X [ X X X X 7 Q X B X B X Q [ C 8 A X ] X B X B X TX 9 A X A X Q X Q TX Q 10 ] X A X B X [ Q Q 11 A X G X B X Q Q Q 12 ] X ] X ] X Q Q Q 13 C X C X C TX Q Q Q t = 22 1 2 3 4 5 6 7 8 9 1 B Q B B G B G [ C 2 B X X X X X X X X 3 C X B B B [ B [ C 4 Q X Q X X X X X X 5 A X G X B B G [ C 6 A X B X [ X X X X 7 A X ] X B X [ ] C 8 Q X Q X Q X Q X X 9 A X A X B X B X Q 10 ] X A X B X B TX Q 11 A X G X ] X [ Q Q 12 ] X ] X [ X Q Q Q 13 C X C X C X Q Q Q t = 23 1 2 3 4 5 6 7 8 9 1 B B Q B G B G [ C 2 ] X X X X X X X X 3 C X Q B B [ B [ C 4 [ X B X X X X X X 5 Q X G X B B G [ C 6 A X ] X [ X X X X 7 A X A X G X B [ C 8 A X A X B X [ X X 9 G X Q X B X B X TX 10 ] X A X ] X B X Q 11 A X G X A X Q TX Q 12 ] X ] X ] X [ Q Q 13 C X C X C X Q Q Q t = 24 1 2 3 4 5 6 7 8 9 1 ] B B [ G B G [ C 2 [ X X X X X X X X 3 C X B Q B [ B [ C 4 ] X B X X X X X X 5 [ X C X B B G [ C 6 Q X Q X Q X X X X 7 A X A X G X B [ C 8 A X A X B X [ X X 9 G X A X ] X B X G 10 Q X ] X Q X Q X Q 11 A X G X A X B X Q 12 ] X ] X ] X B TX Q 13 C X C X C X C Q Q t = 25 1 2 3 4 5 6 7 8 9 1 A ] B [ B B G [ C 2 ] X X X X X X X X 3 C X B B G [ B [ C 4 [ X ] X X X X X X 5 B X C X Q B G [ C 6 [ X [ X B X X X X 7 Q X Q X G X B [ C 8 A X A X ] X [ X X 9 G X A X A X G X C 10 A X ] X A X B X [ 11 G X A X G X B X Q 12 ] X ] X ] X ] X Q 13 C X C X C X C TX Q t = 26 1 2 3 4 5 6 7 8 9 1 A Q ] [ B B G [ C 2 ] X X X X X X X X 3 C X ] B G Q B [ C 4 [ X [ X X X X X X 5 B X C X B [ G [ C 6 Q X ] X B X X X X 7 [ X [ X C X B [ C 8 ] X Q X Q X Q X X 9 G X A X A X G X C 10 A X ] X A X B X ] 11 G X A X G X ] X [ 12 ] X ] X ] X [ X Q 13 C X C X C X C X Q t = 27 1 2 3 4 5 6 7 8 9 1 G A A C B B G [ C 2 ] X X X X X X X X 3 C X A ] G B G [ C 4 [ X ] X X X X X X 5 G X C X B [ B [ C 6 B X [ X ] X X X X 7 B X B X C X G [ C 8 C X [ X [ X B X X 9 A X G X Q X G X C 10 A X ] X A X ] X [ 11 G X A X G X A X B 12 ] X ] X ] X ] X [ 13 C X C X C X C X Q t = 28 1 2 3 4 5 6 7 8 9 1 G A [ C ] B G [ C 2 ] X X X X X X X X 3 C X A Q C B G [ C 4 [ X ] X X X X X X 5 G X C X ] [ B [ C 6 B X [ X [ X X X X 7 ] X B X C X G [ C 8 C X Q X ] X B X X 9 [ X C X [ X C X C 10 A X Q X ] X Q X [ 11 G X A X G X A X B 12 ] X ] X ] X ] X Q 13 C X C X C X C X C t = 29 1 2 3 4 5 6 7 8 9 1 G [ ] C [ ] G [ C 2 ] X X X X X X X X 3 C X G [ C ] G [ C 4 [ X ] X X X X X X 5 G X C X G C B [ C 6 ] X [ X ] X X X X 7 [ X G X C X G [ C 8 C X ] X [ X ] X X 9 ] X C X G X C X C 10 [ X [ X C X [ X [ 11 G X G X A X G X G 12 ] X ] X ] X ] X ] 13 C X C X C X C X ] t = 30 1 2 3 4 5 6 7 8 9 1 C ] [ C ] [ C [ C 2 ] X X X X X X X X 3 C X C [ C ] C [ C 4 [ X ] X X X X X X 5 C X C X [ C ] [ C 6 [ X [ X ] X X X X 7 ] X C X C X C [ C 8 C X ] X [ X ] X X 9 [ X C X ] X C X C 10 ] X [ X C X [ X [ 11 C X C X [ X C X C 12 ] X ] X ] X ] X Q 13 C X C X C X C X [ t = 31 1 2 3 4 5 6 7 8 9 1 C C C C C C C C C 2 C X X X X X X X X 3 C X C C C C C C C 4 C X C X X X X X X 5 C X C X C C C C C 6 C X C X C X X X X 7 C X C X C X C C C 8 C X C X C X C X X 9 C X C X C X C X C 10 C X C X C X C X C 11 C X C X C X C X C 12 C X C X C X C X C 13 C X C X C X C X C t = 32 1 2 3 4 5 6 7 8 9 1 X X X X X X X X X 2 X X X X X X X X X 3 X X X X X X X X X 4 X X X X X X X X X 5 X X X X X X X X X 6 X X X X X X X X X 7 X X X X X X X X X 8 X X X X X X X X X 9 X X X X X X X X X 10 X X X X X X X X X 11 X X X X X X X X X 12 X X X X X X X X X 13 X X X X X X X X X t = 33 1 2 3 4 5 6 7 8 9 1 F F F F F F F F F 2 F F F F F F F F F 3 F F F F F F F F F 4 F F F F F F F F F 5 F F F F F F F F F 6 F F F F F F F F F 7 F F F F F F F F F 8 F F F F F F F F F 9 F F F F F F F F F 10 F F F F F F F F F 11 F F F F F F F F F 12 F F F F F F F F F 13 F F F F F F F F F Fig. 4. Snapshots of the non-optimum-time ten-state synchroniza- tion process on a 13 × 9 rectangular array. used in the recursive division as the pre-firing state, making the algorithm work in optimum-steps. Those three implementations are stated in Theorems 4, 5 and 6. Their proofs are omitted due to the limited space avai- lable. Some snapshots of the synchronization processes in those three implementations are given in Figures 4, 5, and 6. Theorem 4 There exists a ten-state 2D CA that can synchronize any m × n rectangle arrays in m + n + max(m, n) − 2 non-optimum steps. Theorem 5 There exists an eleven-state 2D CA that can synchronize any m × n rectangle arrays in m + n + max(m, n) − 3 optimum steps. Theorem 6 There exists a nine-state 2D CA that can synchronize any m × n rectangle arrays in m + n + max(m, n) − 3 optimum steps. t = 0 1 2 3 4 5 6 7 8 9 1 G Q Q Q Q Q Q Q Q 2 Q Q Q Q Q Q Q Q Q 3 Q Q Q Q Q Q Q Q Q 4 Q Q Q Q Q Q Q Q Q 5 Q Q Q Q Q Q Q Q Q 6 Q Q Q Q Q Q Q Q Q 7 Q Q Q Q Q Q Q Q Q 8 Q Q Q Q Q Q Q Q Q 9 Q Q Q Q Q Q Q Q Q 10 Q Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q t = 1 1 2 3 4 5 6 7 8 9 1 Q GX Q Q Q Q Q Q Q 2 [ Q Q Q Q Q Q Q Q 3 Q Q Q Q Q Q Q Q Q 4 Q Q Q Q Q Q Q Q Q 5 Q Q Q Q Q Q Q Q Q 6 Q Q Q Q Q Q Q Q Q 7 Q Q Q Q Q Q Q Q Q 8 Q Q Q Q Q Q Q Q Q 9 Q Q Q Q Q Q Q Q Q 10 Q Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q t = 2 1 2 3 4 5 6 7 8 9 1 Q A ] Q Q Q Q Q Q 2 B GX Q Q Q Q Q Q Q 3 [ Q Q Q Q Q Q Q Q 4 Q Q Q Q Q Q Q Q Q 5 Q Q Q Q Q Q Q Q Q 6 Q Q Q Q Q Q Q Q Q 7 Q Q Q Q Q Q Q Q Q 8 Q Q Q Q Q Q Q Q Q 9 Q Q Q Q Q Q Q Q Q 10 Q Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q t = 3 1 2 3 4 5 6 7 8 9 1 Q A Q ] Q Q Q Q Q 2 B X GX Q Q Q Q Q Q 3 Q GX Q Q Q Q Q Q Q 4 [ Q Q Q Q Q Q Q Q 5 Q Q Q Q Q Q Q Q Q 6 Q Q Q Q Q Q Q Q Q 7 Q Q Q Q Q Q Q Q Q 8 Q Q Q Q Q Q Q Q Q 9 Q Q Q Q Q Q Q Q Q 10 Q Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q t = 4 1 2 3 4 5 6 7 8 9 1 Q Q A A ] Q Q Q Q 2 Q X X GX Q Q Q Q Q 3 B X TX Q Q Q Q Q Q 4 B GX Q Q Q Q Q Q Q 5 [ Q Q Q Q Q Q Q Q 6 Q Q Q Q Q Q Q Q Q 7 Q Q Q Q Q Q Q Q Q 8 Q Q Q Q Q Q Q Q Q 9 Q Q Q Q Q Q Q Q Q 10 Q Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q t = 5 1 2 3 4 5 6 7 8 9 1 Q A A A Q ] Q Q Q 2 B X X X GX Q Q Q Q 3 B X G Q Q Q Q Q Q 4 B X Q Q Q Q Q Q Q 5 Q GX Q Q Q Q Q Q Q 6 [ Q Q Q Q Q Q Q Q 7 Q Q Q Q Q Q Q Q Q 8 Q Q Q Q Q Q Q Q Q 9 Q Q Q Q Q Q Q Q Q 10 Q Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q t = 6 1 2 3 4 5 6 7 8 9 1 Q A A Q A A ] Q Q 2 B X X X X GX Q Q Q 3 B X Q ] Q Q Q Q Q 4 Q X [ Q Q Q Q Q Q 5 B X Q Q Q Q Q Q Q 6 B GX Q Q Q Q Q Q Q 7 [ Q Q Q Q Q Q Q Q 8 Q Q Q Q Q Q Q Q Q 9 Q Q Q Q Q Q Q Q Q 10 Q Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q t = 7 1 2 3 4 5 6 7 8 9 1 Q A Q A A A Q ] Q 2 B X X X X X GX Q Q 3 Q X Q A ] Q Q Q Q 4 B X B TX Q Q Q Q Q 5 B X [ Q Q Q Q Q Q 6 B X Q Q Q Q Q Q Q 7 Q GX Q Q Q Q Q Q Q 8 [ Q Q Q Q Q Q Q Q 9 Q Q Q Q Q Q Q Q Q 10 Q Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q t = 8 1 2 3 4 5 6 7 8 9 1 Q Q A A A Q A A GX 2 Q X X X X X X GX Q 3 B X Q A Q ] Q Q Q 4 B X B X TX Q Q Q Q 5 B X Q TX Q Q Q Q Q 6 Q X [ Q Q Q Q Q Q 7 B X Q Q Q Q Q Q Q 8 B GX Q Q Q Q Q Q Q 9 [ Q Q Q Q Q Q Q Q 10 Q Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q t = 9 1 2 3 4 5 6 7 8 9 1 Q A A A Q A A [ GX 2 B X X X X X X X TX 3 B X Q Q A A ] Q Q 4 B X Q X X TX Q Q Q 5 Q X B X Q Q Q Q Q 6 B X B TX Q Q Q Q Q 7 B X [ Q Q Q Q Q Q 8 B X Q Q Q Q Q Q Q 9 Q GX Q Q Q Q Q Q Q 10 [ Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q t = 10 1 2 3 4 5 6 7 8 9 1 Q A A Q A A [ ] GX 2 B X X X X X X X X 3 B X TX A A A Q ] Q 4 Q X B X X X TX Q Q 5 B X B X TX Q Q Q Q 6 B X B X Q Q Q Q Q 7 B X Q TX Q Q Q Q Q 8 Q X [ Q Q Q Q Q Q 9 B X Q Q Q Q Q Q Q 10 B GX Q Q Q Q Q Q Q 11 [ Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q t = 11 1 2 3 4 5 6 7 8 9 1 Q A Q A A [ B [ GX 2 B X X X X X X X X 3 Q X Q A A Q A A C 4 B X B X X X X TX Q 5 B X B X G Q Q Q Q 6 B X Q X Q Q Q Q Q 7 Q X B X Q Q Q Q Q 8 B X B TX Q Q Q Q Q 9 B X [ Q Q Q Q Q Q 10 B X Q Q Q Q Q Q Q 11 Q GX Q Q Q Q Q Q Q 12 [ Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q t = 12 1 2 3 4 5 6 7 8 9 1 Q Q A A [ Q B [ GX 2 Q X X X X X X X X 3 B X Q A Q A A [ C 4 B X B X X X X X TX 5 B X Q X Q ] Q Q Q 6 Q X B X [ Q Q Q Q 7 B X B X Q Q Q Q Q 8 B X B X Q Q Q Q Q 9 B X Q TX Q Q Q Q Q 10 Q X [ Q Q Q Q Q Q 11 B X Q Q Q Q Q Q Q 12 B GX Q Q Q Q Q Q Q 13 GX Q Q Q Q Q Q Q Q t = 13 1 2 3 4 5 6 7 8 9 1 Q A A [ B B G [ GX 2 B X X X X X X X X 3 B X Q Q A A [ ] C 4 B X Q X X X X X X 5 Q X B X Q A ] Q Q 6 B X B X B TX Q Q Q 7 B X B X [ Q Q Q Q 8 B X Q X Q Q Q Q Q 9 Q X B X Q Q Q Q Q 10 B X B TX Q Q Q Q Q 11 B X [ Q Q Q Q Q Q 12 ] X Q Q Q Q Q Q Q 13 GX TX Q Q Q Q Q Q Q t = 14 1 2 3 4 5 6 7 8 9 1 Q A [ Q B B G [ GX 2 B X X X X X X X X 3 B X TX A A [ B [ C 4 Q X B X X X X X X 5 B X B X Q A Q ] Q 6 B X B X B X TX Q Q 7 B X Q X Q TX Q Q Q 8 Q X B X [ Q Q Q Q 9 B X B X Q Q Q Q Q 10 B X B X Q Q Q Q Q 11 ] X Q TX Q Q Q Q Q 12 [ X [ Q Q Q Q Q Q 13 GX X Q Q Q Q Q Q Q t = 15 1 2 3 4 5 6 7 8 9 1 Q [ B B Q B G [ GX 2 B X X X X X X X X 3 Q X Q A [ Q B [ C 4 B X B X X X X X X 5 B X B X Q Q A A C 6 B X Q X Q X X TX Q 7 Q X B X B X Q Q Q 8 B X B X B TX Q Q Q 9 B X B X [ Q Q Q Q 10 ] X Q X Q Q Q Q Q 11 A X B X Q Q Q Q Q 12 ] X B TX Q Q Q Q Q 13 GX X C Q Q Q Q Q Q t = 16 1 2 3 4 5 6 7 8 9 1 [ Q B B B [ G [ GX 2 Q X X X X X X X X 3 B X Q [ B B G [ C 4 B X B X X X X X X 5 B X Q X TX A A [ C 6 Q X B X B X X X TX 7 B X B X B X TX Q Q 8 B X B X B X Q Q Q 9 ] X Q X Q TX Q Q Q 10 Q X B X [ Q Q Q Q 11 A X B X Q Q Q Q Q 12 ] X ] X Q Q Q Q Q 13 GX X C TX Q Q Q Q Q t = 17 1 2 3 4 5 6 7 8 9 1 B B Q B B [ B [ GX 2 [ X X X X X X X X 3 B X [ Q B B G [ C 4 B X Q X X X X X X 5 Q X B X Q A [ ] C 6 B X B X B X X X X 7 B X B X B X G Q Q 8 ] X Q X Q X Q Q Q 9 A X B X B X Q Q Q 10 A X B X B TX Q Q Q 11 G X ] X [ Q Q Q Q 12 ] X [ X Q Q Q Q Q 13 GX X C X Q Q Q Q Q t = 18 1 2 3 4 5 6 7 8 9 1 B B B Q B [ B [ GX 2 [ X X X X X X X X 3 B X B B Q B G [ C 4 Q X [ X X X X X X 5 B X B X Q [ B [ C 6 B X B X B X X X X 7 ] X Q X Q X Q ] Q 8 Q X B X B X [ Q Q 9 A X B X B X Q Q Q 10 A X ] X B X Q Q Q 11 G X A X Q TX Q Q Q 12 ] X ] X [ Q Q Q Q 13 GX X C X Q Q Q Q Q t = 19 1 2 3 4 5 6 7 8 9 1 B B B B G [ B [ GX 2 [ X X X X X X X X 3 G X B B B [ G [ C 4 B X [ X X X X X X 5 B X B X [ Q B [ C 6 ] X Q X Q X X X X 7 A X B X B X Q A C 8 A X B X B X B TX Q 9 Q X ] X B X [ Q Q 10 A X Q X Q X Q Q Q 11 G X A X B X Q Q Q 12 ] X ] X B TX Q Q Q 13 GX X C X C Q Q Q Q t = 20 1 2 3 4 5 6 7 8 9 1 B B B B G Q B [ GX 2 Q X X X X X X X X 3 G X B B B [ B [ C 4 B X [ X X X X X X 5 ] X G X B B G [ C 6 Q X B X [ X X X X 7 A X B X B X Q [ C 8 A X ] X B X B X TX 9 A X A X Q X Q TX Q 10 ] X A X B X [ Q Q 11 G X G X B X Q Q Q 12 ] X ] X ] X Q Q Q 13 GX X C X C TX Q Q Q t = 21 1 2 3 4 5 6 7 8 9 1 Q B B B G B G [ GX 2 B X X X X X X X X 3 G X B B B [ B [ C 4 ] X Q X X X X X X 5 A X G X B B G [ C 6 A X B X [ X X X X 7 Q X ] X B X [ ] C 8 A X Q X Q X Q X X 9 A X A X B X B X Q 10 ] X A X B X B TX Q 11 A X G X ] X [ Q Q 12 ] X ] X [ X Q Q Q 13 GX X C X C X Q Q Q t = 22 1 2 3 4 5 6 7 8 9 1 B Q B B G B G [ GX 2 B X X X X X X X X 3 GX X Q B B [ B [ C 4 Q X B X X X X X X 5 A X G X B B G [ C 6 A X ] X [ X X X X 7 A X A X G X B [ C 8 Q X A X B X [ X X 9 A X Q X B X B X TX 10 ] X A X ] X B X Q 11 A X G X A X Q TX Q 12 ] X ] X ] X [ Q Q 13 GX X C X C X Q Q Q t = 23 1 2 3 4 5 6 7 8 9 1 B B Q B G B G [ GX 2 ] X X X X X X X X 3 GX X B Q B [ B [ C 4 [ X B X X X X X X 5 Q X C X B B G [ C 6 A X Q X Q X X X X 7 A X A X G X B [ C 8 A X A X B X [ X X 9 G X A X ] X B X G 10 ] X ] X Q X Q X Q 11 A X G X A X B X Q 12 ] X ] X ] X B TX Q 13 GX X C X C X C Q Q t = 24 1 2 3 4 5 6 7 8 9 1 ] B B [ G B G [ GX 2 [ X X X X X X X X 3 GX X B B G [ B [ C 4 ] X ] X X X X X X 5 [ X C X Q B G [ C 6 Q X [ X B X X X X 7 A X Q X G X B [ C 8 A X A X ] X [ X X 9 G X A X A X G X C 10 Q X ] X A X B X [ 11 A X A X G X B X Q 12 ] X ] X ] X ] X Q 13 GX X C X C X C TX Q t = 25 1 2 3 4 5 6 7 8 9 1 A ] B [ B B G [ GX 2 ] X X X X X X X X 3 GX X ] B G Q B [ C 4 [ X [ X X X X X X 5 B X C X B [ G [ C 6 [ X ] X B X X X X 7 Q X [ X C X B [ C 8 A X Q X Q X Q X X 9 G X A X A X G X C 10 A X ] X A X B X ] 11 G X A X G X ] X [ 12 ] X ] X ] X [ X Q 13 GX X C X C X C X Q t = 26 1 2 3 4 5 6 7 8 9 1 A Q ] [ B B G [ GX 2 ] X X X X X X X X 3 GX X A ] G B G [ C 4 [ X ] X X X X X X 5 B X C X B [ B [ C 6 Q X [ X ] X X X X 7 [ X B X C X G [ C 8 ] X [ X [ X B X X 9 G X G X Q X G X C 10 A X ] X A X ] X [ 11 G X A X G X A X B 12 ] X ] X ] X ] X [ 13 GX X C X C X C X Q t = 27 1 2 3 4 5 6 7 8 9 1 G A A GX B B G [ GX 2 ] X X X X X X X X 3 GX X A Q C B G [ C 4 [ X ] X X X X X X 5 G X C X ] [ B [ C 6 B X [ X [ X X X X 7 B X B X C X G [ C 8 GX X Q X ] X B X X 9 A X C X [ X C X C 10 A X Q X ] X Q X [ 11 G X A X G X A X B 12 ] X ] X ] X ] X Q 13 GX X C X C X C X C t = 28 1 2 3 4 5 6 7 8 9 1 G A [ GX ] B G [ GX 2 ] X X X X X X X X 3 GX X G [ C ] G [ C 4 [ X ] X X X X X X 5 G X C X G C B [ C 6 B X [ X ] X X X X 7 ] X G X C X G [ C 8 GX X ] X [ X ] X X 9 [ X C X G X C X C 10 A X [ X C X [ X [ 11 G X G X A X G X G 12 ] X ] X ] X ] X ] 13 GX X C X C X C X ] t = 29 1 2 3 4 5 6 7 8 9 1 G [ ] GX [ ] G [ GX 2 ] X X X X X X X X 3 GX X C [ C ] C [ C 4 [ X ] X X X X X X 5 G X C X [ C ] [ C 6 ] X [ X ] X X X X 7 [ X C X C X C [ C 8 GX X ] X [ X ] X X 9 ] X C X ] X C X C 10 [ X [ X C X [ X [ 11 G X C X [ X C X C 12 ] X ] X ] X ] X Q 13 GX X C X C X C X [ t = 30 1 2 3 4 5 6 7 8 9 1 GX ] [ GX ] [ GX [ GX 2 ] X X X X X X X X 3 GX X C C C C C C C 4 [ X C X X X X X X 5 GX X C X C C C C C 6 [ X C X C X X X X 7 ] X C X C X C C C 8 GX X C X C X C X X 9 [ X C X C X C X C 10 ] X C X C X C X C 11 GX X C X C X C X C 12 ] X C X C X C X C 13 GX X C X C X C X C t = 31 1 2 3 4 5 6 7 8 9 1 GX GX GX GX GX GX GX GX GX 2 GX X X X X X X X X 3 GX X X X X X X X X 4 GX X X X X X X X X 5 GX X X X X X X X X 6 GX X X X X X X X X 7 GX X X X X X X X X 8 GX X X X X X X X X 9 GX X X X X X X X X 10 GX X X X X X X X X 11 GX X X X X X X X X 12 GX X X X X X X X X 13 GX X X X X X X X X t = 32 1 2 3 4 5 6 7 8 9 1 F F F F F F F F F 2 F F F F F F F F F 3 F F F F F F F F F 4 F F F F F F F F F 5 F F F F F F F F F 6 F F F F F F F F F 7 F F F F F F F F F 8 F F F F F F F F F 9 F F F F F F F F F 10 F F F F F F F F F 11 F F F F F F F F F 12 F F F F F F F F F 13 F F F F F F F F F Fig. 5. Snapshots of the optimum-time eleven-state synchronization process on a 13 × 9 array. TABLE I A LIST OF IMPLEMENTATIONS FOR 2D RECTANGLE FSSP ALGORITHMS. Implementations # of # of Time Notes states rules complexity Beyer [1969] — — optimum rectangle Shinahr [1974] 28 — optimum rectangle Umeo, Maeda and 6 1718 non- rectangle Fujiwara [2002] optimum Umeo and Kubo [2010] 7 787 optimum square Theorem 4 10 1629 non- rectangle (this paper) optimum Theorem 5 11 4044 optimum rectangle (this paper) Theorem 6 9 2561 optimum rectangle (this paper) IV. CONCLUSION We have proposed a nine-state optimum-time synchro- nization algorithm that can synchronize any rectangle arrays of size m × n with a general at one corner in m + n + max(m, n)−3 steps. The algorithm is based on a new, simple zebra-like mapping scheme which embeds Biomath 1 (2012), 1209022, http://dx.doi.org/10.11145/j.biomath.2012.09.022 Page 5 of 6 http://dx.doi.org/10.11145/j.biomath.2012.09.022 H. Umeo et al., A State-Efficient Zebra-Like Implementation of Synchronization Algorithms... t = 0 1 2 3 4 5 6 7 8 9 1 G Q Q Q Q Q Q Q Q 2 Q Q Q Q Q Q Q Q Q 3 Q Q Q Q Q Q Q Q Q 4 Q Q Q Q Q Q Q Q Q 5 Q Q Q Q Q Q Q Q Q 6 Q Q Q Q Q Q Q Q Q 7 Q Q Q Q Q Q Q Q Q 8 Q Q Q Q Q Q Q Q Q 9 Q Q Q Q Q Q Q Q Q 10 Q Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q t = 1 1 2 3 4 5 6 7 8 9 1 Q X Q Q Q Q Q Q Q 2 [ Q Q Q Q Q Q Q Q 3 Q Q Q Q Q Q Q Q Q 4 Q Q Q Q Q Q Q Q Q 5 Q Q Q Q Q Q Q Q Q 6 Q Q Q Q Q Q Q Q Q 7 Q Q Q Q Q Q Q Q Q 8 Q Q Q Q Q Q Q Q Q 9 Q Q Q Q Q Q Q Q Q 10 Q Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q t = 2 1 2 3 4 5 6 7 8 9 1 Q A ] Q Q Q Q Q Q 2 B X Q Q Q Q Q Q Q 3 [ Q Q Q Q Q Q Q Q 4 Q Q Q Q Q Q Q Q Q 5 Q Q Q Q Q Q Q Q Q 6 Q Q Q Q Q Q Q Q Q 7 Q Q Q Q Q Q Q Q Q 8 Q Q Q Q Q Q Q Q Q 9 Q Q Q Q Q Q Q Q Q 10 Q Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q t = 3 1 2 3 4 5 6 7 8 9 1 Q A Q ] Q Q Q Q Q 2 B X C Q Q Q Q Q Q 3 Q X Q Q Q Q Q Q Q 4 [ Q Q Q Q Q Q Q Q 5 Q Q Q Q Q Q Q Q Q 6 Q Q Q Q Q Q Q Q Q 7 Q Q Q Q Q Q Q Q Q 8 Q Q Q Q Q Q Q Q Q 9 Q Q Q Q Q Q Q Q Q 10 Q Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q t = 4 1 2 3 4 5 6 7 8 9 1 Q Q A A ] Q Q Q Q 2 Q X X X Q Q Q Q Q 3 B X X Q Q Q Q Q Q 4 B X Q Q Q Q Q Q Q 5 [ Q Q Q Q Q Q Q Q 6 Q Q Q Q Q Q Q Q Q 7 Q Q Q Q Q Q Q Q Q 8 Q Q Q Q Q Q Q Q Q 9 Q Q Q Q Q Q Q Q Q 10 Q Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q t = 5 1 2 3 4 5 6 7 8 9 1 Q A A A Q ] Q Q Q 2 B X X X C Q Q Q Q 3 B X G Q Q Q Q Q Q 4 B X Q Q Q Q Q Q Q 5 Q X Q Q Q Q Q Q Q 6 [ Q Q Q Q Q Q Q Q 7 Q Q Q Q Q Q Q Q Q 8 Q Q Q Q Q Q Q Q Q 9 Q Q Q Q Q Q Q Q Q 10 Q Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q t = 6 1 2 3 4 5 6 7 8 9 1 Q A A Q A A ] Q Q 2 B X X X X X Q Q Q 3 B X Q ] Q Q Q Q Q 4 Q X [ Q Q Q Q Q Q 5 B X Q Q Q Q Q Q Q 6 B X Q Q Q Q Q Q Q 7 [ Q Q Q Q Q Q Q Q 8 Q Q Q Q Q Q Q Q Q 9 Q Q Q Q Q Q Q Q Q 10 Q Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q t = 7 1 2 3 4 5 6 7 8 9 1 Q A Q A A A Q ] Q 2 B X X X X X C Q Q 3 Q X Q A ] Q Q Q Q 4 B X B G Q Q Q Q Q 5 B X [ Q Q Q Q Q Q 6 B X Q Q Q Q Q Q Q 7 Q X Q Q Q Q Q Q Q 8 [ Q Q Q Q Q Q Q Q 9 Q Q Q Q Q Q Q Q Q 10 Q Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q t = 8 1 2 3 4 5 6 7 8 9 1 Q Q A A A Q A A C 2 Q X X X X X X X Q 3 B X Q A Q ] Q Q Q 4 B X B X G Q Q Q Q 5 B X Q G Q Q Q Q Q 6 Q X [ Q Q Q Q Q Q 7 B X Q Q Q Q Q Q Q 8 B X Q Q Q Q Q Q Q 9 [ Q Q Q Q Q Q Q Q 10 Q Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q t = 9 1 2 3 4 5 6 7 8 9 1 Q A A A Q A A [ X 2 B X X X X X X X A 3 B X Q Q A A ] Q Q 4 B X Q X C G Q Q Q 5 Q X B C Q Q Q Q Q 6 B X B G Q Q Q Q Q 7 B X [ Q Q Q Q Q Q 8 B X Q Q Q Q Q Q Q 9 Q X Q Q Q Q Q Q Q 10 [ Q Q Q Q Q Q Q Q 11 Q Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q t = 10 1 2 3 4 5 6 7 8 9 1 Q A A Q A A [ ] X 2 B X X X X X X X X 3 B X Q A A A Q ] Q 4 Q X B X X X G Q Q 5 B X B X X Q Q Q Q 6 B X B X Q Q Q Q Q 7 B X Q G Q Q Q Q Q 8 Q X [ Q Q Q Q Q Q 9 B X Q Q Q Q Q Q Q 10 B X Q Q Q Q Q Q Q 11 [ Q Q Q Q Q Q Q Q 12 Q Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q t = 11 1 2 3 4 5 6 7 8 9 1 Q A Q A A [ B [ X 2 B X X X X X X X X 3 Q X Q A A Q A A C 4 B X B X X X C G Q 5 B X B X G Q Q Q Q 6 B X Q X Q Q Q Q Q 7 Q X B C Q Q Q Q Q 8 B X B G Q Q Q Q Q 9 B X [ Q Q Q Q Q Q 10 B X Q Q Q Q Q Q Q 11 Q X Q Q Q Q Q Q Q 12 [ Q Q Q Q Q Q Q Q 13 Q Q Q Q Q Q Q Q Q t = 12 1 2 3 4 5 6 7 8 9 1 Q Q A A [ Q B [ X 2 Q X X X X X X X X 3 B X Q A Q A A [ C 4 B X B X X X X X B 5 B X Q X Q ] Q Q Q 6 Q X B X [ Q Q Q Q 7 B X B X Q Q Q Q Q 8 B X B X Q Q Q Q Q 9 B X Q G Q Q Q Q Q 10 Q X [ Q Q Q Q Q Q 11 B X Q Q Q Q Q Q Q 12 B X Q Q Q Q Q Q Q 13 C Q Q Q Q Q Q Q Q t = 13 1 2 3 4 5 6 7 8 9 1 Q A A [ B B G [ X 2 B X X X X X X X X 3 B X Q Q A A [ ] C 4 B X Q X X X X X X 5 Q X B X Q A ] Q Q 6 B X B X B G Q Q Q 7 B X B X [ Q Q Q Q 8 B X Q X Q Q Q Q Q 9 Q X B C Q Q Q Q Q 10 B X B G Q Q Q Q Q 11 B X [ Q Q Q Q Q Q 12 ] X Q Q Q Q Q Q Q 13 X B Q Q Q Q Q Q Q t = 14 1 2 3 4 5 6 7 8 9 1 Q A [ Q B B G [ X 2 B X X X X X X X X 3 B X Q A A [ B [ C 4 Q X B X X X X X X 5 B X B X Q A Q ] Q 6 B X B X B X G Q Q 7 B X Q X Q G Q Q Q 8 Q X B X [ Q Q Q Q 9 B X B X Q Q Q Q Q 10 B X B X Q Q Q Q Q 11 ] X Q G Q Q Q Q Q 12 [ X [ Q Q Q Q Q Q 13 X X Q Q Q Q Q Q Q t = 15 1 2 3 4 5 6 7 8 9 1 Q [ B B Q B G [ X 2 B X X X X X X X X 3 Q X Q A [ Q B [ C 4 B X B X X X X X X 5 B X B X Q Q A A C 6 B X Q X Q X C G Q 7 Q X B X B C Q Q Q 8 B X B X B G Q Q Q 9 B X B X [ Q Q Q Q 10 ] X Q X Q Q Q Q Q 11 A X B C Q Q Q Q Q 12 ] X B G Q Q Q Q Q 13 X X C Q Q Q Q Q Q t = 16 1 2 3 4 5 6 7 8 9 1 [ Q B B B [ G [ X 2 Q X X X X X X X X 3 B X Q [ B B G [ C 4 B X B X X X X X X 5 B X Q X Q A A [ C 6 Q X B X B X X X B 7 B X B X B X X Q Q 8 B X B X B X Q Q Q 9 ] X Q X Q G Q Q Q 10 Q X B X [ Q Q Q Q 11 A X B X Q Q Q Q Q 12 ] X ] X Q Q Q Q Q 13 X X C A Q Q Q Q Q t = 17 1 2 3 4 5 6 7 8 9 1 B B Q B B [ B [ X 2 [ X X X X X X X X 3 B X [ Q B B G [ C 4 B X Q X X X X X X 5 Q X B X Q A [ ] C 6 B X B X B X X X X 7 B X B X B X G Q Q 8 ] X Q X Q X Q Q Q 9 A X B X B C Q Q Q 10 A X B X B G Q Q Q 11 G X ] X [ Q Q Q Q 12 ] X [ X Q Q Q Q Q 13 X X C X Q Q Q Q Q t = 18 1 2 3 4 5 6 7 8 9 1 B B B Q B [ B [ X 2 [ X X X X X X X X 3 B X B B Q B G [ C 4 Q X [ X X X X X X 5 B X B X Q [ B [ C 6 B X B X B X X X X 7 ] X Q X Q X Q ] Q 8 Q X B X B X [ Q Q 9 A X B X B X Q Q Q 10 A X ] X B X Q Q Q 11 G X A X Q G Q Q Q 12 ] X ] X [ Q Q Q Q 13 X X C X Q Q Q Q Q t = 19 1 2 3 4 5 6 7 8 9 1 B B B B G [ B [ X 2 [ X X X X X X X X 3 G X B B B [ G [ C 4 B X [ X X X X X X 5 B X B X [ Q B [ C 6 ] X Q X Q X X X X 7 A X B X B X Q A C 8 A X B X B X B G Q 9 Q X ] X B X [ Q Q 10 A X Q X Q X Q Q Q 11 G X A X B C Q Q Q 12 ] X ] X B G Q Q Q 13 X X C X C Q Q Q Q t = 20 1 2 3 4 5 6 7 8 9 1 B B B B G Q B [ X 2 Q X X X X X X X X 3 G X B B B [ B [ C 4 B X [ X X X X X X 5 ] X G X B B G [ C 6 Q X B X [ X X X X 7 A X B X B X Q [ C 8 A X ] X B X B X B 9 A X A X Q X Q G Q 10 ] X A X B X [ Q Q 11 G X G X B X Q Q Q 12 ] X ] X ] X Q Q Q 13 X X C X C A Q Q Q t = 21 1 2 3 4 5 6 7 8 9 1 Q B B B G B G [ X 2 B X X X X X X X X 3 G X B B B [ B [ C 4 ] X Q X X X X X X 5 A X G X B B G [ C 6 A X B X [ X X X X 7 Q X ] X B X [ ] C 8 A X Q X Q X Q G X 9 A X A X B X B C Q 10 ] X A X B X B G Q 11 A X G X ] X [ Q Q 12 ] X ] X [ X Q Q Q 13 X X C X C X Q Q Q t = 22 1 2 3 4 5 6 7 8 9 1 B Q B B G B G [ X 2 B X X X X X X X X 3 X X Q B B [ B [ C 4 Q X B X X X X X X 5 A X G X B B G [ C 6 A X ] X [ X X X X 7 A X A X G X B [ C 8 Q X A X B X [ X X 9 A X Q X B X B [ Q 10 ] X A X ] X B X Q 11 A X G X A X Q G Q 12 ] X ] X ] X [ Q Q 13 X X C X C X Q Q Q t = 23 1 2 3 4 5 6 7 8 9 1 B B Q B G B G [ X 2 ] X X X X X X X X 3 X X B Q B [ B [ C 4 [ X B X X X X X X 5 Q X C X B B G [ C 6 A X Q X Q X X X X 7 A X A X G X B [ C 8 A X A X B X [ X X 9 G X A X ] X B X G 10 ] X ] X Q X Q X Q 11 A X G X A X B C Q 12 ] X ] X ] X B G Q 13 X X C X C X C Q Q t = 24 1 2 3 4 5 6 7 8 9 1 ] B B [ G B G [ X 2 [ X X X X X X X X 3 X X B B G [ B [ C 4 ] X ] X X X X X X 5 [ X C X Q B G [ C 6 Q X [ X B X X X X 7 A X Q X G X B [ C 8 A X A X ] X [ X X 9 G X A X A X G X C 10 Q X ] X A X B X [ 11 A X A X G X B X Q 12 ] X ] X ] X ] X Q 13 X X C X C X C A Q t = 25 1 2 3 4 5 6 7 8 9 1 A ] B [ B B G [ X 2 ] X X X X X X X X 3 X X ] B G Q B [ C 4 [ X [ X X X X X X 5 B X C X B [ G [ C 6 [ X ] X B X X X X 7 Q X [ X C X B [ C 8 A X Q X Q X Q X X 9 G X A X A X G X C 10 A X ] X A X B X ] 11 G X A X G X ] X [ 12 ] X ] X ] X [ X Q 13 X X C X C X C X Q t = 26 1 2 3 4 5 6 7 8 9 1 A Q ] [ B B G [ X 2 ] X X X X X X X X 3 X X A ] G B G [ C 4 [ X ] X X X X X X 5 B X C X B [ B [ C 6 Q X [ X ] X X X X 7 [ X B X C X G [ C 8 ] X [ X [ X B X X 9 G X G X Q X G X C 10 A X ] X A X ] X [ 11 G X A X G X A X B 12 ] X ] X ] X ] X [ 13 X X C X C X C X Q t = 27 1 2 3 4 5 6 7 8 9 1 G A A X B B G [ X 2 ] X X X X X X X X 3 X X A Q C B G [ C 4 [ X ] X X X X X X 5 G X C X ] [ B [ C 6 B X [ X [ X X X X 7 B X B X C X G [ C 8 X X Q X ] X B X X 9 A X C X [ X C X C 10 A X Q X ] X Q X [ 11 G X A X G X A X B 12 ] X ] X ] X ] X Q 13 X X C X C X C X C t = 28 1 2 3 4 5 6 7 8 9 1 G A [ X ] B G [ X 2 ] X X X X X X X X 3 X X G [ C ] G [ C 4 [ X ] X X X X X X 5 G X C X G C B [ C 6 B X [ X ] X X X X 7 ] X G X C X G [ C 8 X X ] X [ X ] X X 9 [ X C X G X C X C 10 A X [ X C X [ X [ 11 G X G X A X G X G 12 ] X ] X ] X ] X ] 13 X X C X C X C X ] t = 29 1 2 3 4 5 6 7 8 9 1 G [ ] X [ ] G [ X 2 ] X X X X X X X X 3 X X C [ C ] C [ C 4 [ X ] X X X X X X 5 G X C X [ C ] [ C 6 ] X [ X ] X X X X 7 [ X C X C X C [ C 8 X X ] X [ X ] X X 9 ] X C X ] X C X C 10 [ X [ X C X [ X [ 11 G X C X [ X C X C 12 ] X ] X ] X ] X Q 13 X X C X C X C X [ t = 30 1 2 3 4 5 6 7 8 9 1 X ] [ X ] [ X [ X 2 ] X X X X X X X X 3 X X C C C C C C C 4 [ X C X X X X X X 5 X X C X C C C C C 6 [ X C X C X X X X 7 ] X C X C X C C C 8 X X C X C X C X X 9 [ X C X C X C X C 10 ] X C X C X C X C 11 X X C X C X C X C 12 ] X C X C X C X C 13 X X C X C X C X C t = 31 1 2 3 4 5 6 7 8 9 1 X X X X X X X X X 2 X X X X X X X X X 3 X X X X X X X X X 4 X X X X X X X X X 5 X X X X X X X X X 6 X X X X X X X X X 7 X X X X X X X X X 8 X X X X X X X X X 9 X X X X X X X X X 10 X X X X X X X X X 11 X X X X X X X X X 12 X X X X X X X X X 13 X X X X X X X X X t = 32 1 2 3 4 5 6 7 8 9 1 F F F F F F F F F 2 F F F F F F F F F 3 F F F F F F F F F 4 F F F F F F F F F 5 F F F F F F F F F 6 F F F F F F F F F 7 F F F F F F F F F 8 F F F F F F F F F 9 F F F F F F F F F 10 F F F F F F F F F 11 F F F F F F F F F 12 F F F F F F F F F 13 F F F F F F F F F Fig. 6. Snapshots of the optimum-time nine-state synchronization process on a 13 × 9 array. 1D synchronization operations onto rectangle arrays. The nine-state implementation described in terms of state transition table is a smallest, known at present, realiza- tion of time-optimum rectangle synchronizer. The em- bedding scheme developed in this paper would be useful for state-efficient implementation of multi-dimensional synchronization algorithms. REFERENCES [1] R. Balzer, “An 8-state minimal time solution to the firing squad synchronization problem”, Information and Control 10, 22–42 (1967). http://dx.doi.org/10.1016/S0019-9958(67)90032-0 [2] W. T. Beyer, “Recognition of topological invariants by iterative arrays”, Ph.D. Thesis, MIT, pp. 144 (1969). [3] H. D. Gerken, “Über Synchronisations — Probleme bei Zellula- rautomaten”, Diplomarbeit, Institut für Theoretische Informatik, Technische Universität Braunschweig, pp. 50 (1987). [4] E. Goto, “A minimal time solution of the firing squad problem”, Dittoed course notes for Applied Mathematics 298, Harvard University, 52–59 (1962). [5] J. Mazoyer, “A six-state minimal time solution to the firing squad synchronization problem”, Theoretical Computer Science 50, 183–238 (1987). http://dx.doi.org/10.1016/0304-3975(87)90124-1 [6] E. F. Moore, “The firing squad synchronization problem”, in Sequential Machines, Selected Papers, (E. F. Moore, ed.), Addison-Wesley, Reading MA, 213–214 (1964). [7] H. Schmid, “Synchronisationsprobleme für zelluläre Automaten mit mehreren Generälen”, Diplomarbeit, Universität Karsruhe, (2003). [8] H. Schmid and T. Worsch, “The firing squad synchronization problem with many generals for one-dimensional CA”, Proc. of IFIP World Congress, 111–124 (2004). [9] I. Shinahr, “Two- and three-dimensional firing squad syn- chronization problems”, Information and Control 24, 163–180 (1974). http://dx.doi.org/10.1016/S0019-9958(74)80055-0 [10] H. Szwerinski, “Time-optimum solution of the firing-squad- synchronization-problem for n-dimensional rectangles with the general at an arbitrary position”, Theoretical Computer Science 19, 305–320 (1982). http://dx.doi.org/10.1016/0304-3975(82)90040-8 [11] H. Umeo, “Firing squad synchronization algorithms for two- dimensional cellular automata”, Journal of Cellular Automata 4, 1–20 (2008). [12] H. Umeo, “Firing squad synchronization problem in cellular automata”, In: Encyclopedia of Complexity and System Science, R. A. Meyers (Ed.), Springer, Vol.4, 3537–3574 (2009). [13] H. Umeo, M. Hisaoka, and S. Akiguchi, “Twelve-state optimum-time synchronization algorithm for two-dimensional rectangular cellular arrays”, Proc. of 4th International Confer- ence on Unconventional Computing: UC 2005, LNCS 3699, 214–223 (2005). [14] H. Umeo, N. Kamikawa, K. Nishioka, and S. Akiguchi, “Generalized firing squad synchronization protocols for one- dimensional cellular automata — a survey”, Acta Physica Polonica B, Proceedings Supplement 3, 267–289 (2010). [15] Umeo and Kubo, “A seven-state time-optimum square synchro- nizer.”, Proc. of the 9th International Conference on Cellular Automata for Research and Industry, LNCS 6350, Springer- Verlag, 219–230 (2010). [16] H. Umeo, M. Maeda and N. Fujiwara, “An efficient mapping scheme for embedding any one-dimensional firing squad syn- chronization algorithm onto two-dimensional arrays”, Proc. of the 5th International Conference on Cellular Automata for Research and Industry, LNCS 2493, Springer-Verlag, 69–81 (2002). [17] H. Umeo, M. Maeda, M. Hisaoka and M. Teraoka, “A state- efficient mapping scheme for designing two-dimensional firing squad synchronization algorithms”, Fundamenta Informaticae, 74 No. 4, 603–623 (2006). [18] H. Umeo and H. Uchino, “A new time-optimum synchronization algorithm for two-dimensional cellular arrays”, Proc. of Intern. Conf. on Computer Aided Systems Theory, EUROCAST 2007, (A. Quesada-Arenciba, J. C. Rodriguez, R. Moreno-Diaz Jr., R. Moreno-Diaz (Eds.)), 213–216, (2007). [19] H. Umeo, T. Yamawaki, N. Shimizu and H. Uchino, “Modeling and simulation of global synchronization processes for large- scale-of two-dimensional cellular arrays”, Proc. of Intern. Conf. on Modeling and Simulation, AMS 2007, 139–144 (2007). Biomath 1 (2012), 1209022, http://dx.doi.org/10.11145/j.biomath.2012.09.022 Page 6 of 6 http://dx.doi.org/10.1016/S0019-9958(67)90032-0 http://dx.doi.org/10.1016/0304-3975(87)90124-1 http://dx.doi.org/10.1016/S0019-9958(74)80055-0 http://dx.doi.org/10.1016/0304-3975(82)90040-8 http://dx.doi.org/10.11145/j.biomath.2012.09.022 Introduction Firing Squad Synchronization Problem FSSP on 2D Arrays Optimum-Time L-Shaped Mapping Algorithm Zebra-Like Mapping on Square Arrays Zebra-Like Mapping on Rectangle Arrays Conclusion References