The firing squad synchronization problem for a class of polyautomata networks

摘要

By the work of Rosenstiehl we know that the firing squad synchronization problem for the class of all polyautomata networks N satisfying the following conditions has a solution: (1) N is connected, (2) the connections of N are bilateral (that is, each connection carries information in both directions). We show that the problem has a solution even if we delete condition (2) if we add the following conditions: (3) the “fan-out” of each output terminal of automata is at most one, (4) for each output terminal of an automaton, the automaton knows whether there is a connection from the output terminal or not. The firing time of our solution is at most (2a2 + 1)n for sufficiently large n (n is the number of finite automata in the given network and a is the number of output terminals of the component finite automaton).