Linear Cellular Automata and Finite Automata

Abstract Linear cellular automata have a canonical representation in terms of labeled de Bruijn graphs. We will show that these graphs, construed as semiautomata, provide a natural setting for the study of cellular automata. For example, we give a simple algorithm to determine reversibility and surjectivity of the global maps. We also comment on Wolfram's question about the growth rates of the minimal finite state machines associated with iterates of a cellular automaton. 1 Introduction Historically, there are two main sources of interest in cellular automata. One the one hand, in symbolic dynamics they appear as morphisms of shift spaces, see Hedlund's [10] for a very detailed discussion. On the other hand, von Neumann and Ulam used two-dimensional cellular automata to address the problem of self-reproduction, see [3]. More recent work by Wolfra