Summary
International Technical Conference on Circuits/Systems, Computers and Communications
2008
Session Number:C6
Session:
Number:C6-2
A Note on Three-Dimensional Firing Squad Synchronization Algorithm
Takuya Yamawaki, Takashi Amesara, Hiroshi Umeo,
pp.-
Publication Date:2008/7/7
Online ISSN:2188-5079
Summary:
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 [1-10]. In the present paper, we propose an optimumtime firing squad synchronization algorithm for three-dimensional cellular automata. The algorithm can synchronize any threedimensional array of size m × n × l with a general at an arbitrary corner cell at exactly m+ n + l + max(m, n, l) - 4steps. A lower bound in time complexity is also given.