Černý's conjecture for D3-directing complete nondeterministic finite automata

Let a complete nondeterministic finite automaton (CNFA) be an automaton in which every state and input symbol has at least one outgoing transition. A word is D3-directing if, starting from every state qq, there exists a path labelled by that word that ends in one common state qsq_s. Let nn be the number of states of the CNFA.

Černý's conjecture for D3-directing CNFAs. Every D3-directing CNFA with nn states admits a D3-directing word of length at most

(n1)2.(n-1)^2.

The paper states that this formulation is equivalent to Černý's conjecture for DFAs. The result would give the sharp quadratic bound for shortest D3-directing words; the conjecture remains unresolved.

Sources & referencesView supporting material

Primary source

Henk Don and Hans Zantema, “Synchronizing non-deterministic finite automata”, arXiv:1703.07995 (2017).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.