Regular Language Invariance under One-Dimensional Cellular Automaton Rules
Lenore Levine
Department of Mathematics, University of Illinois,
273 Altgeld Hall, 1409 W. Green St., Urbana, IL 61801, USA
Abstract
Procedures are given for determining regular language invariance under one-dimensional cellular automaton rules. A metric is defined for the space of all one-dimensional cellular automaton rules over a given alphabet 
. It is shown that under this metric, for certain regular languages, the set of rules under which the language is invariant contains no interior, and its complement contains no interior. Characteristics of surjective rules (rules under which the regular language 
is invariant) are also explored. Examples are given of a sequence of rules for which the limit language of the limit rule is not invariant under any rule in the sequence. Numerical experiments indicate that these rules do indeed display discontinuous behavior.
