Hardly reachable subsets and completely reachable automata with 1-deficient words.

This article focuses on subset reachability in synchronizing automata. First, we study the length of shortest words reaching subsets of states in synchronizing automata. We provide an automata family with subsets that cannot be reached by words shorter than 2n/n, thus disproving a recent conjecture of Don. We then analyze relaxed versions of this conjecture. Second, we analyze the 􀀀1-graph construction. The 􀀀1-graph is derived from 1-deficient words, and is a key tool for studying completely reachable automata. We introduce the concept of roots of 1-deficient words, which allows to state explicit concatenation rules for these words. Based on these results, we provide a polynomial-time algorithm for constructing the 􀀀1-graph. Then, we disprove a conjecture by Bondar and Volkov linking the strong connectivity of this graph and the concatenation of 1- deficient words of completely reachable automata. Finally, we prove an alternative version of this conjecture.