Surjective cellular automata far from the Garden of Eden

Keywords

Mathematics, Surjective function, Cellular automaton, Garden of Eden, Automaton

References

• SOFIC GROUPS AND DYNAMICAL SYSTEMSBenjamin Weiss — 2000
• Algorithmic Randomness and ComplexityRodney G. Downey, Denis R. Hirschfeldt — 2010
• Introduction to the Modern Theory of Dynamical SystemsJ.A. Zukas — 1998
• Condition for Injectivity of Global Maps for Tessellation AutomataAkira Maruoka, Masayuki Kimura — 1976
• Gardens of Eden and amenability on cellular automataLaurent Bartholdi — 2010
• Garden of Eden Configurations for Cellular Automata on Cayley Graphs of GroupsAntonio Machı̀, Filippo Mignosi — 1993
• Entropy and isomorphism theorems for actions of amenable groupsDonald Ornstein, Benjamin Weiss — 1987
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of ObservationsHerman Chernoff — 1952
• The converse of Moore’s Garden-of-Eden theoremJohn Myhill — 1963
• Randomness on full shift spacesCristian S. Calude, Peter Hertling, Helmut Jürgensen — 2001
• Computable algebra, general theory and theory of computable fields.Michael O. Rabin — 1960
• On the definition of normal numbersIvan Niven, Hannah Zuckerman — 1951
• The Axiomatization of RandomnessMichiel van Lambalgen — 1990
• The Definition of Random SequencesPer Martin-Löf — 1966
• Induction and restriction of cellular automataTullio Ceccherini‐Silberstein, Michel Coornaert — 2009
• Combinatorial Group TheoryCharles F. Miller — 2002
• Amenable groups and cellular automataTullio Ceccherini‐Silberstein, Antonio Machı̀, Fabio Scarabotti — 1999
• Introduction to the modern theory of dynamical systemsKatok, Anatole, Hasselblatt, Boris — 1996
• Cellular Automata and GroupsTullio Ceccherini‐Silberstein, Michel Coornaert — 2010
• Combinatorial Group Theory.P. M. Cohn, Wilhelm Magnus, A. Karrass — 1967

Cited by

• Post-surjectivity and balancedness of cellular automata over groupsSilvio Capobianco, Jarkko Kari, Siamak Taati — 2015
• Freezing, Bounded-Change and Convergent Cellular AutomataNicolas Ollinger, Guillaume Theyssier — 2019
• Besicovitch Pseudodistances with Respect to Non-Følner SequencesSilvio Capobianco, P. Guillon, CNRS, Aix-Marseille Université Institut de Mathématiques de Marseille — 2020
• Cellular Automata and Discrete Complex SystemsMatthew Cook, Turlough Neary, International Federation for Information Processing — 2016
• Cellular Automata and Discrete Complex Systems: 26th IFIP WG 1.5 International Workshop, AUTOMATA 2020, Stockholm, Sweden, August 10–12, 2020, ProceedingsHéctor Zenil — 2020
• Cold dynamics in cellular automata: a tutorialGuillaume Theyssier — 2022
• Not just the Garden of Eden: Additional takes on cellular automata surjectivitySilvio Capobianco — 2025
• A Characterization of Amenable Groups by Besicovitch PseudodistancesSilvio Capobianco, Pierre Guillon, C. Noûs — 2020
• An "almost dual" to Gottschalk's ConjectureSilvio Capobianco, J. Kari, Siamak Taati — 2016
• Balancedness and Martin-Lof randomness in cellular automataSilvio Capobianco — 2014

Related papers

• Permanent Polya problem for additive surjective mapsA. É. Guterman, Igor Spiridonov — 2020
• The Garden of Eden as an Israelite Sacred PlaceSeung Il Kang — 2020
• Cellular automata modelling of dendritic crystal growth based on Moore and von Neumann neighbourhoodsYifan Zhao, S.A. Billings, Daniel Coca — 2009
• Nonlinear strong *-commutativity preserving maps on factor von Neumann algebrasFangjuan Zhang — 2012
• Garden of eden configurations for 2-D cellular automata with rule 2460 Nİrfan Şiap, Hasan Akın, Ferhat ŞAH — 2010
• A Garden of Eden theorem for Anosov diffeomorphisms on toriTullio Ceccherini‐Silberstein, Michel Coornaert — 2015
• The Garden of Eden theorem for cellular automata on group setsSimon Wacker — 2016