Non-Abelian Cellular Automata
Cristopher Moore · 1995
We show that a wide variety of non-linear cellular automata can be written as a semidirect product of linear ones, and that these CAs can be predicted in parallel time O(log t). This class includes any CA whose rule, when written as an algebra, is a solvable group.