![Complex Systems Complex Systems](https://www.complex-systems.com/wp-content/themes/complexsystems/img/ui_logo_small.png)
De Bruijn Graphs and Linear Cellular Automata
Klaus Sutner
Stevens Institute of Technology, Hoboken, NJ 07030 USA
Abstract
De Bruijn graphs provide a convenient way to describe configurations of linear cellular automata (CAs). Using these graphs, we give a simple quadratic time algorithm to determine whether a linear CA is reversible. Similarly, one can decide in quadratic time whether the global map of the automaton is surjective. We also show that every recursive configuration that has a predecessor on a linear CA already has a recursive predecessor. By contradistinction, it is in general impossible to compute such a predecessor effectively.