Hostname: page-component-7b7567c8c-kwt9d Total loading time: 0 Render date: 2026-11-14T01:48:03.655Z Has data issue: false hasContentIssue false
  • English
  • Français

Large semigroups of cellular automata

Published online by Cambridge University Press:  20 October 2011

YAIR HARTMAN
YAIR HARTMAN*
Affiliation:
Faculty of Mathematics and Computer Science, Weizmann Institute of Science, POB 26, Rehovot, 76100, Israel (email: yair.hartman@weizmann.ac.il)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

In this article, we consider semigroups of transformations of cellular automata which act on a fixed shift space. In particular, we are interested in two properties of these semigroups which relate to ‘largeness’: first, a semigroup has the ID (infinite is dense) property if the only infinite invariant closed set (with respect to the semigroup action) is the entire space; the second property is maximal commutativity (MC). We shall consider two examples of semigroups: one is spanned by cellular automata transformations that represent multiplications by integers on the one-dimensional torus, and the other one consists of all the cellular automata transformations which are linear (when the symbols set is the ring ℤ/sℤ). It will be shown that these two properties of these semigroups depend on the number of symbols s. The multiplication semigroup is ID and MC if and only if s is not a power of a prime. The linear semigroup over the mentioned ring is always MC but is ID if and only if s is prime. When the symbol set is endowed with a finite field structure (when possible), the linear semigroup is both ID and MC. In addition, we associate with each semigroup which acts on a one-sided shift space a semigroup acting on a two-sided shift space, and vice versa, in a way that preserves the ID and the MC properties.

Information

Type
Research Article
Information
Ergodic Theory and Dynamical Systems , Volume 32 , Issue 6 , December 2012, pp. 1991 - 2010
Copyright
Copyright © Cambridge University Press 2011

References

[1]Berend, D.. Multi-invariant sets on tori. Trans. Amer. Math. Soc. 280(2) (1983), 509–532.CrossRefGoogle Scholar
[2]Berend, D.. Multi-invariant sets on compact abelian groups. Trans. Amer. Math. Soc. 286(2) (1984), 505–535.Google Scholar
[3]Blanchard, F., Host, B. and Maass, A.. Représentation par automate de fonctions continues de tore. J. Théor. Nombres Bordeaux 5(2) (1993), 303–321.CrossRefGoogle Scholar
[4]Blanchard, F. and Maass, A.. Dynamical properties of expansive one-sided cellular automata. Israel J. Math. 99(1) (1997), 149–174.CrossRefGoogle Scholar
[5]Boyle, M., Lind, D. and Rudolph, D.. The automorphism group of a shift of finite type. Trans. Amer. Math. Soc. 306(1) (1988), 71–114.CrossRefGoogle Scholar
[6]Ceccherini-Silberstein, T. and Coornaert, M.. The garden of eden theorem for linear cellular automata. Ergod. Th. & Dynam. Sys. 26(01) (2006), 53–68.CrossRefGoogle Scholar
[7]Ceccherini-Silberstein, T. G. and Coornaert, M.. Cellular Automata and Groups (Springer Monographs in Mathematics). Springer, Berlin, 2010.CrossRefGoogle Scholar
[8]Coven, E. M., Hedlund, G. A. and Rhodes, F.. The commuting block maps problem. Trans. Amer. Math. Soc. 249(1) (1979), 113–138.CrossRefGoogle Scholar
[9]Ferguson, J. D.. Some properties of mappings on sequence spaces. Dissertation, Yale University, 1962.Google Scholar
[10]Furstenberg, H.. Disjointness in ergodic theory, minimal sets, and a problem in Diophantine approximation. Theory Comput. Syst. 1(1) (1967), 1–49.Google Scholar
[11]Hedlund, G. A.. Endomorphisms and automorphisms of the shift dynamical system. Theory Comput. Syst. 3(4) (1969), 320–375.Google Scholar
[12]Hochman, M.. On the automorphism groups of multidimensional shifts of finite type. Ergod. Th. & Dynam. Sys. 30(03) (2010), 809–840.CrossRefGoogle Scholar
[13]Ito, M., Osato, N. and Nasu, M.. Linear cellular automata over zm. J. Comput. System Sci. 27(1) (1983), 125–140.Google Scholar
[14]Katok, A. and Spatzier, R. J.. Invariant measures for higher-rank hyperbolic abelian actions. Ergod. Th. & Dynam. Sys. 16(04) (1996), 751–778.CrossRefGoogle Scholar
[15]Lindenstrauss, E.. Invariant measures for multiparameter diagonalizable algebraic actions—a short survey. European Congress of Mathematics (Stockholm, 27 June–2 July 2004). ASM International, 2005, p. 247.Google Scholar
[16]Rudolph, D. J.. x2 and x3 invariant measures and entropy. Ergod. Th. & Dynam. Sys. 10 (1990), 395–406.CrossRefGoogle Scholar