论文标题
在具有多个速度的一维CA中，FSSP的更快算法
A faster algorithm for the FSSP in one-dimensional CA with multiple speeds
论文作者
论文摘要
在每个单元$ i $的蜂窝自动机中，有一个正整数$ p_i $，因此该单元格仍然定期更新其状态，但有时仅是$ p_i $的倍数。此外，所有$ p_i $都有有限的上限。 Manzoni和Umeo描述了这些（一维的）细胞自动机的算法，该算法解决了点火小队同步问题。该算法需要线性时间（在要同步的单元格数中），但是对于许多问题实例，它比最佳时间慢，而某个正常数因子。在本文中，我们在可能的同步时间上得出了下限，并描述了一种算法，在某些情况下，该算法比Manzoni和Umeo的算法更快，并且在更多情况下接近下限（恒定汇总）。
In cellular automata with multiple speeds for each cell $i$ there is a positive integer $p_i$ such that this cell updates its state still periodically but only at times which are a multiple of $p_i$. Additionally there is a finite upper bound on all $p_i$. Manzoni and Umeo have described an algorithm for these (one-dimensional) cellular automata which solves the Firing Squad Synchronization Problem. This algorithm needs linear time (in the number of cells to be synchronized) but for many problem instances it is slower than the optimum time by some positive constant factor. In the present paper we derive lower bounds on possible synchronization times and describe an algorithm which is never slower and in some cases faster than the one by Manzoni and Umeo and which is close to a lower bound (up to a constant summand) in more cases.
