arXiv:2610.07044 · v2

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

首次提交 2026-10-05 09:15

版本更新 2026-11-10 13:18

雷达观测 2026-11-11 13:08

摘要

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$.

作者备注：9 pages, 1 figure. Revised proofs and exposition, corrected boundary transitions, updated references, and added a coauthor