Paperlane

no. 13 · Wednesday 11 November 2026

An exact compress-with-another threshold in a binary automaton family

Qichao Wang and Daoyu Dong

math.CO · v2 · 9 pp

Abstract

For a state $q$ in a synchronizing automaton, let $μ(q)$ be the minimum length of a word merging $q$ with another initial state. Szykuła asked whether $μ(q)=O(n)$ for strongly connected synchronizing automata and described a binary family attributed to Dżyga, with $n=3p$ states and a conjectured threshold $4n/3$. We specify the boundary transitions omitted from the published piecewise definition and prove that the resulting automata $\mathcal A_p$ satisfy $μ(q_0)=4p=4n/3$ for all $p\geq3$. A shortest word merging $q_0$ with another state is $(ba)^p(ab)^p$. We also construct a reset word of length $3p^2+4p-1$. Consequently, any uniform linear upper bound for $μ(q)$ on binary strongly connected synchronizing automata with corank-one letters has leading constant at least $4/3$.

comments
9 pages, 1 figure. Revised proofs and exposition, corrected boundary transitions, updated references, and added a coauthor
fields
Combinatorics
pdf ↗ page arXiv:2610.07044 ↗