%0 Conference Proceedings
%T An “almost dual” to Gottschalk’s Conjecture
%+ Institute of Cybernetics [Tallinn]
%+ University of Turku
%+ Universiteit Leiden = Leiden University 
%A Capobianco, Silvio
%A Kari, Jarkko
%A Taati, Siamak
%Z Part 2: Regular Papers
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 22th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA)
%C Zurich, Switzerland
%Y Matthew Cook
%Y Turlough Neary
%3 Cellular Automata and Discrete Complex Systems
%V LNCS-9664
%P 77-89
%8 2016-06-15
%D 2016
%R 10.1007/978-3-319-39300-1_7
%K Cellular automata
%K Reversibility
%K Sofic groups
%Z Computer Science [cs]Conference papers
%X 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.
%G English
%Z TC 1
%Z WG 1.5
%2 https://inria.hal.science/hal-01435035/document
%2 https://inria.hal.science/hal-01435035/file/395687_1_En_7_Chapter.pdf
%L hal-01435035
%U https://inria.hal.science/hal-01435035
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-LNCS-9664
%~ IFIP-WG1-5
%~ IFIP-AUTOMATA