Papex

Open problem · Computer science · since 1969 · Open

Černý conjecture

If a finite automaton with n states can be reset by some input word, is there always such a word of length at most (n − 1)²?

Summary

A synchronising word sends an automaton to one known state from any starting state. Ján Černý conjectured the (n − 1)² bound in 1969 and gave automata that need exactly that length; the best proved upper bound is still cubic in n.

Why it is open

A deterministic finite automaton has a finite set of states and input letters, each of which moves every state to some state [9]. It is synchronising if some word, called a reset word, leaves it in one particular state whatever state it started in; the length of its shortest reset word is its reset threshold [9]. The notion first appeared explicitly in Černý's paper of 1964, where such automata were called directable [4]. There Černý gave, for each n, an automaton Cₙ with n states and two letters whose shortest reset word has length (n − 1)² [4, 9]. The Černý conjecture says that this is the worst case: every synchronising automaton with n states has a reset threshold of at most (n − 1)² [9].

The 1964 paper did not state the conjecture. It gave only the bounds (n − 1)² ≤ C(n) ≤ 2ⁿ − n − 1 for the largest reset threshold C(n), and expected the upper bound to improve [4]. Mikhail Volkov records that Černý stated the conjecture in a talk at the Bratislava Cybernetics Conference in 1969, and that it first appeared in print in 1971 [4].

A proof for every synchronising automaton, or one automaton whose reset threshold exceeds (n − 1)², would settle the question. No prize or committee sets further terms; the status here follows Wikipedia's list of unsolved problems in computer science [10]. Volkov's list of results, dated January 2026, records the conjecture as "neither confirmed nor refuted", and notes that as of September 2025 not even an upper bound quadratic in n was known [9].

Volkov's 2008 survey notes that the greedy method, which shrinks the set of possible states one step at a time, meets a basic difficulty: "the standard optimality principle does not apply", since a shortest reset word need not act optimally at intermediate steps [4]. Random automata do not help either, because a randomly chosen automaton with a large enough alphabet tends to be synchronising with a reset word of length at most 2n; Volkov concluded in 2008 that there is "no hope" of finding a counterexample by random sampling [4].

What is known

Origins (1964–1971). Černý's paper, in Slovak with an English translation published in 2019 [9], treats "homogeneous experiments" that bring an automaton without output into one determined state, independent of its initial state; it gives necessary and sufficient conditions for their existence and estimates of their minimal length [1]. In 1966 Starke improved the upper bound to 1 + n(n − 1)(n − 2)/2, the first bound polynomial in n [4].

Cubic upper bounds (1970–2019). The greedy algorithm, combined with a combinatorial theorem proved by Péter Frankl in 1982, gives C(n) ≤ (n³ − n)/6 [4, 9]. The bound is usually attributed to Jean-Éric Pin, who explained the connection in a talk in 1981, published in 1983; Volkov notes that it first appeared in a 1970 paper by Fischler and Tannenbaum, derived there from an unproved equivalent conjecture [4]. Marek Szykuła gives the Pin–Frankl bound as (n³ − n)/6 − 1 for n ≥ 4, through a further observation of Pin's [7]. In 2011 Avraham Trahtman claimed the bound (7n³ + 6n − 16)/48, but the proof contains an error: a lemma on avoiding words, words after which the automaton cannot be in a given state, has a counterexample [7]. Using avoiding words, Szykuła improved the Pin–Frankl bound in 2018 to (85059n³ + 90024n² + 196504n − 10648)/511104, with leading coefficient about 0.1664 [7, 9]. In 2019 Yaroslav Shitov modified this approach and obtained a leading coefficient of at most 0.1654 [8]. Volkov's list, in its January 2026 version, gives Shitov's bound as the best known and calls it only a slight improvement on Szykuła's [9].

Classes where the conjecture holds. Many restricted classes satisfy it [9]. David Eppstein, motivated by a reduction of the design of mechanical parts orienters to reset sequences, gave tight bounds for "monotonic" automata [2]; for these automata, now called orientable, whose letters respect a cyclic order of the states, the bound is (n − 1)² [9]. Circular automata, in which one letter permutes all states in a single cycle, also satisfy it [9]. Jarkko Kari proved the bound n² − 3n + 3 for Eulerian automata, whose underlying graph has a cycle using every edge exactly once [9]. Trahtman showed in 2007 that aperiodic automata, whose transition monoids have no nontrivial subgroups, have reset words of length at most n(n − 1)/2, so the conjecture holds for them and for automata that accept only star-free languages [3, 9]. The Papex page Generalised star-height problem discusses star-free languages. The bound n(n − 1)/2 also holds for automata with a zero, a state fixed by every letter [9]. Benjamin Steinberg proved the conjecture in 2011 for one-cluster automata, in which some letter's action has exactly one cycle, when that cycle has prime length [5, 9]. For all one-cluster automata, and for completely reachable automata, in which every non-empty set of states is the image of the whole set under some word, quadratic bounds are known but the conjecture was still open in January 2026 [9].

Extreme automata and computer searches (2008–2016). In 2008 Volkov wrote that very few automata reach (n − 1)², and that automata close to that bound are also rare [4]. By 2016 the series Cₙ was the only known infinite series meeting the bound, with eight further examples of at most six states [6]. Ananichev, Gusev and Volkov checked all automata with two letters and at most 9 states, and a check of all automata with at most 10 states was reported separately [6]. In 2016 Andrzej Kisielewicz, Jakub Kowalski and Szykuła verified the conjecture for all two-letter automata with at most 12 states and all three-letter automata with at most 8 states [6].

Main approaches

