Synchronization of a Rectangular Array of Automata

Variants of the synchronization problem are discussed for a rectangular array of homogeneous automata. It is shown that the synchronization problem for an $n\times m$ array reduces to the synchronization problem for a line of $n+m-1$ automata [E. F. Moore, Sequential Machines, Addison–Wesley, Reading, Mass., 1964, pp. 212–214; V. I. Levenshtein, Probl. Peredachi Inf., 1965, vol. 1, no. 4, pp. 20–32]. An expression is derived for the minimum synchronization time after the delivery of a starting signal to an arbitrary automaton in the array. It is remarked that with respect to the synchronization time the result of [V. I. Varshavskii, V. B. Marakhovskii, and V. A. Peschanskii, Probl. Peredachi Inf., 1968, vol. 4, no. 3, pp. 73–83] is a special case of the problem treated here. Each automaton of the array except the corner members has 19 states; the corner automata have 23 states each.