For each integer n ≥ 4 there is a strongly connected binary synchronizing one-cluster automaton F_n with m = 2, ℓ = n−2 and reset threshold 3n−5=(m−1)(n−1)+mℓ.
Assumptions
The example is sharp for the parameter-dependent theorem. It does not establish (n−1)² as the threshold for all n in this family.
Explanation
Constructions · 1
A four-state member of the sharp family
Letter a
0 → 1; 1 → 0; 2 → 1; 3 → 2
Letter b
0 → 1; 1 → 2; 2 → 3; 3 → 1
Parameters
n = 4, m = 2, ℓ = 2; parameter bound 7 versus conjectural bound 9
This is the n = 4 member of Definition 10.1. Its finite trace explains synchronization; the all-n optimality theorem needs the separate lower-bound argument.