Predicting nonlinear cellular automata quickly by decomposing them into linear ones
From MaRDI portal
Publication:1376426
DOI10.1016/S0167-2789(97)80003-6zbMath0932.37004arXivpatt-sol/9701008MaRDI QIDQ1376426
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
Related Items
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
