Predicting nonlinear cellular automata quickly by decomposing them into linear ones

DOI10.1016/S0167-2789(97)80003-6MaRDI QIDQ1376426zbMATH OpenFDO

Authors Cristopher Moore

Publication date 17 December 1997

Published in Physica D (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/patt-sol/9701008

zbMATH Keywords

parallel computing group theory efficient algorithm cellular automata decomposition

Mathematics Subject Classification ID

Dynamical aspects of cellular automata (37B15) Cellular automata (computational aspects) (68Q80)

Abstract: 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.

Recommendations

Cites work

Cited in

(15)

This page was built for publication: Predicting nonlinear cellular automata quickly by decomposing them into linear ones

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1376426)