Introduction

Imagine a machine with a few internal states and a couple of buttons. You know exactly what each button does in each state — but you can't see which state the machine is in right now. There is no reset switch. Can you still press a fixed sequence of buttons that is guaranteed to leave the machine in one known state, whatever state it started in?

In the language of finite automata, the machine is a deterministic finite automaton (DFA) A=(Q,Σ,δ)\mathcal{A} = (Q, \Sigma, \delta): a finite set of nn states QQ, an alphabet Σ\Sigma of letters (the buttons), and a transition function δ:Q×Σ→Q\delta: Q \times \Sigma \to Q. A word ww is a reset word (or synchronizing word) if

δ(p,w)=δ(q,w)for all p,q∈Q,\delta(p, w) = \delta(q, w) \quad \text{for all } p, q \in Q,

that is, after reading ww every possible starting state ends up in the same place. An automaton that has a reset word is called synchronizing, and the length of its shortest reset word is its reset threshold.

The trick is to stop tracking one state and start tracking the set of states the machine could be in. At the start that set is all of QQ. Each letter maps the set to its image, and the image can only stay the same size or shrink. A reset word is exactly a word that squeezes the set down to a single state.

In 1964 the Slovak mathematician Ján Černý described a family of automata Cn\mathcal{C}_n with nn states and two letters whose shortest reset word has length exactly (n−1)2(n-1)^2. He then asked whether that is the worst case. The Černý conjecture says:

Every synchronizing automaton with nn states has a reset word of length at most (n−1)2(n-1)^2.

Sixty years later, nobody knows whether it is true.

Reset the Machine Yourself

Below is Černý's automaton Cn\mathcal{C}_n drawn on a circle. Letter b (blue) rotates every state one step around the circle. Letter a (red) sends state 0 to state 1 and leaves every other state where it is. All states start lit, because you don't know where the machine is. Press a and b and try to light up just one.

<p class="hint">The machine is in <b>one</b> of these states, but you are blindfolded: you don't know which. So every state is lit. Press <b>a</b> or <b>b</b> — each letter moves every possible state along its arrow — and watch the set of possibilities shrink. Can you squeeze it down to a single state?</p>
<div class="controls">
  <label>States n
    <select id="nsel">
      <option value="4">4</option>
      <option value="5" selected>5</option>
      <option value="6">6</option>
      <option value="7">7</option>
      <option value="8">8</option>
    </select>
  </label>
  <label>Automaton
    <select id="modesel">
      <option value="cerny" selected>Černý automaton C_n</option>
      <option value="random">Random automaton</option>
    </select>
  </label>
  <button id="newrand" type="button" class="ghost">New random</button>
</div>
<svg id="dia" viewBox="0 0 300 300" role="img" aria-label="Diagram of the automaton: states on a circle, red arrows for letter a, blue arrows for letter b"></svg>
<div class="legend"><span class="la">━ letter a</span> <span class="lb">━ letter b</span></div>
<div class="btns">
  <button id="ka" type="button" class="letter la-btn">a</button>
  <button id="kb" type="button" class="letter lb-btn">b</button>
  <button id="undo" type="button" class="ghost">Undo</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div class="status" id="status"></div>
<div class="word"><span class="wl">Your word:</span> <span id="word"></span></div>
<div class="btns">
  <button id="bfs" type="button">Find shortest reset word (BFS)</button>
  <button id="play" type="button" class="ghost" disabled>Play it</button>
