Garden of Eden Configurations for Cellular Automata on Cayley Graphs of Groups

DOI10.1137/0406004zbMath0768.68103OpenAlexW2024206422MaRDI QIDQ5285936

Filippo Mignosi, Antonio Machì

Publication date: 29 June 1993

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0406004

zbMATH Keywords

tessellationautomataCayley graphsgrowth functionfree abelian groupGarden of Eden configurations

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Cellular automata (computational aspects) (68Q80) Combinatorial aspects of tessellation and tiling problems (05B45)

Related Items (32)

Cellular automata and strongly irreducible shifts of finite type. ⋮ Semi-strongly irreducible shifts ⋮ Gardens of Eden and amenability on cellular automata ⋮ A garden of Eden theorem for Anosov diffeomorphisms on tori ⋮ A single-copy minimal-time simulation of a torus of automata by a ring of automata ⋮ Propagation, Diffusion and Randomization in Cellular Automata ⋮ Cellular non-deterministic automata and partial differential equations ⋮ Homoclinically expansive actions and a garden of Eden theorem for harmonic models ⋮ A survey of cellular automata: types, dynamics, non-uniformity and applications ⋮ Amenability and Linear Cellular Automata Over Semisimple Modules of Finite Length ⋮ Groups, graphs, languages, automata, games and second-order monadic logic ⋮ Amenability of Groups and G-Sets ⋮ Simulations between cellular automata on Cayley graphs ⋮ Induced Subshifts and Cellular Automata ⋮ On problems related to growth, entropy, and spectrum in group theory ⋮ Surjunctivity and Reversibility of Cellular Automata over Concrete Categories ⋮ The Moore-Myhill pseudo tiling for the Heisenberg tessellation automata ⋮ Linear cellular automata on Cayley graphs ⋮ A simulation of cellular automata on hexagons by cellular automata on rings ⋮ Embeddings of dynamical systems into cellular automata ⋮ The firing squad synchronization problem on Cayley graphs ⋮ Induction and restriction of cellular automata ⋮ About the Garden of Eden Theorems for Cellular Automata in the Hyperbolic Plane ⋮ Pre-expansivity in cellular automata ⋮ PERIODIC CONFIGURATIONS OF SUBSHIFTS ON GROUPS ⋮ Garden of Eden and specification ⋮ Amenable groups and cellular automata ⋮ The Myhill property for cellular automata on amenable semigroups ⋮ On the induction operation for shift subspaces and cellular automata as presentations of dynamical systems ⋮ Amenability of groups is characterized by Myhill's theorem ⋮ CELLULAR AUTOMATA OVER SEMI-DIRECT PRODUCT GROUPS: REDUCTION AND INVERTIBILITY RESULTS ⋮ On dual surjunctivity and applications

This page was built for publication: Garden of Eden Configurations for Cellular Automata on Cayley Graphs of Groups