pith. sign in

arxiv: 1612.06117 · v2 · pith:YYMQA3GNnew · submitted 2016-12-19 · 🧮 math.GR

Linear cellular automata, duality and sofic groups

classification 🧮 math.GR
keywords cellularautomataautomatongroupslinearonlygroupinjective
0
0 comments X
read the original abstract

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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.