Abstract : We discuss cellular automata over arbitrary finitely generated groups. We call a cellular automaton post-surjective if for any pair of asymptotic configurations, every pre-image of one is asymptotic to a pre-image of the other. The well known dual concept is pre-injectivity: a cellular automaton is pre-injective if distinct asymptotic configurations have distinct images. We prove that pre-injective, post-surjective cellular automata are reversible. We then show that on sofic groups, where it is known that injective cellular automata are surjective, post-surjectivity implies pre-injectivity. As no non-sofic groups are currently known, we conjecture that this implication always holds. This mirrors Gottschalk’s conjecture that every injective cellular automaton is surjective.
https://hal.inria.fr/hal-01435035 Contributor : Hal IfipConnect in order to contact the contributor Submitted on : Friday, January 13, 2017 - 3:24:10 PM Last modification on : Wednesday, August 29, 2018 - 11:02:01 AM Long-term archiving on: : Friday, April 14, 2017 - 8:19:21 PM
Silvio Capobianco, Jarkko Kari, Siamak Taati. An “almost dual” to Gottschalk’s Conjecture. 22th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2016, Zurich, Switzerland. pp.77-89, ⟨10.1007/978-3-319-39300-1_7⟩. ⟨hal-01435035⟩