Amenable groups and cellular automata
Ceccherini-Silberstein, Tullio G. ; Machi, Antonio ; Scarabotti, Fabio
Annales de l'Institut Fourier, Tome 49 (1999), p. 673-685 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

On étend les théorèmes “Jardin d’Eden” de Moore et Myhill au cas des automates cellulaires dont l’univers est un graphe de Cayley d’un groupe finiment engendré moyennable. On obtient ainsi une extension du résultat analogue de A. Machi et F. Mignosi pour les groupes à croissance sub-exponentielle.

We show that the theorems of Moore and Myhill hold for cellular automata whose universes are Cayley graphs of amenable finitely generated groups. This extends the analogous result of A. Machi and F. Mignosi “Garden of Eden configurations for cellular automata on Cayley graphs of groups” for groups of sub-exponential growth.

@article{AIF_1999__49_2_673_0,
     author = {Ceccherini-Silberstein, Tullio G. and Machi, Antonio and Scarabotti, Fabio},
     title = {Amenable groups and cellular automata},
     journal = {Annales de l'Institut Fourier},
     volume = {49},
     year = {1999},
     pages = {673-685},
     doi = {10.5802/aif.1686},
     mrnumber = {2000k:43001},
     zbl = {0920.43001},
     language = {en},
     url = {http://dml.mathdoc.fr/item/AIF_1999__49_2_673_0}
}

Ceccherini-Silberstein, Tullio G.; Machi, Antonio; Scarabotti, Fabio. Amenable groups and cellular automata. Annales de l'Institut Fourier, Tome 49 (1999) pp. 673-685. doi : 10.5802/aif.1686. http://gdmltest.u-ga.fr/item/AIF_1999__49_2_673_0/

[A] S.I. Adyan, Random walks on free periodic groups, Math. USSR Izvestiya, 21-3 (1983) 425-434. | Zbl 0528.60011

[ACP] S. Amoroso, G. Cooper and Y. Patt, Some clarifications of the concept of Garden of Eden configuration, J. Comput. Sci., 10 (1975), 77-82. | MR 51 #5203 | Zbl 0348.94056

[BCG] E.R. Berlekamp, J.H. Conway and R.K. Guy, Winning Ways for your mathematical plays, vol 2, Chapter 25, Academic Press, 1982. | Zbl 0485.00025

[CG] T.G. Ceccherini-Silberstein and R.I. Grigorchuk, Amenability and growth of one-relator groups, Enseign. Math., 43 (1997), 337-354. | MR 99b:20057 | Zbl 0897.20022

[CGH] T. Ceccherini-Silberstein, R. Grigorchuk and P. De La Harpe, Amenability and paradoxical decompositions for pseudogroups and for discrete metric spaces, Proc. Steklov Math. Inst., to appear. | Zbl 0968.43002

[F] H. Furstenberg, private communication.

[G] R.I. Grigorchuk, Degrees of growth of finitely generated groups and the theory of invariant means, Math USSR Izvestiya, 25 (1985), 259-300. | Zbl 0583.20023

[Gr] F.P. Greenleaf, Invariant Means on Topological Groups, New York: van Nostrand, 1969. | MR 40 #4776 | Zbl 0174.19001

[Gro] M. Gromov, Endomorphisms of symbolic algebraic varieties, preprint IHES/M/98/56, 1998. | Zbl 01294431

[MaMi] A. Machì and F. Mignosi, Garden of Eden configurations for cellular automata on Cayley graphs of groups, SIAM J. Disc. Math., 6 (1993), 44-56. | MR 95a:68084 | Zbl 0768.68103

[Mo] E.F. Moore, Machine models of self-reproduction, in Essays on Cellular Automata, Arthur B. Burks ed., University of Illinois Press, Urbana, Chicago, London, 1970. | Zbl 0233.94026

[My] J. Myhill, The converse of Moore's Garden of Eden Theorem, Proc. Amer. Math. Soc., 14 (1963), 685-686. | MR 27 #5698 | Zbl 0126.32501

[vN1] J. Von Neumann, The Theory of Self-Reproducing Automata, A. Burks ed., University of Illinois Press, Urbana, IL 1966.

[vN2] J. Von Neumann, Zur allgemeinen Theorie des Masses, Fund. Math., 13 (1930), 73-116. | JFM 55.0151.01

[O] A. Yu Ol'Shanski, On the question of the existence of an invariant mean on a group. (Russian) Uspekhi Mat. Nauk, 35 (1980), n° 4 (214), 199-200. | MR 82b:43002 | Zbl 0452.20032