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},
     mrnumber = {2000k:43001},
     zbl = {0920.43001},
     language = {en},
     url = {https://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  - https://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 https://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. https://www.numdam.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

  • Huang, Xiaojun; Zhang, Qin The Garden of Eden Theorem over Generalized Cellular Automata, Bulletin of the Malaysian Mathematical Sciences Society, Volume 47 (2024) no. 4 | DOI:10.1007/s40840-024-01719-y
  • Phung, Xuan Kien Stable finiteness of twisted group rings and noisy linear cellular automata, Canadian Journal of Mathematics, Volume 76 (2024) no. 4, p. 1089 | DOI:10.4153/s0008414x23000329
  • Ceccherini-Silberstein, Tullio; Coornaert, Michel; Li, Hanfeng Expansive actions with specification of sofic groups, strong topological Markov property, and surjunctivity, Journal of Functional Analysis, Volume 286 (2024) no. 9, p. 110376 | DOI:10.1016/j.jfa.2024.110376
  • Phung, Xuan Kien On linear non-uniform cellular automata: Duality and dynamics, Linear Algebra and its Applications, Volume 688 (2024), p. 78 | DOI:10.1016/j.laa.2024.02.011
  • Phung, Xuan Kien On the Garden of Eden theorem for non-uniform cellular automata, Nonlinearity, Volume 37 (2024) no. 6, p. 065012 | DOI:10.1088/1361-6544/ad3ffa
  • Ceccherini-Silberstein, Tullio; Coornaert, Michel The Garden of Eden Theorem, Cellular Automata and Groups (2023), p. 151 | DOI:10.1007/978-3-031-43328-3_5
  • DOUCHA, MICHAL Garden of Eden and weakly periodic points for certain expansive actions of groups, Ergodic Theory and Dynamical Systems, Volume 43 (2023) no. 7, p. 2354 | DOI:10.1017/etds.2022.37
  • PHUNG, XUAN KIEN On images of subshifts under embeddings of symbolic varieties, Ergodic Theory and Dynamical Systems, Volume 43 (2023) no. 9, p. 3131 | DOI:10.1017/etds.2022.48
  • Phung, Xuan Kien On invertible and stably reversible non-uniform cellular automata, Theoretical Computer Science, Volume 940 (2023), p. 43 | DOI:10.1016/j.tcs.2022.09.011
  • Phung, Xuan Kien On Invertible And Stably Reversible Non-Uniform Cellular Automata, SSRN Electronic Journal (2022) | DOI:10.2139/ssrn.4106365
  • Lind, Douglas; Marcus, Brian An Introduction to Symbolic Dynamics and Coding, 2021 | DOI:10.1017/9781108899727
  • Ceccherini-Silberstein, Tullio; Coornaert, Michel Expansive Actions with Specification on Uniform Spaces, Topological Entropy, and the Myhill Property, Journal of Dynamical and Control Systems, Volume 27 (2021) no. 3, p. 427 | DOI:10.1007/s10883-020-09485-3
  • Phung, Xuan Kien On sofic groups, Kaplansky's conjectures, and endomorphisms of pro-algebraic groups, Journal of Algebra, Volume 562 (2020), p. 537 | DOI:10.1016/j.jalgebra.2020.05.037
  • Bhattacharjee, Kamalika; Naskar, Nazma; Roy, Souvik; Das, Sukanta A survey of cellular automata: types, dynamics, non-uniformity and applications, Natural Computing, Volume 19 (2020) no. 2, p. 433 | DOI:10.1007/s11047-018-9696-8
  • Ceccherini-Silberstein, Tullio; Coornaert, Michel; Phung, Xuan Kien On the Garden of Eden theorem for endomorphisms of symbolic algebraic varieties, Pacific Journal of Mathematics, Volume 306 (2020) no. 1, p. 31 | DOI:10.2140/pjm.2020.306.31
  • Gajardo, A.; Nesme, V.; Theyssier, G. Pre-expansivity in cellular automata, Theoretical Computer Science, Volume 816 (2020), p. 37 | DOI:10.1016/j.tcs.2019.10.034
  • Ceccherini-Silberstein, Tullio; Coornaert, Michel; Li, Hanfeng Homoclinically Expansive Actions and a Garden of Eden Theorem for Harmonic Models, Communications in Mathematical Physics, Volume 368 (2019) no. 3, p. 1175 | DOI:10.1007/s00220-019-03320-y
  • LI, HANFENG Garden of Eden and specification, Ergodic Theory and Dynamical Systems, Volume 39 (2019) no. 11, p. 3075 | DOI:10.1017/etds.2018.6
  • Bartholdi, Laurent Amenability of Groups and G-Sets, Sequences, Groups, and Number Theory (2018), p. 433 | DOI:10.1007/978-3-319-69152-7_11
  • Capobianco, Silvio; Kari, Jarkko; Taati, Siamak An “almost dual” to Gottschalk’s Conjecture, Cellular Automata and Discrete Complex Systems, Volume 9664 (2016), p. 77 | DOI:10.1007/978-3-319-39300-1_7
  • Castillo-Ramirez, Alonso; Gadouleau, Maximilien Ranks of finite semigroups of one-dimensional cellular automata, Semigroup Forum, Volume 93 (2016) no. 2, p. 347 | DOI:10.1007/s00233-016-9783-z
  • Ceccherini-Silberstein, Tullio; Coornaert, Michel A Garden of Eden theorem for Anosov diffeomorphisms on tori, Topology and its Applications, Volume 212 (2016), p. 49 | DOI:10.1016/j.topol.2016.08.025
  • Ceccherini-Silberstein, Tullio; Coornaert, Michel Expansive actions of countable amenable groups, homoclinic pairs, and the Myhill property, Illinois Journal of Mathematics, Volume 59 (2015) no. 3 | DOI:10.1215/ijm/1475266399
  • Ceccherini-Silberstein, Tullio; Coornaert, Michel On surjunctive monoids, International Journal of Algebra and Computation, Volume 25 (2015) no. 04, p. 567 | DOI:10.1142/s0218196715500113
  • Kari, Jarkko; Taati, Siamak Statistical Mechanics of Surjective Cellular Automata, Journal of Statistical Physics, Volume 160 (2015) no. 5, p. 1198 | DOI:10.1007/s10955-015-1281-2
  • Sawamura, Jitsuki; Morishita, Shigeru; Ishigooka, Jun A symmetry model for genetic coding via a wallpaper group composed of the traditional four bases and an imaginary base E: Towards category theory-like systematization of molecular/genetic biology, Theoretical Biology and Medical Modelling, Volume 11 (2014) no. 1 | DOI:10.1186/1742-4682-11-18
  • Ceccherini-Silberstein, Tullio; Coornaert, Michel; Fiorenzi, Francesca; Šunić, Zoran Cellular automata between sofic tree shifts, Theoretical Computer Science, Volume 506 (2013), p. 79 | DOI:10.1016/j.tcs.2013.07.007
  • Ceccherini-Silberstein, Tullio; Coornaert, Michel Surjunctivity and Reversibility of Cellular Automata over Concrete Categories, Trends in Harmonic Analysis, Volume 3 (2013), p. 91 | DOI:10.1007/978-88-470-2853-1_6
  • Ceccherini‐Silberstein, Tullio; Coornaert, Michel Cellular Automata and Groups, Computational Complexity (2012), p. 336 | DOI:10.1007/978-1-4614-1800-9_23
  • Pivato, Marcus Ergodic Theory of Cellular Automata, Computational Complexity (2012), p. 965 | DOI:10.1007/978-1-4614-1800-9_62
  • CECCHERINI-SILBERSTEIN, TULLIO; COORNAERT, MICHEL A Garden of Eden theorem for linear subshifts, Ergodic Theory and Dynamical Systems, Volume 32 (2012) no. 1, p. 81 | DOI:10.1017/s0143385710000921
  • Ceccherini-Silberstein, Tullio; Coornaert, Michel; Fiorenzi, Francesca; Schupp, Paul E. Groups, graphs, languages, automata, games and second-order monadic logic, European Journal of Combinatorics, Volume 33 (2012) no. 7, p. 1330 | DOI:10.1016/j.ejc.2012.03.010
  • Ceccherini-Silberstein, Tullio; Coornaert, Michel The Myhill property for strongly irreducible subshifts over amenable groups, Monatshefte für Mathematik, Volume 165 (2012) no. 2, p. 155 | DOI:10.1007/s00605-010-0256-2
  • Capobianco, Silvio Generalized Besicovitch and Weyl spaces: Topology, patterns, and sliding block codes, Theoretical Computer Science, Volume 412 (2011) no. 30, p. 3822 | DOI:10.1016/j.tcs.2011.02.020
  • Ceccherini-Silberstein, Tullio; Coornaert, Michel Cellular Automata and Groups, Cellular Automata (2009), p. 221 | DOI:10.1007/978-1-4939-8700-9_52
  • Pivato, Marcus Ergodic Theory of Cellular Automata, Cellular Automata (2009), p. 373 | DOI:10.1007/978-1-4939-8700-9_178
  • Margenstern, Maurice About the Garden of Eden Theorems for Cellular Automata in the Hyperbolic Plane, Electronic Notes in Theoretical Computer Science, Volume 252 (2009), p. 93 | DOI:10.1016/j.entcs.2009.09.016
  • Pivato, Marcus Ergodic Theory of Cellular Automata, Encyclopedia of Complexity and Systems Science (2009), p. 2980 | DOI:10.1007/978-0-387-30440-3_178
  • Ceccherini‐Silberstein, Tullio; Coornaert, Michel Cellular Automata and Groups, Encyclopedia of Complexity and Systems Science (2009), p. 778 | DOI:10.1007/978-0-387-30440-3_52
  • MÜLLER, JOHANNES; SPANDL, CHRISTOPH Embeddings of dynamical systems into cellular automata, Ergodic Theory and Dynamical Systems, Volume 29 (2009) no. 1, p. 165 | DOI:10.1017/s0143385708080036
  • CECCHERINI-SILBERSTEIN, TULLIO; COORNAERT, MICHEL Induction and restriction of cellular automata, Ergodic Theory and Dynamical Systems, Volume 29 (2009) no. 2, p. 371 | DOI:10.1017/s0143385708080437
  • Capobianco, Silvio On the induction operation for shift subspaces and cellular automata as presentations of dynamical systems, Information and Computation, Volume 207 (2009) no. 11, p. 1169 | DOI:10.1016/j.ic.2009.02.006
  • Ceccherini-Silberstein, Tullio; Coornaert, Michel Amenability and Linear Cellular Automata Over Semisimple Modules of Finite Length, Communications in Algebra, Volume 36 (2008) no. 4, p. 1320 | DOI:10.1080/00927870701864015
  • Capobianco, Silvio Induced Subshifts and Cellular Automata, Language and Automata Theory and Applications, Volume 5196 (2008), p. 160 | DOI:10.1007/978-3-540-88282-4_16
  • Martin, Bruno; Peyrat, Claudine A single-copy minimal-time simulation of a torus of automata by a ring of automata, Discrete Applied Mathematics, Volume 155 (2007) no. 16, p. 2130 | DOI:10.1016/j.dam.2007.05.019
  • Ceccherini-Silberstein, Tullio; Coornaert, Michel Linear cellular automata over modules of finite length and stable finiteness of group rings, Journal of Algebra, Volume 317 (2007) no. 2, p. 743 | DOI:10.1016/j.jalgebra.2007.06.035
  • Glebsky, L. Yu.; Gordon, E. I. ON SURJUNCTIVITY OF THE TRANSITION FUNCTIONS OF CELLULAR AUTOMATA ON GROUPS, Taiwanese Journal of Mathematics, Volume 9 (2005) no. 3 | DOI:10.11650/twjm/1500407858
  • Fiorenzi, Francesca Semi-strongly irreducible shifts, Advances in Applied Mathematics, Volume 32 (2004) no. 3, p. 421 | DOI:10.1016/s0196-8858(03)00053-8
  • Fiorenzi, Francesca Cellular automata and strongly irreducible shifts of finite type, Theoretical Computer Science, Volume 299 (2003) no. 1-3, p. 477 | DOI:10.1016/s0304-3975(02)00492-9

Cité par 49 documents. Sources : Crossref