Predicting nonlinear cellular automata quickly by decomposing them into linear ones

DOI10.1016/S0167-2789(97)80003-6zbMATH Open0932.37004arXivpatt-sol/9701008MaRDI QIDQ1376426FDOQ1376426

Cristopher Moore

Publication date: 17 December 1997

Published in: Physica D (Search for Journal in Brave)

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.

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

Recommendations

• Quasilinear cellular automata
• Group properties of nonlinear cellular automata
• On the prediction of local patterns in cellular automata
• Computations on nondeterministic cellular automata
• scientific article

zbMATH Keywords

parallel computinggroup theoryefficient algorithmcellular automata decomposition

Mathematics Subject Classification ID

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

Cites Work

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Title not available (Why is that?)
• Circuits and expressions with nonassociative gates
• Exact solvability and quasiperiodicity of one-dimensional cellular automata
• Title not available (Why is that?)
• Statistical mechanics of cellular automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• On pseudovarieties
• Parity, circuits, and the polynomial-time hierarchy
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Computation theoretic aspects of cellular automata
• Algebraic properties of cellular automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Attractor vicinity decay for a cellular automaton
• Title not available (Why is that?)
• Title not available (Why is that?)
• The computational complexity of generating random fractals
• Title not available (Why is that?)

Cited In (13)

• Replication in one-dimensional cellular automata
• Pre-expansivity in cellular automata
• Evaluation of circuits over nilpotent and polycyclic groups
• Unraveling simplicity in elementary cellular automata
• Efficient exhaustive listings of reversible one dimensional cellular automata
• Mutually orthogonal Latin squares based on cellular automata
• Circuits and expressions with nonassociative gates
• Algebraic properties of some quadratic dynamical systems
• The Complexity of Small Universal Turing Machines: A Survey
• Theory of Composing Non-linear Machines with Predictable Cyclic Structures
• Group properties of nonlinear cellular automata
• The complexity of small universal Turing machines: A survey
• Graph-theoretical characterization of invertible cellular automata

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)