Path automata: compression thresholds, a floor(4n/3) construction for every n, and exact reset thresholds
Enkai Zhang · Zenodo (CERN European Organization for Nuclear Research) · 2026
We study a family of deterministic automata with two input letters. For every n >= 9 it contains a strongly connected synchronizing automaton with a state for which the minimum length of a word merging it with some other state is floor(4n/3). We determine this quantity in several parameter ranges. We also prove rt(B_(s,s)) = 3s^2+4s-1 for s >= 3; rt(B_(s,s+1)) = 3(s+1)^2 for odd s >= 3; and rt(B_(s,s+2)) = 3s^2+8s+8 for s >= 6 divisible by 3, with rt(B_(3,5)) = 58 separately. The lower bounds use families covering all successive inverse images, with integer labels controlling word length. The technical supplement contains the complete rules and their checks over the stated unbounded ranges. The complete two-parameter reset formula remains open. Preprint. Not externally peer reviewed. The main paper is accompanied by a required technical supplement and computational evidence archives.