Affiliations: Hiroshima University, Faculty of Engineering,
Higashi-Hiroshima, 739-8527, Japan
Abstract: We study the Firing Squad Synchronization Problem (FSSP) on a
cellular automaton (CA) having number-conservation property. In a
number-conserving CA, all states of cells are represented by (tuples of)
non-negative integers and the total number of its configuration is conserved
throughout its computing processes. But, if we use a usual framework of CA in
which each state of a cell is represented by a single integer, it is not
possible to make every cell to be in the same firing state, which should be
different from the soldier state, under the usual FSSP condition without
violating the number-conservativeness. So, we employ the framework of a
partitioned cellular automaton, and define a number-conserving partitioned
cellular automaton (NC-PCA). Its cell is divided into three parts, and hence
each cell is represented by a triple of non-negative integers. In NC-PCA, only
the constraint that the local transition function should satisfy a
number-conserving condition is supposed. Thus, it makes relatively easy to
construct an NC-PCA. Because each cell can hold three non-negative integers, it
is possible to represent different states even if the sum of three numbers are
equal. Using this technique, we show that Minsky's 3n time solution can be
embedded into an NC-PCA, having an integer at most 9 in each part of a
cell.
