Two barriers for minimal time firing squads, with applications to four and five states
cs.FL, nlin.CG
Submitted: 2026-11-08
Updated: 2026-11-08
Comments: 34 pages, 18 figures, accepted (awaiting print) at the Journal of Cellular Automata
Code: https://github.com/giamkiakeng/proj1
License: http://creativecommons.org/licenses/by/4.0/
The gist: A minimal-time solution of the firing squad synchronization problem synchronizes every line of n cells at time 2n minus 2.
Abstract
A minimal-time solution of the firing squad synchronization problem synchronizes every line of n cells at time 2n minus 2. Six states suffice; whether five do has been open since 1987. Every line agrees with the half line until its right ends echo returns. For minimal time solutions with any number of states, we prove that cells at distance j behind the half lines front become time-periodic only after time (1.5 minus epsilon)j, for every epsilon greater than 0 and infinitely many j, and that the half line is never periodic in time and space on a wedge at its left border, hence not eventually regular in our sense. With certified satisfiability checks, we exclude four states using the lines of lengths 2 to 5 and parts of the next five, and show that every five state minimal time solution uses at least 15 non quiescent neighbourhoods on its half lines first 78 anti-diagonals. We give five state rules synchronizing exactly the lengths 2 to 14.
Sources
Related papers
- Quantitative Verification of Infinite-State Networks
- A Unary-to-Nonunary Transition in the Accepting-State Spectrum of Right Quotient for Permutation Automata
- Positive-Data Learning of Fixed-Observation Linear MCFGs from Working Binary Presentations
- On the Separability Problem of VASS Reachability Languages
- Exact Accepting-State Spectrum for Reversal of Permutation Automata
- On Word Representations and Embeddings in Complex Matrices