Complex Systems 11 (1997) 55-64.
We study the algebraic conditions under which two cellular automata can commute. We show that if either rule is permutive, i.e. one-to-one on its leftmost and rightmost inputs, then the other rule can be written in terms of it; if either rule is a group, then the other is linear in it; and if either is permutive and affine, i.e. linear up to a constant, then the other must also be affine. We also prove some simple results regarding the existence of identities, idempotents (quiescent states) and zeroes (absorbing states).