On the Garden of Eden theorem for non-uniform cellular automata

2023/04/03 by Phung, Xuan Kien
#37B10 #37B15 #37B50 #43A05 #43A07 #68Q80 #Cellular Automata and Lattice Gases (nlin.CG) #Discrete Mathematics (cs.DM) #Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Mathematical Physics (math-ph)

paper · doi:10.48550/arxiv.2304.00661

Abstract

We establish several extensions of the well-known Garden of Eden theorem for non-uniform cellular automata over the full shifts and over amenable group universes. In particular, our results describe quantitatively the relations between the partial pre-injectivity and the size of the image of a non-uniform cellular automata. A strengthened surjunctivity result is also obtained for multi-dimensional cellular automata over strongly irreducible subshifts of finite type.

Related

• On the surjunctivity and the Garden of Eden theorem for non-uniform cellular automata
• Kolmogorov Complexity and the Garden of Eden Theorem
• Non-Uniform Cellular Automata: classes, dynamics, and decidability
• Some pointwise and decidable properties of non-uniform cellular automata
• On the Garden of Eden theorem for B-free subshifts