no. 16 · Tuesday 17 November 2026
Avoid-or-Compress Words for Reachable Images Missing Four or Five States
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