Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
1993 | 10.1137/0406004 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
eden configuration,cellular automaton,cayley graph,cayley graphs,cellular automata,automata | Discrete mathematics,Cellular automaton,Free abelian group,Automata theory,Combinatorics,Vertex-transitive graph,Cayley table,Cayley's theorem,Cayley graph,Garden of Eden,Mathematics | Journal |
Volume | Issue | ISSN |
6 | 1 | 0895-4801 |
Citations | PageRank | References |
13 | 1.83 | 1 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Antonio Machì | 1 | 19 | 2.48 |
Filippo Mignosi | 2 | 569 | 99.71 |