2016/12/19 by Laurent Bartholdi, Bartholdi, Laurent
Computer Science · Mathematics · #37B15 #43A07 #68B50 #Cellular Automata and Applications #Computability, Logic, AI Algorithms #FOS: Mathematics #Group Theory (math.GR) #Mathematical Dynamics and Fractals
paper · pdf · doi:10.48550/arxiv.1612.06117
openalex publication_date 2016/12/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We produce for arbitrary non-amenable group G and field K a non-pre-injective, 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 post-surjective. 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 pre-injective if and only if the original cellular automaton is surjective, and is injective if and only if the original cellular automaton is post-surjective.