</div>
<div class="result" id="result"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.controls { display: flex; gap: .6rem; flex-wrap: wrap; align-items: center; font-size: .85rem; margin-bottom: .3rem; }
.controls select { font: inherit; margin-left: .3rem; padding: .2rem .3rem; border-radius: 6px; border: 1px solid #adb1b8; background: #fff; color: #222; }
#dia { width: 100%; max-width: 320px; display: block; margin: 0 auto; }
.node { stroke: #8a929c; stroke-width: 2; fill: #fff; transition: fill .25s, stroke .25s; }
.node.on { fill: #1d3557; stroke: #1d3557; }
.node.sync { fill: #0a7d33; stroke: #0a7d33; }
.nlabel { font: 700 13px ui-monospace, monospace; text-anchor: middle; dominant-baseline: central; fill: #1d3557; pointer-events: none; }
.nlabel.on { fill: #fff; }
.ea { stroke: #e63946; }
.eb { stroke: #1d6fb8; }
.edge { fill: none; stroke-width: 1.6; opacity: .75; }
.legend { text-align: center; font-size: .8rem; margin: .1rem 0 .4rem; }
.la { color: #e63946; font-weight: 600; }
.lb { color: #1d6fb8; font-weight: 600; margin-left: .8rem; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin: .35rem 0; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
button.letter { font: 700 18px ui-monospace, monospace; min-width: 52px; }
button.la-btn { background: #e63946; border-color: #c92f3c; }
button.lb-btn { background: #1d6fb8; border-color: #175d9b; }
.status { font-size: .95rem; font-weight: 600; margin: .4rem 0 .2rem; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.word { font: 14px ui-monospace, monospace; word-break: break-all; min-height: 1.3em; color: #333; }
.word .wl { font-family: system-ui, sans-serif; color: #666; }
.result { font-size: .9rem; line-height: 1.45; margin-top: .3rem; min-height: 1.3em; }
.result code { font: 13px ui-monospace, monospace; background: #eef2f6; padding: 0 .25rem; border-radius: 4px; word-break: break-all; }
.result .tight { color: #c92f3c; font-weight: 600; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Černý automaton C_n: letter b rotates every state one step around the circle; letter a sends state 0 to state 1 and leaves all the others where they are.
function cernyDfa(n) {
  const a = [], b = [];
  for (let i = 0; i < n; i++) { a.push(i === 0 ? 1 : i); b.push((i + 1) % n); }
  return { a, b };
}
// Random automaton: each letter sends each state to a uniformly random state (it may or may not be synchronizing).
function randomDfa(n) {
  const r = () => Math.floor(Math.random() * n);
  const a = [], b = [];
  for (let i = 0; i < n; i++) { a.push(r()); b.push(r()); }
  return { a, b };
}
// Image of a set of states (bitmask) under one letter.
function stepSet(d, n, mask, letter) {
  let out = 0;
  for (let i = 0; i < n; i++) if ((mask >> i) & 1) out |= 1 << d[letter][i];
  return out;
}
// Breadth-first search over subsets, starting from the full set; the first singleton reached gives a shortest reset word.
function shortestReset(d, n) {
  const full = (1 << n) - 1;
  const parent = new Map([[full, null]]);
  const queue = [full];
  for (let h = 0; h < queue.length; h++) {
    const S = queue[h];
    if ((S & (S - 1)) === 0) {
      let w = '', cur = S;
      while (parent.get(cur)) { const [p, x] = parent.get(cur); w = x + w; cur = p; }
      return { word: w, explored: parent.size };
    }
    for (const x of ['a', 'b']) {
      const T = stepSet(d, n, S, x);
      if (!parent.has(T)) { parent.set(T, [S, x]); queue.push(T); }
    }
  }
  return { word: null, explored: parent.size };
}
// Interface state and drawing helpers.
let n = 5, mode = 'cerny', dfa = cernyDfa(5), S = 31, word = '', hist = [], timer = null, best = null;
const $ = (id) => document.getElementById(id);
const pop = (m) => { let c = 0; while (m) { c += m & 1; m >>= 1; } return c; };
const NS = 'http://www.w3.org/2000/svg';
const R = 110, C = 150, NR = 16;
const pos = (i) => { const t = -Math.PI / 2 + 2 * Math.PI * i / n; return [C + R * Math.cos(t), C + R * Math.sin(t)]; };
function el(tag, attrs) { const e = document.createElementNS(NS, tag); for (const k in attrs) e.setAttribute(k, attrs[k]); return e; }

// Draw the states on a circle with curved arrows: a bends one way, b the other.
function draw() {
  const svg = $('dia'); svg.innerHTML = '';
  const defs = el('defs', {});
  for (const [id, col] of [['ma', '#e63946'], ['mb', '#1d6fb8']]) {
    const m = el('marker', { id, viewBox: '0 0 10 10', refX: 9, refY: 5, markerWidth: 6, markerHeight: 6, orient: 'auto-start-reverse' });
    m.appendChild(el('path', { d: 'M0,0 L10,5 L0,10 z', fill: col }));
    defs.appendChild(m);
  }
  svg.appendChild(defs);
  for (const x of ['a', 'b']) {
    for (let i = 0; i < n; i++) {
      const j = dfa[x][i];
      const [x1, y1] = pos(i);
      if (i === j) {
        // Self-loop: a small circle just outside the node.
        const t = -Math.PI / 2 + 2 * Math.PI * i / n + (x === 'a' ? -0.7 : 0.7);
        const cx = x1 + (NR + 6) * Math.cos(t), cy = y1 + (NR + 6) * Math.sin(t);
        svg.appendChild(el('circle', { cx, cy, r: 9, class: 'edge e' + x }));
        continue;
      }
      const [x2, y2] = pos(j);
      const mx = (x1 + x2) / 2, my = (y1 + y2) / 2;
      const dx = x2 - x1, dy = y2 - y1, L = Math.hypot(dx, dy);
      const off = (x === 'a' ? 1 : -1) * Math.min(28, L * 0.22);
      const qx = mx - dy / L * off, qy = my + dx / L * off;
      const sh = (px, py, tx, ty) => { const ux = tx - px, uy = ty - py, l = Math.hypot(ux, uy); return [px + ux / l * NR, py + uy / l * NR]; };
      const [sx, sy] = sh(x1, y1, qx, qy), [ex, ey] = sh(x2, y2, qx, qy);
      svg.appendChild(el('path', { d: `M${sx},${sy} Q${qx},${qy} ${ex},${ey}`, class: 'edge e' + x, 'marker-end': `url(#m${x})` }));
    }
  }
  for (let i = 0; i < n; i++) {
    const [px, py] = pos(i);
    svg.appendChild(el('circle', { cx: px, cy: py, r: NR, class: 'node', id: 'n' + i }));
    const t = el('text', { x: px, y: py, class: 'nlabel', id: 't' + i }); t.textContent = i;
    svg.appendChild(t);
  }
  paint();
}
// Compact display: runs like bbbb become b with an exponent.
function compress(w) {
  return w.replace(/(a+|b+)/g, (r) => r.length > 1 ? `${r[0]}<sup>${r.length}</sup>` : r);
}
function paint() {
  const k = pop(S), single = k === 1;
  for (let i = 0; i < n; i++) {
    const on = (S >> i) & 1;
    $('n' + i).setAttribute('class', 'node' + (on ? (single ? ' sync' : ' on') : ''));
    $('t' + i).setAttribute('class', 'nlabel' + (on ? ' on' : ''));
  }
  const st = $('status');
  if (single) {
    st.textContent = i18nFmt("Synchronized! After %len% letters the machine is surely in state %q%, whatever state it started in.", { len: word.length, q: Math.log2(S) });
    st.className = 'status ok';
  } else {
    st.textContent = i18nFmt("Possible states: %k% of %n% · letters typed: %len%", { k, n, len: word.length });
    st.className = 'status';
  }
  $('word').innerHTML = word ? compress(word) : "(empty)";
}
function apply(x) {
  hist.push(S); S = stepSet(dfa, n, S, x); word += x; paint();
}
function stopPlay() { if (timer) { clearInterval(timer); timer = null; } }
function restart() { stopPlay(); S = (1 << n) - 1; word = ''; hist = []; paint(); }
function rebuild() {
  // New automaton: restart with every state possible and forget the previous search.
  stopPlay();
  dfa = mode === 'cerny' ? cernyDfa(n) : randomDfa(n);
  best = null; $('play').disabled = true; $('result').innerHTML = '';
  S = (1 << n) - 1; word = ''; hist = [];
  draw();
}
function runBfs() {
  stopPlay();
  const res = shortestReset(dfa, n);
  const bound = (n - 1) * (n - 1);
  best = res.word;
  if (best === null) {
    $('result').textContent = i18nFmt("No reset word exists: this automaton is not synchronizing (%k% reachable subsets explored, none of them a single state). Try another random one.", { k: res.explored });
    $('play').disabled = true;
    return;
  }
  let html = i18nFmt("Shortest reset word: length %len% (Černý bound (n−1)² = %bound%; subsets explored: %k%).", { len: best.length, bound, k: res.explored });
  html += ` <code>${best ? compress(best) : '—'}</code>`;
  if (best.length === bound) html += ` <span class="tight">${"It hits the bound exactly — this is Černý's extreme family."}</span>`;
  else html += ' ' + i18nFmt("That is %gap% letters below the bound.", { gap: bound - best.length });
  $('result').innerHTML = html;
  $('play').disabled = false;
}
function play() {
  // Replay the shortest reset word letter by letter from the full set.
  if (best === null) return;
  restart();
  let i = 0;
  const delay = best.length > 30 ? 160 : 320;
  timer = setInterval(() => {
    if (i >= best.length) { stopPlay(); return; }
    apply(best[i++]);
  }, delay);
}
$('ka').addEventListener('click', () => { stopPlay(); apply('a'); });
$('kb').addEventListener('click', () => { stopPlay(); apply('b'); });
$('undo').addEventListener('click', () => { stopPlay(); if (hist.length) { S = hist.pop(); word = word.slice(0, -1); paint(); } });
$('reset').addEventListener('click', restart);
$('bfs').addEventListener('click', runBfs);
$('play').addEventListener('click', play);
$('nsel').addEventListener('change', (e) => { n = +e.target.value; rebuild(); });
$('modesel').addEventListener('change', (e) => { mode = e.target.value; rebuild(); });
$('newrand').addEventListener('click', () => { mode = 'random'; $('modesel').value = 'random'; rebuild(); });
// Keyboard shortcuts: the a and b keys apply letters.
document.addEventListener('keydown', (e) => {
  if (e.target && e.target.tagName === 'SELECT') return;
  if (e.key === 'a' || e.key === 'b') { stopPlay(); apply(e.key); }
});
rebuild();
Result
Console

Two things to notice. First, the letter a is the only one that ever merges two states, and it only does so when both 0 and 1 are still lit — so you have to rotate the set with b until the right pair lines up, again and again. That is why Cn\mathcal{C}_n is so slow: the BFS button confirms its shortest reset word is (abn−1)n−2a(ab^{n-1})^{n-2}a, of length exactly (n−1)2(n-1)^2. Second, switch to random automata: most of them synchronize, and they do so far below the bound. Nobody has ever found an automaton that beats (n−1)2(n-1)^2 — but nobody can prove that none exists.

What Is Actually Known

Computing a shortest reset word for one automaton is easy in principle: run breadth-first search over the subsets of QQ, starting from QQ itself — exactly what the demo's BFS button does:

shortest_reset_word(Q, Σ, δ):
    parent[Q] ← none;  queue ← [Q]
    while queue is not empty:
        S ← queue.pop_front()
        if |S| = 1: return the letters on the path from Q to S
        for each letter x in Σ:
            T ← { δ(q, x) : q ∈ S }        # image of the set
            if T not seen: parent[T] ← (S, x); queue.push(T)
    return "not synchronizing"

The catch is that there are 2n2^n subsets, so this takes exponential time. What we know about the length is this:

  • Lower bound — tight. Černý's automata Cn\mathcal{C}_n need exactly (n−1)2(n-1)^2 letters, so the conjecture, if true, is best possible.
  • Best general upper bound — cubic. In the early 1980s Peter Frankl (1982) and Jean-Éric Pin (1983) showed every synchronizing automaton has a reset word of length at most n3−n6\frac{n^3 - n}{6}. That bound stood for over thirty years. Marek Szykuła (STACS 2018) lowered the leading constant to about 0.1664 n30.1664\,n^3, and Yaroslav Shitov (2019) to about 0.1654 n30.1654\,n^3 — precisely (748+15625798768)n3+o(n3)\left(\tfrac{7}{48} + \tfrac{15625}{798768}\right)n^3 + o(n^3). As of 2026 that is still the best general bound: no one has proved any bound of the form O(n3−ε)O(n^{3-\varepsilon}), let alone (n−1)2(n-1)^2.
  • Proven for special classes. The conjecture holds for orientable (monotonic) automata (Eppstein, 1990) and for circular automata, where some letter cyclically permutes all states (Dubuc, 1998). Strong quadratic bounds are known for aperiodic automata — n(n−1)2\frac{n(n-1)}{2} (Trahtman, 2007) — and for Eulerian automata — n2−3n+3n^2 - 3n + 3 (Kari, 2003).
  • Checked by computer for small nn. Exhaustive searches have confirmed the conjecture for every two-letter automaton with up to 11 states, every four-letter automaton with up to 7 states, and every eight-letter one with up to 5 states (as collected in Volkov's survey of results, updated January 2026).
  • Algorithmic side. Deciding whether an automaton is synchronizing is easy: it is synchronizing if and only if every pair of states can be merged by some word, which can be checked in polynomial time on the graph of pairs, O(∣Σ∣ n2)O(|\Sigma|\,n^2). Eppstein's greedy algorithm (1990) even builds a reset word of length O(n3)O(n^3) in polynomial time. But finding a shortest one is hard: deciding whether a reset word of length ≤k\le k exists is NP-complete (Eppstein, 1990, by a reduction from SAT), and computing the exact reset threshold is even harder (DP-complete, Olschewski and Ullrich, 2010).

Why is it so stubborn? The extreme examples are rare and fragile: only a handful of infinite families come anywhere near (n−1)2(n-1)^2, while typical automata reset after only on the order of n\sqrt{n} letters in experiments. A proof must control the worst case among roughly n∣Σ∣nn^{|\Sigma| n} automata, and every general technique so far — essentially counting how fast subsets can be shrunk one state at a time — loses a factor of nn along the way. It is the same gap between "we checked every small case" and "we proved it for all nn" that keeps Collatz open.

Where It Matters

"Get a system into a known state without looking at it" turns out to be a very practical need:

  • Robotics and parts feeders. A part lying on a conveyor belt can be in any of a few orientations. A sequence of fixed obstacles or tray tilts that forces every orientation into the same one is a reset word — this "sensorless" orienting was the motivation for Natarajan's and Eppstein's work in the late 1980s.
  • Testing digital circuits. A sequential circuit is a finite-state machine. When a chip has no reliable reset line, a synchronizing input sequence drives it into a known state so that tests can start from a clean slate; shorter sequences mean cheaper tests.
  • Coding theory. In a synchronizing code, a decoder that has lost track after a transmission error regains synchronization after reading a reset word, so one error does not corrupt the rest of the message. The famous road coloring problem — can the edges of every suitable graph be labelled so the result is synchronizing? — was solved positively by Avraham Trahtman (published 2009).
  • Automata theory itself. Synchronization interacts with the structure studied by DFA minimization and the Myhill–Nerode theorem: it is a question about how the transformations of the states compose, not about which words are accepted.

And because finding the shortest reset word is NP-hard, the problem is also a clean, natural test case for the P vs NP landscape: easy to decide, hard to optimize.

Conclusion

The Černý conjecture is one of the oldest open problems in automata theory, and one of the easiest to state: if a machine can be reset blindfolded, can it always be done in (n−1)2(n-1)^2 steps? Černý's own automata show that number cannot be lowered. Computers confirm it for every small case they can reach. And yet the best theorem we have is cubic — about 0.1654 n30.1654\,n^3 — and every improvement in sixty years has only shaved the constant.

Play with the demo again and notice how hard you have to work to synchronize Cn\mathcal{C}_n, and how easily random machines collapse. The conjecture says nothing can be harder than Černý's slow rotating wheel. Like Collatz, it is a reminder that a simple statement and a stack of evidence still do not add up to a proof.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/cerny-conjecture/Content licensed under CC BY-NC 4.0.