An “almost dual” to Gottschalk’s Conjecture - Cellular Automata and Discrete Complex Systems Access content directly
Conference Papers Year : 2016

An “almost dual” to Gottschalk’s Conjecture

Silvio Capobianco
  • Function : Author
  • PersonId : 884133
Jarkko Kari
Siamak Taati
  • Function : Author
  • PersonId : 978944


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.
Fichier principal
Vignette du fichier
395687_1_En_7_Chapter.pdf (310.95 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-01435035 , version 1 (13-01-2017)





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⟩
102 View
187 Download



Gmail Facebook X LinkedIn More