| HAL-Inria | Publications, software ... of Inria's scientists |
Conference papers
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.
Cited literature [13 references]
https://hal.inria.fr/hal-01435035
Contributor : Hal Ifip <>
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
Contributor : Hal Ifip <>
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
File
395687_1_En_7_Chapter.pdf
Files produced by the author(s)
Licence
Distributed under a Creative Commons Attribution 4.0 International License