Černý–Pin rank conjecture for complete automata

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

(nr)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.

Sources & referencesView supporting material

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.