Amenable groups and cellular automata

Tullio G. Ceccherini-Silberstein; Antonio Machi; Fabio Scarabotti

Annales de l'institut Fourier (1999)

  • Volume: 49, Issue: 2, page 673-685
  • ISSN: 0373-0956

Abstract

top
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.

How to cite

top

Ceccherini-Silberstein, Tullio G., Machi, Antonio, and Scarabotti, Fabio. "Amenable groups and cellular automata." Annales de l'institut Fourier 49.2 (1999): 673-685. <http://eudml.org/doc/75350>.

@article{Ceccherini1999,
abstract = {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.},
author = {Ceccherini-Silberstein, Tullio G., Machi, Antonio, Scarabotti, Fabio},
journal = {Annales de l'institut Fourier},
keywords = {amenable groups; Cayley graph; cellular automaton; garden of Eden},
language = {eng},
number = {2},
pages = {673-685},
publisher = {Association des Annales de l'Institut Fourier},
title = {Amenable groups and cellular automata},
url = {http://eudml.org/doc/75350},
volume = {49},
year = {1999},
}

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
PB - Association des Annales de l'Institut Fourier
VL - 49
IS - 2
SP - 673
EP - 685
AB - 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.
LA - eng
KW - amenable groups; Cayley graph; cellular automaton; garden of Eden
UR - http://eudml.org/doc/75350
ER -

References

top
  1. [A] S.I. ADYAN, Random walks on free periodic groups, Math. USSR Izvestiya, 21-3 (1983) 425-434. Zbl0528.60011
  2. [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. Zbl0348.94056MR51 #5203
  3. [BCG] E.R. BERLEKAMP, J.H. CONWAY and R.K. GUY, Winning Ways for your mathematical plays, vol 2, Chapter 25, Academic Press, 1982. Zbl0485.00025
  4. [CG] T.G. CECCHERINI-SILBERSTEIN and R.I. GRIGORCHUK, Amenability and growth of one-relator groups, Enseign. Math., 43 (1997), 337-354. Zbl0897.20022MR99b:20057
  5. [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. Zbl0968.43002
  6. [F] H. FURSTENBERG, private communication. 
  7. [G] R.I. GRIGORCHUK, Degrees of growth of finitely generated groups and the theory of invariant means, Math USSR Izvestiya, 25 (1985), 259-300. Zbl0583.20023
  8. [Gr] F.P. GREENLEAF, Invariant Means on Topological Groups, New York: van Nostrand, 1969. Zbl0174.19001MR40 #4776
  9. [Gro] M. GROMOV, Endomorphisms of symbolic algebraic varieties, preprint IHES/M/98/56, 1998. Zbl0998.14001
  10. [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. Zbl0768.68103MR95a:68084
  11. [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. Zbl0233.94026
  12. [My] J. MYHILL, The converse of Moore's Garden of Eden Theorem, Proc. Amer. Math. Soc., 14 (1963), 685-686. Zbl0126.32501MR27 #5698
  13. [vN1] J. von NEUMANN, The Theory of Self-Reproducing Automata, A. Burks ed., University of Illinois Press, Urbana, IL 1966. 
  14. [vN2] J. von NEUMANN, Zur allgemeinen Theorie des Masses, Fund. Math., 13 (1930), 73-116. Zbl55.0151.01JFM55.0151.01
  15. [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. Zbl0452.20032MR82b:43002

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.