Černý–Pin rank conjecture for complete automata

About 5 years old · traced to

Let \mathrsfsA\mathrsfs{A} be an nn-state complete automaton, and let rr be the minimal rank of any word, where the rank of a word is the cardinality of its image on the state set. Rank conjecture. There exists a word of rank rr whose length is at most

(n−r)2.(n-r)^2.

This is a generalization of the Černý conjecture to nonsynchronizing automata; the case r=1r=1 is the Černý conjecture. The stronger version originally stated by Pin was disproved, whereas this minimal-rank version is presented as an open conjecture.

References

Primary source

Mikhail V. Berlinkov, Robert Ferens, Andrew Ryzhikov and Marek Szykuła, “Synchronization of strongly connected partial DFAs and prefix codes”, arXiv:2101.05057 (2026).

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.