Gardens of Eden and amenability on cellular automata

DOI10.4171/JEMS/196MaRDI QIDQ845292zbMATH OpenFDO

Authors Laurent Bartholdi

Publication date 28 January 2010

Published in Journal of the European Mathematical Society (JEMS) (Search for Journal in Brave)

Full work available at URL https://doi.org/10.4171/JEMS/196

zbMATH Keywords

amenable groupsendomorphismsGarden-of-Eden theoremmultidimensional cellular automata

Mathematics Subject Classification ID

Dynamical aspects of cellular automata (37B15) Means on groups, semigroups, etc.; amenable groups (43A07) Cellular automata (computational aspects) (68Q80)

Review text

Two new characterizations of amenable groups were yielded by proof a converse to the Garden-of-Eden theorem by Ceccherini-Silberstein, Machi and Scarabotti and to a theorem of \textit{T.~Meywrovitch} [``Finite entropy for multidimensional cellular automata, Ergodic Theory Dynam. Systems 28, 1243--1260 (2008; Zbl 1152.37009)]. In particular, the following is proved to be equivalent: the group \(G\) is amenable, all cellular automata living on \(G\) that admit mutually erasable patterns also admit gardens of Eden; all cellular automata living on \(G\) that do not preserve Bernoulli measure admit gardens of Eden.

Recommendations

• Amenable groups and cellular automata
• A garden of Eden theorem for linear subshifts
• Amenability of groups is characterized by Myhill's theorem
• The Garden of Eden theorem for cellular automata on group sets
• The Garden of Eden theorem: old and new

Cites work

• A conjecture concerning a limit of non-Cayley graphs
• Amenable groups and cellular automata
• Endomorphisms and automorphisms of the shift dynamical system
• Endomorphisms of irreducible subshifts of finite type
• Endomorphisms of symbolic algebraic varieties
• Finite entropy for multidimensional cellular automata
• Garden of Eden Configurations for Cellular Automata on Cayley Graphs of Groups
• scientific article; zbMATH DE number 4156708 (Why is no real title available?)
• scientific article; zbMATH DE number 4076625 (Why is no real title available?)
• scientific article; zbMATH DE number 3205673 (Why is no real title available?)
• scientific article; zbMATH DE number 3363435 (Why is no real title available?)
• Shorter Note: The Converse of Moore's Garden-of-Eden Theorem
• The amenability and non-amenability of skew fields
• The Garden of Eden theorem for linear cellular automata
• Transversal theory. An account of some aspects of combinatorial mathematics

Cited in

(25)

• Amenable groups and cellular automata
• On dual surjunctivity and applications
• The Moore-Myhill pseudo tiling for the Heisenberg tessellation automata
• Pre-expansivity in cellular automata
• Group-graded rings satisfying the strong rank condition
• Amenability of groups is characterized by Myhill's theorem
• scientific article; zbMATH DE number 2128182 (Why is no real title available?)
• An ``almost dual to Gottschalk's conjecture
• Expansive actions of countable amenable groups, homoclinic pairs, and the Myhill property
• The Garden of Eden theorem for linear cellular automata
• Ranks of finite semigroups of one-dimensional cellular automata
• Linear cellular automata: Garden of Eden Theorem, L-surjunctivity and group rings
• Groups, graphs, languages, automata, games and second-order monadic logic
• The Garden of Eden theorem for cellular automata on group sets
• Amenability of groups and G-sets
• Surjunctivity and reversibility of cellular automata over concrete categories
• Garden of Eden and specification
• Reversibility vs Local Creation/Destruction
• Garden of Eden Configurations for Cellular Automata on Cayley Graphs of Groups
• The Myhill property for cellular automata on amenable semigroups
• Surjective cellular automata far from the Garden of Eden
• Garden of Eden and weakly periodic points for certain expansive actions of groups
• Cold dynamics in cellular automata: a tutorial
• The Garden of Eden theorem over generalized cellular automata
• Not just the Garden of Eden: additional takes on cellular automata surjectivity

This page was built for publication: Gardens of Eden and amenability on cellular automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q845292)