Around Don's conjecture for binary completely reachable automata
<|reference_start|>Around Don's conjecture for binary completely reachable automata: A word $w$ is called a reaching word of a subset $S$ of states in a deterministic finite automaton (DFA) if $S$ is the image of $Q$ under the action of $w$. A DFA is called completely reachable if every non-empty subset of the state set has a reaching word. A conjecture states that in every $n$-state completely reachable DFA, for every $k$-element subset of states, there exists a reaching word of length at most $n(n-k)$. We present infinitely many completely reachable DFAs with two letters that violate this conjecture. A subfamily of completely reachable DFAs with two letters, is called standardized DFAs, introduced by Casas and Volkov (2023). We prove that every $k$-element subset of states in an $n$-state standardized DFA has a reaching word of length $\le n(n-k) + n - 1$. Finally, we confirm the conjecture for standardized DFAs with additional properties, thus generalizing a result of Casas and Volkov (2023).<|reference_end|>
@article{zhu2024around,
    title={Around Don's conjecture for binary completely reachable automata},
    author={Yinfeng Zhu},
    journal={arXiv preprint arXiv:2402.19089},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.19089},
    primaryClass={cs.FL}
}