World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.
Special Issue on Cellular Automata Theory and ApplicationsNo Access


    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.


    • R. Balzer, Information and Control 10, 22 (1967), DOI: 10.1016/S0019-9958(67)90032-0. CrossrefGoogle Scholar
    • A. Berthiaumeet al., Theoretical Computer Science 320, 213 (2004), DOI: 10.1016/j.tcs.2004.01.036. Crossref, ISIGoogle 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
    • J. Mazoyer, Theoretical Computer Science 50, 183 (1987), DOI: 10.1016/0304-3975(87)90124-1. Crossref, ISIGoogle Scholar
    • M. Minsky, Computation: Finite and infinite machines (Prentice Hall, 1967) pp. 28–29. Google Scholar
    • E. F. Moore, 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 Scholar
    • H. 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
    • A. Waksman, Information and Control 9, 66 (1966), DOI: 10.1016/S0019-9958(66)90110-0. CrossrefGoogle Scholar
    • J. B. Yunès, Information Processing Letters 19(2), 71 (2008). ISIGoogle 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