THE FIRING SQUAD SYNCHRONIZATION PROBLEM WITH MANY GENERALS FOR ONE-DIMENSIONAL CA

摘要

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 optimum-time 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.