A New Class of the Smallest 4-State Semi-symmetric FSSP Partial Solutions for 1D Arrays

A synchronization problem in cellular automata has been known as the Firing Squad Synchronization Problem (FSSP), 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. It has been shown by Balzer [1967], Sanders [1994], Berthiaume et al. [2004], and Ng [2011] that there exists no 4-state FSSP solution to one-dimensional (1D) arrays and rings. The number four is the state lower bound in the class of FSSP protocols. Umeo, Kamikawa and Yunès [2009], by introducing a notion of full versus partial FSSP solutions, provided a list of the smallest 4-state symmetric powers-of-2 FSSP solutions that can synchronize any 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 4-state powers-of-2 FSSP partial solutions. On the other hand, nothing has been explored for the smaller-state 1D array synchronizers. A question whether how many 4-state partial solutions there are for 1D arrays has been remained open. In this paper, we answer the question by providing a new class of the smallest 4-state FSSP partial solutions that can synchronize any 1D arrays of length \(n=2^{k}-1\) , \(2^{k}\) , and \(2^{k}+1\) for any positive integer \(k \ge 2\) . We present a class of the smallest 4-state semi-symmetric array synchronizers: 4 solutions for 1D arrays of length \(n=2^{k}-1\) , 415 solutions for length \(n=2^{k}\) , and 41 solutions for length \(n=2^{k}+1\) .