Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

The Myhill property for cellular automata on amenable semigroups


Authors: Tullio Ceccherini-Silberstein and Michel Coornaert
Journal: Proc. Amer. Math. Soc. 143 (2015), 327-339
MSC (2010): Primary 43A07, 37B15, 68Q80
DOI: https://doi.org/10.1090/S0002-9939-2014-12227-1
Published electronically: September 16, 2014
MathSciNet review: 3272758
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ S$ be a cancellative left-amenable semigroup and let $ A$ be a finite set. We prove that every pre-injective cellular automaton $ \tau \colon A^S \to A^S$ is surjective.


References [Enhancements On Off] (What's this?)

  • [1] Laurent Bartholdi, Gardens of Eden and amenability on cellular automata, J. Eur. Math. Soc. (JEMS) 12 (2010), no. 1, 241-248. MR 2578610 (2011e:05282), https://doi.org/10.4171/JEMS/196
  • [2] Tullio Ceccherini-Silberstein and Michel Coornaert, Cellular automata and groups, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2010. MR 2683112 (2011j:37002)
  • [3] T. Ceccherini-Silberstein, M. Coornaert, and F. Krieger, An analogue of Fekete's lemma for subadditive functions on cancellative amenable semigroups, Journal d'Analyse Mathématique (to appear), arXiv:1209.6179.
  • [4] T. G. Ceccherini-Silberstein, A. Machì, and F. Scarabotti, Amenable groups and cellular automata, Ann. Inst. Fourier (Grenoble) 49 (1999), no. 2, 673-685 (English, with English and French summaries). MR 1697376 (2000k:43001)
  • [5] Mahlon M. Day, Amenable semigroups, Illinois J. Math. 1 (1957), 509-544. MR 0092128 (19,1067c)
  • [6] J. Duncan and I. Namioka, Amenability of inverse semigroups and their semigroup algebras, Proc. Roy. Soc. Edinburgh Sect. A 80 (1978), no. 3-4, 309-321. MR 516230 (80a:43002), https://doi.org/10.1017/S0308210500010313
  • [7] Walter Gottschalk, Some general dynamical notions, Recent advances in topological dynamics (Proc. Conf. Topological Dynamics, Yale Univ., New Haven, Conn., 1972; in honor of Gustav Arnold Hedlund), Lecture Notes in Math., vol. 318, Springer, Berlin, 1973, pp. 120-125. MR 0407821 (53 #11591)
  • [8] Frederick P. Greenleaf, Invariant means on topological groups and their applications, Van Nostrand Mathematical Studies, No. 16, Van Nostrand Reinhold Co., New York, 1969. MR 0251549 (40 #4776)
  • [9] M. Gromov, Endomorphisms of symbolic algebraic varieties, J. Eur. Math. Soc. (JEMS) 1 (1999), no. 2, 109-197. MR 1694588 (2000f:14003), https://doi.org/10.1007/PL00011162
  • [10] Antonio Machì and Filippo Mignosi, Garden of Eden configurations for cellular automata on Cayley graphs of groups, SIAM J. Discrete Math. 6 (1993), no. 1, 44-56. MR 1201989 (95a:68084), https://doi.org/10.1137/0406004
  • [11] E. F. Moore, Machine models of self-reproduction, Proc. Symp. Appl. Math., 14, American Mathematical Society, Providence, RI, 1963, pp. 17-34.
  • [12] John Myhill, The converse of Moore's Garden-of-Eden theorem, Proc. Amer. Math. Soc. 14 (1963), 685-686. MR 0155764 (27 #5698)
  • [13] I. Namioka, Følner's conditions for amenable semi-groups, Math. Scand. 15 (1964), 18-28. MR 0180832 (31 #5062)
  • [14] Alan L. T. Paterson, Amenability, Mathematical Surveys and Monographs, vol. 29, American Mathematical Society, Providence, RI, 1988. MR 961261 (90e:43001)
  • [15] Benjamin Weiss, Sofic groups and dynamical systems, Ergodic theory and harmonic analysis (Mumbai, 1999), Sankhyā Ser. A 62 (2000), no. 3, 350-359. MR 1803462 (2001j:37022)
  • [16] Carroll Wilde and Klaus Witz, Invariant means and the Stone-Čech compactification, Pacific J. Math. 21 (1967), 577-586. MR 0212552 (35 #3423)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 43A07, 37B15, 68Q80

Retrieve articles in all journals with MSC (2010): 43A07, 37B15, 68Q80


Additional Information

Tullio Ceccherini-Silberstein
Affiliation: Dipartimento di Ingegneria, Università del Sannio, Corso Garibaldi 107, 82100 Benevento, Italy
Email: tceccher@mat.uniroma3.it

Michel Coornaert
Affiliation: Institut de Recherche Mathématique Avancée, UMR 7501, Université de Strasbourg et CNRS, 7 rue René-Descartes, 67000 Strasbourg, France
Email: coornaert@math.unistra.fr

DOI: https://doi.org/10.1090/S0002-9939-2014-12227-1
Keywords: Cellular automaton, semigroup, pre-injectivity, Garden of Eden theorem, amenable semigroup, F{\o}lner net, entropy
Received by editor(s): February 21, 2013
Received by editor(s) in revised form: February 24, 2013, and April 8, 2013
Published electronically: September 16, 2014
Dedicated: Dedicated to Slava Grigorchuk on his 60th birthday
Communicated by: Nimish Shah
Article copyright: © Copyright 2014 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society