Invertible Linear Cellular Automata overZm:: Algorithmic and Dynamical Aspects

摘要

We give an explicit and efficiently computable formula for the inverse ofD-dimensional linear cellular automata overZm(D⩾1, m⩾2). We use this formula to get an easy-to-check necessary and sufficient condition for an invertible one-dimensional linear CA to be expansive, and we prove that this condition is equivalent to topological transitivity.