Some Cellular Fields Interrelations and Optimizations in FSSP Solutions
Tien Thao Nguyen and Luidnel Maignan
A large number of cellular automata have been given as a transition table constructed by hand. The methodology of “cellular fields” propose to give them by their modular design principles instead, and to generate the transition table in last step, as it is the case for high-level programming language source code and their binary executable file. In this paper, we check whether this generated tables can be optimized to be as small as their counterpart constructed by hand. This is done in the particular case of a cellular automaton solving the Firing Squad Synchronization Problem using cellular fields. We study the internal structure of this solution and study their reductions in the same vein as deterministic finite automata minimization. We also compare this solution with the solutions of Noguchi and devise another notion of optimization.
Keywords: Cellular automata, automata minimization, program optimization, firing squad synchronization problem