pipette
ENEnglish

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

Qichao Wang, Daoyu Dong

Preprint

En palabras de los autores

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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: viernes, 30 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 13 pages, 2 figures, 1 table. Computer-assisted upper bounds