The algebraic entropy of one-dimensional finitary linear cellular automata

Abstract

The aim of this paper is to present one-dimensional finitary linear cellular automata $S$ on ${\mathbb{Z}}_m$ from an algebraic point of view. Among various other results, we: (i) show that the Pontryagin dual $\hat{S}$ of $S$ is a classical one-dimensional linear cellular automaton $T$ on ${\mathbb{Z}}_m$; (ii) give several equivalent conditions for $S$ to be invertible with inverse a finitary linear cellular automaton; (iii) compute the algebraic entropy of $S$, which coincides with the topological entropy of $T=\hat{S}$ by the so-called Bridge Theorem. In order to better understand and describe the entropy we introduce the degree $\mathrm{deg}(S)$ and $\mathrm{deg}(T)$ of $S$ and $T$.

21 pages