pipette
ESEspañol

Exact Avoid-or-Compress Extrema for Dense Reachable Images: Defects Four and Five

Qichao Wang, Daoyu Dong

Preprint

In the authors' words

Let be a reachable image of a strongly connected synchronizing automaton and . We determine the maximum shortest avoid-or-compress length over binary and arbitrary finite alphabets for and . The exact values are and , respectively. Uniform binary constructions attain both bounds. For the upper bounds, short-pair graphs and actual-image constraints reduce all parameters to finite necessary domains. Exhaustive checks exclude the domains, apart from a single relaxation eliminated by a multipartite overlap lemma. The largest calculation covers 3,206,988 domains.

Main resultThe abstract does not state a limitation.

Appeared: Friday, October 30. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 13 pages, 2 figures, 1 table. Computer-assisted upper bounds