Predicting nonlinear cellular automata quickly by decomposing them into linear ones

DOI10.1016/S0167-2789(97)80003-6zbMath0932.37004arXivpatt-sol/9701008MaRDI QIDQ1376426

Moore, Cristopher

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 computinggroup theoryefficient algorithmcellular automata decomposition

Mathematics Subject Classification ID

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

Related Items (12)

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

Cites Work

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

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