# The Smallest FSSP Partial Solutions for One-Dimensional Ring Cellular Automata: Symmetric and Asymmetric Synchronizers

• Hiroshi Umeo
• Naoki Kamikawa
• Gen Fujita
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 11187)

## Abstract

A synchronization problem in cellular automata has been known as the Firing Squad Synchronization Problem (FSSP) since its development, where the FSSP gives a finite-state protocol for synchronizing a large scale of cellular automata. A quest for smaller state FSSP solutions has been an interesting problem for a long time. Umeo, Kamikawa and Yunès (2009) answered partially by introducing a concept of partial FSSP solutions and proposed a full list of the smallest four-state symmetric powers-of-2 FSSP protocols that can synchronize any one-dimensional (1D) ring cellular automata of length $$n=2^{k}$$ for any positive integer $$k \ge 1$$. Afterwards, Ng (2011) also added a list of asymmetric FSSP partial solutions, thus completing the four-state powers-of-2 FSSP partial solutions. The number four is the lower bound in the class of FSSP protocols. A question: are there any four-state partial solutions other than powers-of-2? has remained open. In this paper, we answer the question by proposing a new class of the smallest symmetric and asymmetric four-state FSSP protocols that can synchronize any 1D ring of length $$n=2^{k}-1$$ for any positive integer $$k \ge 2$$. We show that the class includes a rich variety of FSSP protocols that consists of 39 symmetric and 132 asymmetric solutions, ranging from minimum-time to linear-time in synchronization steps. In addition, we make an investigation into several interesting properties of these partial solutions, such as swapping general states, reversal protocols, and a duality property between them.

## References

1. 1.
Balzer, R.: An 8-state minimal time solution to the firing squad synchronization problem. Inf. Control 10(1), 22–42 (1967).
2. 2.
Berthiaume, A., Bittner, T., Perković, L., Settle, A., Simon, J.: Bounding the firing synchronization problem on a ring. Theor. Comput. Sci. 320(2–3), 213–228 (2004).
3. 3.
Gerken, H.D.: Über Synchronisationsprobleme bei Zellularautomaten. Diplomarbeit, Institut für Theoretische Informatik, Technische Universität Braunschweig (1987)Google Scholar
4. 4.
Goto, E.: A minimal time solution of the firing squad problem. Dittoed Course Notes Appl. Math. 298(with an illustration in color), 52–59 (1962)Google Scholar
5. 5.
Mazoyer, J.: A six-state minimal time solution to the firing squad synchronization problem. Theor. Comput. Sci. 50, 183–238 (1987)
6. 6.
Moore, E.F.: The firing squad synchronization problem. In: Moore, E.F. (ed.) Sequential Machines, Selected Papers, pp. 213–214. Addison-Wesley, Reading (1964)
7. 7.
Ng, W.L.: Partial Solutions for the Firing Squad Synchronization Problem on Rings. ProQuest Publications, Ann Arbor (2011)Google Scholar
8. 8.
Sanders, P.: Massively parallel search for transition-tables of polyautomata. In: Jesshope, C., Jossifov, V., Wilhelmi, W. (eds.) Proc. of 6th Int, Workshop on Parallel Processing by Cellular Automata and Arrays, pp. 99–108. Akademie (1994)Google Scholar
9. 9.
Umeo, H., Kamikawa, N., Yunès, J.-B.: A family of smallest symmetrical four-state firing squad synchronization protocols for ring arrays. Parallel Process. Lett. 19(2), 299–313 (2009).
10. 10.
Umeo, H., Yanagihara, T.: A smallest five-state solution to the firing squad synchronization problem. In: Durand-Lose, J., Margenstern, M. (eds.) MCU 2007. LNCS, vol. 4664, pp. 291–302. Springer, Heidelberg (2007).
11. 11.
Waksman, A.: An optimum solution to the firing squad synchronization problem. Inf. Control 9(1), 66–78 (1966).
12. 12.
Yunès, J.-B.: A 4-states algebraic solution to linear cellular automata synchronization. Inf. Process. Lett. 107(2), 71–75 (2008).