Automorphisms of transition graphs for linear cellular automata.

The
*
transition graph
*
of a cellular automaton (CA) represents
the CA's global dynamics. The
*
automorphisms
*
of the transition
graph are its self-isomorphisms or "symmetries", and in a
sense these are precisely the symmetries of the CA's dynamics.

Previously we have argued that studying how the total number of
automorphisms varies with the number of cells on which the CA operates
yields a partial classification of CA rules. One of the classes thus
identified consists mainly of
*
linear
*
CAs; that is, CAs whose
local rules are linear functions.

In this paper, we use the algebraic properties of linear CAs in
general, and of one linear CA (elementary rule 90) in particular, to
derive an expression for the number of automorphisms admitted by that
CA. We use this expression to produce numerical results, and observe
that the number of automorphisms as a function of the number of cells
exhibits a correlation with a number-theoretic function, the
*
suborder
function
*
.

**
Full paper
**
:
PDF
236K |
a
*
revised
*
and
*
generalised
*
version of the
*
Automata
2008
*
paper

@article(SS-JCA-09, author = "Edward J. Powley and Susan Stepney", title = "Automorphisms of transition graphs for linear cellular automata", journal = "Journal of Cellular Automata", volume = 4, number = 4, pages = "293-310", year = 2009 )