Large semigroups of cellular automata

Yair Hartman*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)1991-2010
Number of pages20
JournalErgodic Theory and Dynamical Systems
Volume32
Issue number6
DOIs
StatePublished - Dec 1 2012

ASJC Scopus subject areas

  • Mathematics(all)
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Large semigroups of cellular automata'. Together they form a unique fingerprint.

Cite this