Moore, Cristopher - Santa Fe Institute - 1995
We show that a wide variety of nonlinear cellular automata can be written as a semidirect product of linear ones, and that these CAs can be predicted in parallel time [cal O](log[super 2] t). This class includes any CA whose rule, when written as an algebra, is a solvable group. <p> We also show,...</p>