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.
