Abstract

A cellular automaton (CA) is a discrete dynamical system, and the transition graph is a representation of the CA's phase space. Automorphisms of the transition graph correspond to symmetries of the phase space; studying how the total number of automorphisms varies with the number of cells on which the CA operates yields a (partial) classification of the space of CA rules according to their dynamical behaviour.

In the general case, to find the number of automorphisms we must iterate over the entire transition graph; thus the time complexity is exponential with respect to the number of cells. However, if the CA is linear, the transition graph has properties which allow the number of automorphisms to be computed much more efficiently. In this paper, we investigate the numbers of automorphisms for a particular linear CA, elementary rule 90 . We observe a relationship between the number of automorphisms and a number theoretical function, the suborder function .

@inproceedings(SS-Automata08,
  author = "Edward J. Powley and Susan Stepney",
  title = "Automorphisms of transition graphs for a linear cellular automaton",
  pages = "55-68",
  crossref = "Automata08",
)

@proceedings(Automata08,
  editors = "A. Adamatzky and R. Alonso-Sanz and A. Lawniczak
            and G. J. Martinez and K. Morita and T. Worsch",
  title = "Automata 2008, Bristol, UK, June 2008",
  booktitle = "Automata 2008, Bristol, UK, June 2008",
  publisher = "Luniver Press",
  year = 2008
)