Paperlane

no. 16 · Tuesday 17 November 2026

Avoid-or-Compress Words for Reachable Images Missing Four or Five States

Qichao Wang and Daoyu Dong

math.CO · v2 · 37 pp

Abstract

Given a set of states $S$ and a nonempty proper subset $A\subset S$, an avoid-or-compress word either omits a state of $A$ from the image of $S$ or reduces the size of that image. We determine the largest possible length of a shortest such word when $S$ is a reachable image missing four or five states. For strongly connected synchronizing automata, the answers are $\min(n-|A|,11)$ and $\min(n-|A|,14)$, respectively, and both are attained over a binary alphabet. The lower bounds follow from uniform constructions. For the upper bounds, short-pair graphs and the linear span of short images reduce the problem to finitely many configurations. A computer-assisted classification eliminates these configurations except for one complete bipartite graph, which is excluded by a combinatorial argument.

comments
37 pages, 2 figures, 1 table. Expanded proofs, revised exposition, and detailed computational verification
fields
Combinatorics
pdf ↗ page arXiv:2610.39833 ↗