Locally eventually onto cellular automata

@misc{haugland2026locally,
  title = {{Locally eventually onto cellular automata}},
  author = {Jan Kristian Haugland and Nadia S. Larsen and Tron Omland and Henrikke G. Rustad},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.33131},
  eprint = {2610.33131},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.33131},
  note = {CC BY 4.0},
}

TY  - UNPB
TI  - Locally eventually onto cellular automata
AU  - Jan Kristian Haugland
AU  - Nadia S. Larsen
AU  - Tron Omland
AU  - Henrikke G. Rustad
PY  - 2026
DA  - 2026/10/23
PB  - arXiv
DO  - 10.48550/arxiv.2610.33131
UR  - https://arxiv.org/abs/2610.33131
AB  - We give a new checkable criterion to ensure that a one-dimensional cellular automaton on a finite alphabet is locally eventually onto. In this setting, openness is equivalent to being n-to-1 for some n and therefore implies surjectivity. Bipermutive cellular automata are known to be locally eventually onto, while open cellular automata that are neither bipermutive nor bijective appear to have received less attention. Building on Sutner's work with de Bruijn graphs, we describe a method for deciding openness and at the same time determining n. We then introduce the notion of block-regularity of local rules as a generalization of bipermutivity and prove that it implies openness. We further identify two conditions that, together with block-regularity, ensure that every nonempty cylinder set is mapped onto the whole configuration space after a finite number of iterations, and hence that the cellular automaton is locally eventually onto. The appendix provides the algorithms that check these finite criteria and then presents examples of locally eventually onto, non-bipermutive cellular automata for small diameters.
ER  -