WorksComputer Science
Exact Avoid-or-Compress Extrema for Dense Reachable Images: Defects Four and Five
Abstract · v1
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.
Review conversation
Reviews are not available for this work yet.