What is the name of a DFA where all long enough words are synchronizing words?

Question

TLDR: What is the name of a DFA that satisfies the following property: "I can guarantee that after feeding the automaton $n$ random symbols it will end up at some state that does not depend on the initial state".

Or at least, how can I tell if it's true in less than exponential time?

---

Further explanation. To be clear, I'm talking about DFA automata with no defined initial or accepting states.

So, an automaton $\mathcal{A}$ has a synchronizing word $w$ iff starting from any state, running the automaton on $w$ will bring the automaton to a single final state $q_f$, no matter the initial state. In other words:

$$ sync(w) \leftrightarrow \exists q_f \quad \forall q_0 \quad q_0 \underset{w}{\rightsquigarrow} q_f $$

Then we can talk about its "set of sync words": the set of all words that are synchronizing:

$$ W = \{ w | sync(w) \} $$

Now, we can ask about the automaton: "Are all words of a certain length synchronizing words?":

$$ \mathcal{S}(n): \quad \forall w \in \Sigma^n \quad sync(w) \quad ? $$

(With $\Sigma$ the alphabet of the automaton)

Note that there is no requirement that all words converge to the same final state. Only that for a given word, all initial states end up on a unique final state.

Now of course, for a DFA if all words of length $n$ are synchronizing, then all words of length $n+1$ are synchronizing, so this is equivalent to asking "Are all large enough words synchronizing words?".

In plain words: "Can I guarantee that after feeding the automaton $n$ random symbols it will converge to a known, unique state?".

I can't seem to find any information about this topic, not even the name of such property. I'd like to know if there's an easy way to compute this property, or if it is equivalent to other properties. Maybe it is too "trivial", but I find it weird given that I see this as basically the automata version of self-synchronizing codes (ie. self-synchronizing automata, or "forgetful" automata which only depend on the last $n$ symbols of input).

There seems to be plenty of discussion on whether an automaton has a synchronizing word or not, but none on whether all words (longer than some bound) are synchronizing words.

Answer 1

I don't know whether it has a name, but you can test in polynomial time whether a DFA has this property or not, as it is a 2-safety property.

Specifically, a DFA fails to have this property iff there exists two initial states $q_0,q_1$ and a word $w \in \Sigma^n$ where word $w$ takes you to a different state depending on whether you start in $q_0$ or $q_1$.

You can check for the existence of $q_0,q_1,w$ by building a product automaton that simulates two parallel runs of the DFA on the same word but two different initial states. Specifically, each state of the product automaton has the form $\langle q,r,i \rangle$, where $q,r$ are two states of the DFA and $i \in \{0,1,\dots,n\}$, plus there is one more state, the initial state $a$. We add a transition $\langle q,r,i \rangle \to \langle q',r',i+1 \rangle$ if there exists transitions $q \stackrel{x}{\to} q'$ and $r \stackrel{x}{\to} r'$ in the original DFA. Also, we add a transition $a \to \langle q_0,q_1,0 \rangle$ for all pairs of states $q_0,q_1$ from the original DFA such that $q_0 \ne q_1$. Next, use depth-first search to find the set of states in the product automaton that are reachable from $a$. Finally, check whether any state of the form $\langle q,r,n \rangle$ is reachable, where $q \ne r$. If yes, then the DFA fails to have the desired property. If no, then the DFA does have the desired property.