Symmetries of the firing squad sychronization problem revealed in a nested array

ABSTRACT

The firing squad problem of automata theory is described and a simple, nonoptimal solution is given. Examination of output traces shows that the solution has at least one obvious symmetry. If the transition matrix is reshaped and partitioned, the resulting nested array not only reveals and explicates more symmetries but suggests ways in which nested arrays can be used to save space.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Arrays

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded)
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

General Terms:
Algorithms, Theory