Developments of Smallest Synchronization Protocols and Its Application to Multi-Dimensional Cellular Arrays

研究了行刑队同步问题(FSSP)，给出了元胞自动机(CA)的有限状态同步协议。在这个研究项目中，我们不仅研究了一维(1D)的更小的FSSP解，而且研究了多维CA的FSSP解。我们给出了一类一维CA的最小四态部分解。结果表明，二维方阵存在一个7态方同步器，这是目前已知的方阵的最小解。我们还证明了二维矩形阵列存在九态FSSP解。最后，我们提出了一类新的基于递归对半标记的多维时间最优FSSP算法。

We study a firing squad synchronization problem(FSSP) that gives a finite-state protocol for synchronizing cellular automata(CA). In this research project, we made an investigation into smaller FSSP solutions not only for one-dimensional(1D) but multi-dimensional CAs. We present a class of smallest 4-state partial solutions for 1D the CAs. It is shown that there exists a 7-state square synchronizer for 2D square arrays, which is a smallest solution for square arrays, known at present. We also show that there exists a nine-state FSSP solution for 2D rectangular arrays. In the last, we have proposed a new class of optimum-time multi-dimensional FSSP algorithms based on recursive-halving marking.