Garden of Eden Configurations for Cellular Automata on Cayley Graphs of Groups
Antonio Machı̀, Filippo Mignosi · SIAM Journal on Discrete Mathematics · 1993
The tessellation of the plane given by square cells of equal size can be considered the Cayley graph of the free abelian group of rank 2. This group has polynomial growth. The theorems of Moore [Symposium on Applied Mathematics, Vol. XIV, American Mathematical Society, Providence, Rhode Island, 1962, pp. 17–33] and Myhill [Proceedings of the American Mathematical Society, 14 (1963), pp. 685–686] on the existence of Garden of Eden configurations for an automaton defined on such a graph are extended to Cayley graphs of groups whose growth function is not exponential. Examples are given of Cayley graphs of groups of exponential growth for which these theorems do not hold.