A FAMILY OF SMALLEST SYMMETRICAL FOUR-STATE FIRING SQUAD SYNCHRONIZATION PROTOCOLS FOR RING ARRAYS
Abstract
An existence or non-existence of five-state firing squad synchronization protocol has been a longstanding and famous open problem for a long time. In this paper, we answer partially to this problem by proposing a family of smallest four-state firing squad synchronization protocols that can synchronize any one-dimensional ring cellular arrays of length n = 2k for any positive integer k. The number four is the smallest one in the class of synchronization protocols proposed so far.
A preliminary version of this work was presented at the International Workshop on Cellular Automata: AUTOMATA 2008 (chaired by A. Adamatzky), held at Bristol in June, 2008.
References
- Information and Control 10, 22 (1967), DOI: 10.1016/S0019-9958(67)90032-0. Crossref, Google Scholar
- Theoretical Computer Science 320, 213 (2004), DOI: 10.1016/j.tcs.2004.01.036. Crossref, ISI, Google Scholar
- Hans-D. Gerken. (1987): Über Synchronisations - Probleme bei Zellularautomaten. Diplomarbeit, Institut für Theoretische Informatik, Technische Universität Braunschweig, pp. 50 . Google Scholar
E. Goto , Dittoed course notes for Applied Mathematics 298 (Harvard University, 1962) pp. 52–59. Google Scholar- Theoretical Computer Science 50, 183 (1987), DOI: 10.1016/0304-3975(87)90124-1. Crossref, ISI, Google Scholar
M. Minsky , Computation: Finite and infinite machines (Prentice Hall, 1967) pp. 28–29. Google Scholar- , Sequential Machines, Selected Papers, ed.
E. F. Moore (Addison-Wesley, Reading MA, 1964) pp. 213–214. Google Scholar P. Sanders , Massively parallel search for transition-tables of polyautomata, Proc. of the VI International Workshop on Parallel Processing by Cellular Automata and Arrays, eds.C. Jesshope , V. Jossifov and W. Wilhelmi (Akademie, 1994) pp. 99–108. Google Scholar- H. Umeo and N. Kamikawa. (2007): Four-state solutions to the firing squad synchronization problem based on Wolfram's rule 150 (a draft) . Google Scholar
H. Umeo and T. Yanagihara , A smallest five-state solution to the firing squad synchronization problem, Proc. of 5th Intern. Conf. on Machines, Computations, and Universality, MCU 20074664,LNCS (2007) pp. 292–302. Google ScholarH. Umeo , J. B. Yunès and N. Kamikawa , About 4-states solutions to the firing squad synchronization problem, Proc. of 8th International Conference on Cellular Automata for Research and Industry: ACRI 20085191,LNCS (2008) pp. 108–113. Google Scholar- Information and Control 9, 66 (1966), DOI: 10.1016/S0019-9958(66)90110-0. Crossref, Google Scholar
- Information Processing Letters 19(2), 71 (2008). ISI, Google Scholar
-
J. B. Yunès , Goto's construction and Pascal's triangle: New insights into cellular automata synchronization , Proc. of 1st Symposium on Cellular Automata, JAC 2008 ( 2008 ) . Google Scholar


