Don's reachable-subset length conjecture for finite automata
Don's reachable-subset length conjecture for finite automata
Let be an -state automaton, where is its state set and is its transition function. For of size , suppose there is a word such that
Don's reachable-subset length conjecture. There is a word such that and whose length is at most
The conjecture would make the subset-reachability bound proved for aperiodically -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
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.