Don's reachable-subset length conjecture for finite automata

Let A=(Q,Σ,δ)\mathscr{A}=(Q,\Sigma,\delta) be an nn-state automaton, where QQ is its state set and δ\delta is its transition function. For SQS\subseteq Q of size kk, suppose there is a word ww such that

δ(Q,w)=S.\delta(Q,w)=S.

Don's reachable-subset length conjecture. There is a word vv such that δ(Q,v)=S\delta(Q,v)=S and whose length is at most

vn(nk).|v|\leq n(n-k).

The conjecture would make the subset-reachability bound proved for aperiodically 11-contracting automata universal. The source presents it as a conjecture and gives no resolution, so it remains open.

Sources & referencesView supporting material

Primary source

Henk Don, “The Cerny conjecture and 1-contracting automata”, arXiv:1507.06070 (2015).

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.