Černý–Pin rank conjecture for complete automata
Let be an -state complete automaton, and let 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 whose length is at most
This is a generalization of the Černý conjecture to nonsynchronizing automata; the case 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
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.