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.
Matthew Cook; Turlough Neary. 22th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2016, Zurich, Switzerland. Lecture Notes in Computer Science, LNCS-9664, pp.77-89, 2016, Cellular Automata and Discrete Complex Systems. 〈10.1007/978-3-319-39300-1_7〉
https://hal.inria.fr/hal-01435035
Contributeur : Hal Ifip
<>
Soumis le : vendredi 13 janvier 2017 - 15:24:10
Dernière modification le : mercredi 29 août 2018 - 11:02:01
Document(s) archivé(s) le : vendredi 14 avril 2017 - 20:19:21
Silvio Capobianco, Jarkko Kari, Siamak Taati. An “almost dual” to Gottschalk’s Conjecture. Matthew Cook; Turlough Neary. 22th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2016, Zurich, Switzerland. Lecture Notes in Computer Science, LNCS-9664, pp.77-89, 2016, Cellular Automata and Discrete Complex Systems. 〈10.1007/978-3-319-39300-1_7〉. 〈hal-01435035〉
