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},
mrnumber = {2000k:43001},
zbl = {0920.43001},
language = {en},
url = {http://www.numdam.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 - http://www.numdam.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 http://www.numdam.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. http://www.numdam.org/articles/10.5802/aif.1686/
[A] , Random walks on free periodic groups, Math. USSR Izvestiya, 21-3 (1983) 425-434. | Zbl
[ACP] , and , Some clarifications of the concept of Garden of Eden configuration, J. Comput. Sci., 10 (1975), 77-82. | MR | Zbl
[BCG] , and , Winning Ways for your mathematical plays, vol 2, Chapter 25, Academic Press, 1982. | Zbl
[CG] and , Amenability and growth of one-relator groups, Enseign. Math., 43 (1997), 337-354. | MR | Zbl
[CGH] , and , Amenability and paradoxical decompositions for pseudogroups and for discrete metric spaces, Proc. Steklov Math. Inst., to appear. | Zbl
[F] , private communication.
[G] , Degrees of growth of finitely generated groups and the theory of invariant means, Math USSR Izvestiya, 25 (1985), 259-300. | Zbl
[Gr] , Invariant Means on Topological Groups, New York: van Nostrand, 1969. | MR | Zbl
[Gro] , Endomorphisms of symbolic algebraic varieties, preprint IHES/M/98/56, 1998. | Zbl
[MaMi] and , Garden of Eden configurations for cellular automata on Cayley graphs of groups, SIAM J. Disc. Math., 6 (1993), 44-56. | MR | Zbl
[Mo] , Machine models of self-reproduction, in Essays on Cellular Automata, Arthur B. Burks ed., University of Illinois Press, Urbana, Chicago, London, 1970. | Zbl
[My] , The converse of Moore's Garden of Eden Theorem, Proc. Amer. Math. Soc., 14 (1963), 685-686. | MR | Zbl
[vN1] , The Theory of Self-Reproducing Automata, A. Burks ed., University of Illinois Press, Urbana, IL 1966.
[vN2] , Zur allgemeinen Theorie des Masses, Fund. Math., 13 (1930), 73-116. | JFM
[O] , 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 :
