未解決問題、組合せ論と離散数学, 応用数学と計算数学、1964年に提起

チェルニー予想（同期オートマトン）

未解決

$n$ 個の状態をもつ任意の同期決定性有限オートマトン（DFA）は、すべての $n$ 個の状態を単一の共通状態へ移す（すなわち $|Q \cdot w| = 1$ を満たす）長さ高々 $(n - 1)^2$ のリセット語（同期語） $w \in \Sigma^*$ をもつ。

研究の最前線 2026年時点

2026年現在、チェルニー予想は未解決であり、一般の同期オートマトンに対して2次の上界 $O(n^2)$ を示すことすら未解決である。現在知られている最良の普遍上界は $\alpha \le 0.1654$ とする $\alpha n^3 + o(n^3)$ （2018年のシクワの結果を改良した2019年のシトフによる）である一方、最悪の下界は依然として $(n - 1)^2$ であり、1964年のチェルニーの族 $\mathcal{C}_n$ と高々有限個の散在型極値オートマトン（すべて状態数 $n \le 6$ ）でのみ達成されている。オイラー的、非周期的、巡回的、単一クラスタ、有向単調オートマトンなどのクラスでは証明されており、ランダム同期オートマトンに対しても高確率で成り立つ。

既知の最良の結果

任意の $n$ 状態同期DFAは $\alpha \approx 0.1654$ として長さ高々 $\alpha n^3 + O(n^2)$ のリセット語をもち（シクワ 2018年、シトフ 2019年）、古典的なパン・フランクル上界 $\frac{n^3 - n}{6}$ を改良している。
チェルニーの境界 $(n - 1)^2$ は、オイラー・オートマトン（カリ、1998年）、巡回オートマトン（デュビュック、1998年）、非周期的オートマトン（トラハトマン、2007年）、および素数長サイクルをもつ単一クラスタ・オートマトン（スタインバーグ、2011年）について証明されている。

使われた手法と限界

手法	達成したこと	限界
フランクルの斜交差集合定理と回避語	サイズ $k \ge 2$ の状態部分集合 $S$ をサイズ $k - 1$ に圧縮する最短語の長さを $\binom{n - k + 2}{2}$ で抑え（パン・フランクル）、回避語に関する線形代数的ランク評価によってこれを精密化した（シクワ、シトフ）。	$k = n, n-1, \dots, 2$ にわたって各段階の $O((n - k)^2)$ ステップを足し上げると必然的に $O(n^3)$ の上界となり、1段階あたり償却 $O(n)$ での圧縮を示さない限り3次の壁を越えられない。
遷移モノイドの線形代数表現（カリ、スタインバーグ）	入力文字に行列を対応させ、基礎となる有向グラフの定常分布と $\mathbb{R}^n$ における次元議論を組み合わせて、オイラー・オートマトンや単一クラスタ・オートマトンに対する $O(n^2)$ 上界を確立した。	一般の同期オートマトンは正の定常ベクトルや一様な入次数をもたないため、短い語に沿って逆像の重みが単調に増加するとは限らない。

未解決の問い

任意の $n$ 状態同期DFAが長さ高々 $C n^2$ （2次オーダー）のリセット語をもつような普遍定数 $C > 0$ が存在するか。
$n \ge 7$ において、リセット閾値 $(n - 1)^2$ を達成する極小な $n$ 状態同期オートマトンは（同型と冗長な文字を除いて）チェルニーのオートマトン $\mathcal{C}_n$ に限られるか。

参考文献

Mikhail V. Volkov (2008). Synchronizing automata and the Černý conjecture · DOI:10.1007/978-3-540-78926-0_2
Marek Szykuła (2018). Improving the upper bound on the length of the shortest reset word · DOI:10.4230/LIPIcs.STACS.2018.56 · arXiv:1702.05455
Yaroslav Shitov (2019). An improvement to a recent upper bound for synchronizing words of finite automata · DOI:10.1016/j.jcta.2019.04.007 · arXiv:1901.06542