The Firing Squad Synchronization Problem with Many Generals For One-Dimensional CA
The Firing Squad Synchronization Problem with Many Generals For One-Dimensional CA
复制标题
一维 CA 的多将军行刑队同步问题
DOI：
10.1007/1-4020-8141-3_11
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
T. Worsch
中科院分区：
文献类型：
--
作者：
H. Schmid;T. Worsch
射击队同步问题是元胞自动机的经典问题之一。在本文中，我们考虑不止一位将军的情况。考虑问题的同步和异步版本。在后一种情况下，将军们可能会在不同的时间开始他们的活动。在同步情况下，存在最佳时间解决方案。构建其中一个的非常简单而优雅的技术是本文在算法方面的主要贡献。对于异步情况，导出了每个实例的最佳同步时间的精确公式。我们证明没有一个 CA 可以在最佳时间内解决所有实例，但我们描述了一个运行时间非常接近它的 CA；它只需要额外的 log n 步骤。
The Firing Squad Synchronization Problem is one of the classical problems for cellular automata. In this paper we consider the case of more than one general. A synchronous and an asynchronous version of the problem are considered. In the latter case the generals may start their activities at different times. In the synchronous case there are optimumtime solutions. Very simple and elegant techniques for constructing one of them are the main contribution of this paper on the algorithmic side. For the asynchronous case an exact formula for the optimum synchronization time of each instance is derived. We prove that no CA can solve all instances in optimum time, but we describe a CA whose running time is very close to it; it only needs additional log n steps.