Finitization of Infinite Field-based Multi-general FSSP Solution
Luidnel Maignan and Jean-Baptiste Yunès
In a previous work (see [3]) we presented a general schema to solve the 1D Generalized Firing Squad Synchronization Problem. We used a semantic approach and designed it in a modular way using the concept of fields (open CA). The proposed solution is not directly a finite cellular automaton because it needs unbounded integers in distance fields, and an unbounded stack of fields due to the recursive nature of the algorithm. In this paper, we extend the solution to tackle the multi-general problem and show that this approach does effectively leads to a finite cellular automaton. For this, we exhibit a projection function from infinite to finite states and write a program that generates the associated finite transition table. We finally sketch some theoretical arguments for the validity of the construction.
Keywords: Cellular automata, automata minimization, quotient automata, firing squad synchronization problem