Affiliations: Faculty of Information Science and Technology,
University of Osaka Electro-Communication, Neyagawa-shi, Hatsu-cho, 18-8, Osaka,
572-8530, Japan. {umeo, uchino}@umeolab.osakac.ac.jp
Note: [] Address for correspondence: Faculty of Information Science and
Technology, University of Osaka Electro-Communication, Neyagawa-shi, Hatsu-cho,
18-8, Osaka, 572-8530, Japan
Abstract: The firing squad synchronization problem on cellular automata has
been studied extensively for more than forty years, and a rich variety of
synchronization algorithms have been proposed so far. In the present paper, we
propose a new optimum-time algorithm for synchronizing two-dimensional cellular
automata. The algorithm can synchronize any two-dimensional rectangle array of
size m × n in optimum m + n + max(m, n) − 3 steps. A partial
implementation of the algorithm for small cellular arrays is also given.
Keywords: Cellular automaton, Firing squad synchronization problem
