The Myhill property for cellular automata on amenable semigroups

Ceccherini-Silberstein, Tullio; Coornaert, Michel

doi:10.1090/S0002-9939-2014-12227-1

The Myhill property for cellular automata on amenable semigroups
HTML articles powered by AMS MathViewer

by Tullio Ceccherini-Silberstein and Michel Coornaert PDF

Proc. Amer. Math. Soc. 143 (2015), 327-339 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, Ont.-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