Skip to content
DraconiticResearch
Search Sources API
197,785 studies31 sourcesUpdated 35 min ago
PreprintarXiv licencearXiv

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

  • Qichao Wang
  • Daoyu Dong
Open at sourcePDFDOICite

Abstract

Let S be a reachable image of a strongly connected synchronizing automaton and ∅≠ Asubsetneq S. We determine the maximum shortest avoid-or-compress length over binary and arbitrary finite alphabets for m=n−|S|=4 and m=5. The exact values are min(n−|A|,11) and min(n−|A|,14), 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.

Related

  1. The compress-with-another threshold of Szykuła's Figure 3 family
    Qichao Wang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Counting Reachable Positions in a Simplified Model of Connect Four
    Alistair Folster
    arXivPreprintCC BY 4.0Full textGeneral mathematicsarXiv
  3. Reachable sets under Kolmogorov dynamics in the probability simplex
    Alfonso Fernández de Bobadilla, Mykhailo Hontarenko, Guillem Müller-Rigat +1
    arXivPreprintarXiv licenceFull textMathematical physicsarXiv
  4. Computing Invariant Reachable Sets through Sum-of-Squares Programming
    Mohamed Khalid M Jaffar
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv
  5. A Reachable-State Operator Formulation of Deferred Acceptance: Progress Invariants and Structural Diagnostics
    Yoshiteru Ishida
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{wang2026exact,
  title = {{Exact Avoid-or-Compress Extrema for Dense Reachable Images: Defects Four and Five}},
  author = {Qichao Wang and Daoyu Dong},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.39833},
  eprint = {2610.39833},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.39833},
}
RIS
TY  - UNPB
TI  - Exact Avoid-or-Compress Extrema for Dense Reachable Images: Defects Four and Five
AU  - Qichao Wang
AU  - Daoyu Dong
PY  - 2026
DA  - 2026/10/29
PB  - arXiv
DO  - 10.48550/arxiv.2610.39833
UR  - https://arxiv.org/abs/2610.39833
AB  - Let S be a reachable image of a strongly connected synchronizing automaton and ∅≠ Asubsetneq S. We determine the maximum shortest avoid-or-compress length over binary and arbitrary finite alphabets for m=n−|S|=4 and m=5. The exact values are min(n−|A|,11) and min(n−|A|,14), 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.
ER  -