International Journal of Mathematics and Mathematical Sciences
Volume 8 (1985), Issue 3, Pages 579-587

Weak gardens of Eden for 1-dimensional tessellation automata

Michael D. Taylor

Mathematics Department, University of Central Florida, Orlando, Florida, USA

Received 16 July 1984

Copyright © 1985 Michael D. Taylor. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


If T is the parallel map associated with a 1-dimensional tessellation automaton, then we say a configuration f is a weak Garden of Eden for T if f has no pre-image under T other than a shift of itself. Let WG(T)= the set of weak Gardens of Eden for T and G(T)= the set of Gardens of Eden (i.e., the set of configurations not in the range of T). Typically members of WG(T)G(T) satisfy an equation of the form Tf=Smf where Sm is the shift defined by (Smf)(j)=f(j+m). Subject to a mild restriction on m, the equation Tf=Smf always has a solution f, and all such solutions are periodic. We present a few other properties of weak Gardens of Eden and a characterization of WG(T) for a class of parallel maps we call (0,1)-characteristic transformations in the case where there are at least three cell states.