We study successor-bispecial strings over an alphabet $\Sigma$ of size $\sigma$, a minimal-branching analogue of de Bruijn strings, and ask how few Burrows-Wheeler transform (BWT) runs are possible.
In a de Bruijn string of order $k$, every $(k-1)$-gram has all $\sigma$ right-extensions; here, every $(k-1)$-gram has exactly two right-extensions, determined by a successor rule, which also forces two left-extensions.
For order $3$, we construct an explicit family $B_\sigma^{(3)}$, for every $\sigma \ge 2$, whose cyclic BWT has $r_c = \sigma^2 + 2$ runs. A suitable terminated linearization has the same run count, $r = r_c = \sigma^2 + 2$, while the smallest sufficient set has size $\chi = 2\sigma^2 + 1$.
The ratio $\chi/r = 2 - 3/(\sigma^2 + 2)$ nearly saturates the known bound $\chi/r \le 2$, which we have previously shown to be asymptotically tight. Compared with our earlier general construction, this improves the gap from $O(1/\sigma)$ to $O(1/\sigma^2)$.
We also show that the order-$3$ pattern appears as a blockwise two-row projection of normalized linear-feedback shift register (LFSR) de Bruijn sequences over $\mathbb{F}_q$, when primitive trinomials $x^3 - x + c$ exist.
For higher orders, we prove a general lower bound $r_c \ge \sigma^{k-1} + 2$ for every $\sigma \ge 3$ in the exact-length regime and analyze the boundary-merged higher-order candidate using the last-to-first (LF) permutation: it fails for $k = 4$ and all $\sigma \ge 3$, while verified $k = 5$ instances for $\sigma \in \{3,4\}$ yield $\chi/r$ ratios exceeding $1.96$.
Blogger's Review: This paper provides an in-depth study of successor-bispecial strings, revealing the running characteristics of the Burrows-Wheeler transform, especially in the case of order 3. By constructing an explicit family of strings, it demonstrates potential applications while expanding theoretical boundaries and offering optimization insights that merit further exploration.