Fast Simulation of Cellular Automata by Self-Composition
<|reference_start|>Fast Simulation of Cellular Automata by Self-Composition: It is shown that computing the configuration of any one-dimensional cellular automaton at generation $n$ can be accelerated by constructing and running a composite one with a radius proportional to $\log n$. The new automaton is the original automaton whose local rule function is composed with itself. The asymptotic time complexity to compute the configuration of generation $n$ is reduced from $O(n^2)$ operations to $O(n^2 / \log n)$ on a given machine with $O(n^2)$ memory usage. Experimental results are given in the case of Rule 30.<|reference_end|>
@article{natal2024fast,
    title={Fast Simulation of Cellular Automata by Self-Composition},
    author={Joseph Natal, Oleksiy Al-saadi},
    journal={arXiv preprint arXiv:2409.07065},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.07065},
    primaryClass={cs.CC}
}