Černý conjecture

A finite machine has a few possible states, and each input sends each state to a definite next state. Suppose an input x sends A to B, B to C and C to C. Give x twice and the machine ends in C, whichever of the three states it started in. A sequence with this property is a reset word. The Černý conjecture asks whether every machine that can be reset has a reset word no longer than the square of one less than its number of states. For three states, that limit is four inputs; this example needs only two.[1]

How long must a fixed sequence of inputs be to eliminate uncertainty about a finite machine’s initial state? In a complete deterministic automaton, each state and input letter determine exactly one next state. A reset word sends every starting state to one common state; only automata admitting such a word are synchronizing. If $Q$ is the state set, $n=|Q|$, and $\delta(q,w)$ is the state reached from $q$ after word $w$, write $|w|$ for its input length. The conjecture asks for some $w$ and $s\in Q$ with $$\delta(q,w)=s\text{ for every }q\in Q,\qquad |w|\le(n-1)^2.$$ For a three-state example, let a rotate A→B→C→A, while b fixes A and B and sends C→A. Track all possible current states. The word b,a,a,b changes {A,B,C} to {A,B}, then {B,C}, then {C,A}, then {A}. Four inputs reset this machine, and checking every shorter word shows none does. It is a relabeling of the three-state Černý family, illustrating the bound rather than proving it for other machines.[1]

The predicted bound is unproved in general.[1]

The reviewed one-cluster result is a preprint claim, not a general resolution.[1] [2]

If the initial state is hidden, you cannot choose a different first input for each possible start. A reset word gives one preplanned sequence that removes this uncertainty and puts the system in a known state. The length measures the cost of that control when observing the initial state is unavailable.[1]

An input can move the set of possible states without reducing its size; several such moves may be needed before two possibilities merge. The reset problem therefore studies how a sequence of deterministic transformations can collectively erase initial-state information. The Černý family shows that this coordination can require a sequence whose length grows like the square of the number of states. Finding a universal matching upper bound would characterize the worst-case cost of this form of control.[1]