Additive Cellular Automata with External Inputs
D. K. Arrowsmith
R. A. Dow
School of Mathematical Sciences,
Queen Mary and Westfield College,
University of London, Mile End Road,
London E1 4NS, England
Abstract
In this paper we consider a form of cellular automata (CA) that allows for external input at each stage of its evolution. The investigation is carried out from an algebraic viewpoint whereby the state structure of the CA, together with its action, can be interpreted ring-theoretically.
Specifically, we consider the structure of attractors for different controls and the associated tree structures of the states that approach the attractor. In particular, we relate the invariant sets that arise for controlled and uncontrolled CA and give properties on the number of states in the invariant set. Algebraic properties of the CA ring are used to qualify properties of cycle lengths and number of cycles.
A qualitative equivalence for CA is introduced and equivalence of attractors is characterized by the cycle set structure for different inputs. Sufficient conditions for qualitative equivalence in the presence of distinct inputs are found, and necessary and sufficient conditions for qualitative equivalence in the presence of distinct inputs are given when an extra condition holds.
Finally, the algebraic properties of CA associated with periodic input are investigated, and some generalizations are discussed.
