no. 2
Amenable groups and cellular automata
Annales de l'Institut Fourier, Tome 49 (1999) no. 2, pp. 673-685.

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},
     pages = {673--685},
     publisher = {Association des Annales de l{\textquoteright}institut Fourier},
     volume = {49},
     number = {2},
     year = {1999},
     doi = {10.5802/aif.1686},
     zbl = {0920.43001},
     mrnumber = {2000k:43001},
     language = {en},
     url = {https://aif.centre-mersenne.org/articles/10.5802/aif.1686/}
}
TY  - JOUR
AU  - Ceccherini-Silberstein, Tullio G.
AU  - Machi, Antonio
AU  - Scarabotti, Fabio
TI  - Amenable groups and cellular automata
JO  - Annales de l'Institut Fourier
PY  - 1999
SP  - 673
EP  - 685
VL  - 49
IS  - 2
PB  - Association des Annales de l’institut Fourier
UR  - https://aif.centre-mersenne.org/articles/10.5802/aif.1686/
DO  - 10.5802/aif.1686
LA  - en
ID  - AIF_1999__49_2_673_0
ER  - 
%0 Journal Article
%A Ceccherini-Silberstein, Tullio G.
%A Machi, Antonio
%A Scarabotti, Fabio
%T Amenable groups and cellular automata
%J Annales de l'Institut Fourier
%D 1999
%P 673-685
%V 49
%N 2
%I Association des Annales de l’institut Fourier
%U https://aif.centre-mersenne.org/articles/10.5802/aif.1686/
%R 10.5802/aif.1686
%G en
%F 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) no. 2, pp. 673-685. doi : 10.5802/aif.1686. https://aif.centre-mersenne.org/articles/10.5802/aif.1686/

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

[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 | Zbl

[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

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

[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

[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

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

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

[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 | Zbl

[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

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

[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

[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 | Zbl

Cité par Sources :