Černý's conjecture for D3-directing complete nondeterministic finite automata
Č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 , there exists a path labelled by that word that ends in one common state . Let be the number of states of the CNFA.
Černý's conjecture for D3-directing CNFAs. Every D3-directing CNFA with states admits a D3-directing word of length at most
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.