Non-Abelian Cellular Automata

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^2t)$. This class includes any CA whose rule, when written as an algebra, is a solvable group. We also show, with an induction on levels of commutators, that CAs based on nilpotent groups can be predicted in parallel time ${\cal O}(\log t)$.