Hostname: page-component-78c5997874-xbtfd Total loading time: 0 Render date: 2024-11-03T08:55:45.815Z 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: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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