A linear speed-up theorem for cellular automata
From MaRDI portal
Publication:1193411
DOI10.1016/0304-3975(92)90150-EzbMath0779.68063MaRDI QIDQ1193411
Publication date: 27 September 1992
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items
Two-dimensional cellular automata and their neighborhoods ⋮ Synchronization of 1-way connected processors ⋮ A single-copy minimal-time simulation of a torus of automata by a ring of automata ⋮ Constant Acceleration Theorem for Extended von Neumann Neighbourhoods ⋮ Linear speed-up for cellular automata synchronizers and applications ⋮ Alternation on cellular automata ⋮ Two-dimensional cellular automata and deterministic on-line tessalation automata ⋮ A simulation of cellular automata on hexagons by cellular automata on rings ⋮ Computations on one-dimensional cellular automata ⋮ Inducing an order on cellular automata by a grouping operation ⋮ On the complexity of deadlock detection in families of planar nets ⋮ Two-dimensional cellular automata recognizer ⋮ Different time solutions for the firing squad synchronization problem on basic grid networks ⋮ A universal cellular automaton in quasi-linear time and its S-m-n form ⋮ Parallel recognition of rational languages in plane cellular automata
Cites Work
- Unnamed Item
- Unnamed Item
- On real-time cellular automata and trellis automata
- A six-state minimal time solution to the Firing squad synchronization problem
- Real-time language recognition by one-dimensional cellular automata
- An 8-state minimal time solution to the firing squad synchronization problem
- An optimum solution to the firing squad synchronization problem
- Sequential Machine Characterizations of Trellis and Cellular Automata and Applications
- Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State Machines
- Generation of Primes by a One-Dimensional Real-Time Iterative Array
