The compress-with-another threshold of Szyku{\l}a's Figure 3 family
In the authors' words
We give a self-contained pair-automaton proof of the exact compress-with-another threshold of the corrected Figure 3 family from a recent survey of open problems in synchronizing automata. For every , the automaton has states and . The word attains this value. Two entrance potentials and an excluded region yield the lower bound, with the endpoint exception at treated explicitly. A separate reset construction proves for every parameter. Reproducible computations verify the transition and entrance identities; the all-parameter results follow from the explicit proofs.
Main resultThe abstract does not state a limitation.
Appeared: Wednesday, October 7. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 8 pages. Reproducible computational verification included in the source