An “almost dual” to Gottschalk’s Conjecture

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.
Type de document :
Communication dans un congrès
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〉
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01435035
Contributeur : Hal Ifip <>
Soumis le : vendredi 13 janvier 2017 - 15:24:10
Dernière modification le : vendredi 13 janvier 2017 - 15:29:40
Document(s) archivé(s) le : vendredi 14 avril 2017 - 20:19:21

Fichier

 Accès restreint
Fichier visible le : 2019-01-01

Connectez-vous pour demander l'accès au fichier

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

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〉

Partager

Métriques

Consultations de la notice

91