| |
|
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 (OP-14) in Ceccherini-Silberstein
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 ANR-14-ACHN-0018-01
|
|
Author information
Département de Mathématiques et Applications, École Normale Supérieure, Paris and Mathematisches Institut, Georg-August Universität zu Göttingen
laurent.bartholdi@gmail.com
|
|