Compression. Shrink the set of possible current states with short words until one state remains [9]. Strongest evidence: greedy compression with Frankl's theorem gives the cubic Pin–Frankl bound [4, 9]. Main difficulty: the bound did not improve for about 35 years [7], and shortest compressing steps need not build a shortest reset word [4].

Extension. Start from one state and find short words whose preimages grow until they cover every state [9]. Strongest evidence: if every set of at least two states, other than the whole set, has a larger preimage under some word of length at most n, the conjecture holds; circular and Eulerian automata are handled this way [9]. Main difficulty: for one-cluster and completely reachable automata such words are only known with length up to 2n; for one-cluster automata this gives a bound of the form 2n² + o(n²), not (n − 1)² [9].

Avoiding words. Bound the length of words that exclude a chosen state, then combine them with Frankl's theorem [7]. Strongest evidence: Szykuła's and Shitov's improvements of the Pin–Frankl bound [7, 8]. Main difficulty: the gains are small [9]; Trahtman's lemma that avoiding words of length at most n − 1 always exist is false, and the bound Szykuła proved for avoiding words is quadratic, (n − 1)(n − 2) + 2 [7].

Computer search. Generate automata with long shortest reset words and test conjectures on small cases [6]. Strongest evidence: no counterexample among two-letter automata with up to 12 states [6]. Main difficulty: most of the conjectures tested in this way would imply an improvement of the general cubic bound and are "very hard" [6], and random sampling is not expected to find slowly synchronising automata [4].

Open sub-questions

  1. Short avoiding words. In strongly connected synchronising automata with n states, is 2n − 2 the tight upper bound on the length of shortest avoiding words, as experiments suggest? Szykuła posed this in 2018; the best lower bound he cites, unpublished, is 2n − 3 [7].
  2. A quadratic bound. Is the reset threshold of every synchronising automaton with n states bounded by a fixed quadratic in n, which Volkov's list records as unknown in 2025 [9]?
  3. Eulerian automata. Is ⌊(n² − 3)/2⌋ an upper bound for every Eulerian synchronising automaton with n ≥ 3 states, as Szykuła and Vojtěch Vorel conjectured? Their exhaustive searches confirm it for small cases [9].
  4. Strongly connected aperiodic automata. In a strongly connected automaton every state can reach every other. Is the reset threshold of every strongly connected synchronising aperiodic automaton with n states at most n − 1, as searches up to 11 states with two letters support [9]?
  5. Completely reachable automata. Does every completely reachable automaton with n states have a reset word of length at most (n − 1)², below the known bound 2n² − n ln n − 4n + 2 [9]?
  6. Thirteen states. Does the conjecture hold for every two-letter automaton with 13 states, one beyond the 2016 verification [6]?

Work on this in Papex

If you have a testable answer to one of the sub-questions above, you can draft it as a private hypothesis in Papex, or prepare the draft from Claude or ChatGPT with the Papex connector. You review the exact version, sign it and decide whether to publish it; a public record that names this problem is listed on this page. A Papex record shows who signed which version and when. It is not peer review and does not mean the hypothesis is correct.

Key references

  1. Černý, J. (2019). A note on homogeneous experiments with finite automata. Journal of Automata, Languages and Combinatorics 24(2–4), 123–132. English translation of the 1964 Slovak paper in Matematicko-fyzikálny časopis 14(3), 208–216, as cited in reference 9. 10.25596/jalc-2019-123 · Checked 16 Oct 2026
  2. Eppstein, D. (1990). Reset sequences for monotonic automata. SIAM Journal on Computing 19(3), 500–510. 10.1137/0219033 · Checked 16 Oct 2026
  3. Trahtman, A. N. (2007). The Černý conjecture for aperiodic automata. Discrete Mathematics and Theoretical Computer Science 9(2), 3–10. 10.46298/dmtcs.395 · Checked 16 Oct 2026
  4. Volkov, M. V. (2008). Synchronizing automata and the Černý conjecture. In Language and Automata Theory and Applications (LATA 2008), Lecture Notes in Computer Science 5196, 11–27. 10.1007/978-3-540-88282-4_4 · Checked 16 Oct 2026
  5. Steinberg, B. (2011). The Černý conjecture for one-cluster automata with prime length cycle. Theoretical Computer Science 412(39), 5487–5491. 10.1016/j.tcs.2011.06.012 · Checked 16 Oct 2026
  6. Kisielewicz, A., Kowalski, J. & Szykuła, M. (2016). Experiments with synchronizing automata. In Implementation and Application of Automata (CIAA 2016), Lecture Notes in Computer Science 9705, 176–188. 10.1007/978-3-319-40946-7_15 · Checked 16 Oct 2026
  7. Szykuła, M. (2018). Improving the upper bound on the length of the shortest reset word. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), LIPIcs 96, 56:1–56:13. 10.4230/LIPIcs.STACS.2018.56 · Checked 16 Oct 2026
  8. Shitov, Y. (2019). An improvement to a recent upper bound for synchronizing words of finite automata. Journal of Automata, Languages and Combinatorics 24(2–4), 367–373. 10.25596/jalc-2019-367 · Checked 16 Oct 2026
  9. Volkov, M. V. (2026). List of results on the Černý conjecture and reset thresholds for synchronizing automata. Preprint, arXiv:2508.15655 (version 4, 13 January 2026), not peer reviewed; a list its author updates as results appear. Source · Checked 16 Oct 2026
  10. Wikipedia. List of unsolved problems in computer science (revision of 15 September 2026). Source · Checked 16 Oct 2026

Page reviewed 16 Oct 2026

Source

Open, as listed by Wikipedia · Unsolved problems in computer science. Checked 08 Oct 2026.

The status is the source’s. Papex does not decide whether a problem is solved.

Records on this problem

No public record addresses this problem yet.