Affordable Access

Non-Abelian Cellular Automata

  • Mathematics


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. 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).

There are no comments yet on this publication. Be the first to share your thoughts.