 

Laurent Bartholdi
Cellular automata, duality and sofic groups view print


Published: 
October 13, 2017 
Keywords: 
Linear cellular automata, preinjective and postsurjective endomorphisms, Garden of Eden theorem 
Subject: 
68Q80 (primary: Cellular automata), 43A07 (Amenable groups) 


Abstract
We produce for arbitrary nonamenable group G and field K a
nonpreinjective, surjective linear cellular automaton. This
answers positively Open Problem (OP14) in CeccheriniSilberstein
and Coornaert's monograph "Cellular Automata and Groups''.
We also reprove in a direct manner, for linear cellular automata,
the result by Capobianco, Kari and Taati that cellular automata over
sofic groups are injective if and only if they are postsurjective.
These results come from considerations related to matrices over
group rings: we prove that a matrix's kernel and the image of its
adjoint are mutual orthogonals of each other. This gives rise to a
notion of "dual cellular automaton'', which is preinjective if and
only if the original cellular automaton is surjective, and is
injective if and only if the original cellular automaton is
postsurjective.


Acknowledgements
This work is supported by the "@raction'' grant ANR14ACHN001801


Author information
Département de Mathématiques et Applications, École Normale Supérieure, Paris and Mathematisches Institut, GeorgAugust Universität zu Göttingen
laurent.bartholdi@gmail.com

