The surjectivity characterization conjecture for LR-separated cellular automata
The surjectivity characterization conjecture for LR-separated cellular automata
Let be a -separated cellular automaton over the finite field , where is prime, and let (respectively, ) be the leftmost (respectively, rightmost) position of .
Surjectivity characterization conjecture. is surjective if and only if either
or
The conjecture proposes a complete characterization of surjective -separated cellular automata over finite fields, extending the one-sided sufficient criterion established for finite rings. The converse fails over general finite rings, so the finite-field hypothesis is essential to the proposed statement; its resolution is not given here.
Sources & referencesView supporting material
Primary source
Firas Ben Ramdhane, Alberto Dennunzio, Luciano Margara and Giuliamaria Menara, “Structural Properties of Non-Linear Cellular Automata: Permutivity, Surjectivity and Reversibility”, arXiv:2504.15949 (2025).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.