Č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
- 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.