De Bruijn Graph s and Linear Cellular Automata
Klaus Sutner · Complex Systems · 1991
De Bruij n graphs provide a convenient way to describe configura tions of linear cellular automata (CAs). Using t hese gra phs, we give a simple quadra t ic t ime algorithm to det ermine whet her a linear CA is reversible. Similarly, one can decide in quadrat ic time whet her t he global map of th e auto mato n is surjective. We also show tha t every recursive configuration that has a predecessor on a linear CA already has a recursive pr edecessor. By contradist inction, it is in genera l impossible to comput e such a predecessor effect ively.