Maximal Temporal Period of a Periodic Solution Generated by a One-Dimensional Cellular Automaton

Abstract

One-dimensional cellular automata evolutions with both temporal and spatial periodicity are studied. The main objective is to investigate the longest temporal periods among all two-neighbor rules, with a fixed spatial period s and number of states n. When sigma = 2, 3, 4 or 6, and the rules are restricted to be additive, the longest period can be expressed as the exponent of the multiplicative group of an appropriate ring. Non-additive rules are also constructed with temporal period on the same order as the trivial upper bound n(sigma). Experimental results, open problems and possible extensions of the results are also discussed.