Černý–Pin rank conjecture for complete automata
Č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.
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
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.