The Myhill property for cellular automata on amenable semigroups
HTML articles powered by AMS MathViewer
- by Tullio Ceccherini-Silberstein and Michel Coornaert
- Proc. Amer. Math. Soc. 143 (2015), 327-339
- DOI: https://doi.org/10.1090/S0002-9939-2014-12227-1
- Published electronically: September 16, 2014
- PDF | Request permission
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
- Laurent Bartholdi, Gardens of Eden and amenability on cellular automata, J. Eur. Math. Soc. (JEMS) 12 (2010), no. 1, 241–248. MR 2578610, DOI 10.4171/JEMS/196
- Tullio Ceccherini-Silberstein and Michel Coornaert, Cellular automata and groups, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2010. MR 2683112, DOI 10.1007/978-3-642-14034-1
- 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.
- 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
- Mahlon M. Day, Amenable semigroups, Illinois J. Math. 1 (1957), 509–544. MR 92128
- 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, DOI 10.1017/S0308210500010313
- 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
- Frederick P. Greenleaf, Invariant means on topological groups and their applications, Van Nostrand Mathematical Studies, No. 16, Van Nostrand Reinhold Co., New York-Toronto-London, 1969. MR 0251549
- M. Gromov, Endomorphisms of symbolic algebraic varieties, J. Eur. Math. Soc. (JEMS) 1 (1999), no. 2, 109–197. MR 1694588, DOI 10.1007/PL00011162
- 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, DOI 10.1137/0406004
- E. F. Moore, Machine models of self-reproduction, Proc. Symp. Appl. Math., 14, American Mathematical Society, Providence, RI, 1963, pp. 17–34.
- John Myhill, The converse of Moore’s Garden-of-Eden theorem, Proc. Amer. Math. Soc. 14 (1963), 685–686. MR 155764, DOI 10.1090/S0002-9939-1963-0155764-9
- I. Namioka, Følner’s conditions for amenable semi-groups, Math. Scand. 15 (1964), 18–28. MR 180832, DOI 10.7146/math.scand.a-10723
- Alan L. T. Paterson, Amenability, Mathematical Surveys and Monographs, vol. 29, American Mathematical Society, Providence, RI, 1988. MR 961261, DOI 10.1090/surv/029
- Benjamin Weiss, Sofic groups and dynamical systems, Sankhyā Ser. A 62 (2000), no. 3, 350–359. Ergodic theory and harmonic analysis (Mumbai, 1999). MR 1803462
- Carroll Wilde and Klaus Witz, Invariant means and the Stone-Čech compactification, Pacific J. Math. 21 (1967), 577–586. MR 212552
Bibliographic 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
- 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
- Communicated by: Nimish Shah
- © Copyright 2014
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - 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
- MathSciNet review: 3272758
Dedicated: Dedicated to Slava Grigorchuk on his 60th birthday