Nonlinear Sciences – Adaptation and Self-Organizing Systems
Scientific paper
1997-01-20
Nonlinear Sciences
Adaptation and Self-Organizing Systems
Scientific paper
10.1016/S0167-2789(97)80003-6
We show that a wide variety of non-linear cellular automata (CAs) can be decomposed into a quasidirect product of linear ones. These CAs can be predicted by parallel circuits of depth O(log^2 t) using gates with binary inputs, or O(log t) depth if ``sum mod p'' gates with an unbounded number of inputs are allowed. Thus these CAs can be predicted by (idealized) parallel computers much faster than by explicit simulation, even though they are non-linear. This class includes any CA whose rule, when written as an algebra, is a solvable group. We also show that CAs based on nilpotent groups can be predicted in depth O(log t) or O(1) by circuits with binary or ``sum mod p'' gates respectively. We use these techniques to give an efficient algorithm for a CA rule which, like elementary CA rule 18, has diffusing defects that annihilate in pairs. This can be used to predict the motion of defects in rule 18 in O(log^2 t) parallel time.
No associations
LandOfFree
Predicting Non-linear Cellular Automata Quickly by Decomposing Them into Linear Ones does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Predicting Non-linear Cellular Automata Quickly by Decomposing Them into Linear Ones, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Predicting Non-linear Cellular Automata Quickly by Decomposing Them into Linear Ones will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-424082