この図は、8つの状態と2つの入力記号（赤と青）を持つDFAを表しています。単語 blue-red-red-blue-red-red-blue-red-red は、すべての状態を黄色の状態に遷移させる同期語です（単語 red-red-red-blue-red-red-blue-red-red も同様です）。単語 blue-blue-red-blue-blue-red-blue-blue-red は、すべての状態を緑色の状態に遷移させる別の同期語です。 コンピュータ科学、より正確には 決定性有限オートマトン （DFA）の理論において、同期ワード またはリセットシーケンスと は、 DFA の入力アルファベット内のワードで、DFA の任意の状態を 1 つの同じ状態に送るものです。[ 1 ]
存在 DFA が与えられたとき、同期語が存在するかどうかを判定する問題は、 Ján Černý による定理を用いて多項式時間で解くことができます [ 2 ] 指数関数的 です。しかし、Černý の定理により、この問題のサブストラクチャを利用して、同期語が存在するのは、すべての状態のペアが同期語を持つ場合のみであることを示す多項式アルゴリズムが得られます。
長さ コンピュータサイエンスにおける未解決問題
DFA が
n {\displaystyle n} 状態には同期ワードがあり、最大で長さが1つである必要があります
（ n − 1 ） 2 {\displaystyle (n-1)^{2}} ？
同期語の長さを推定する問題は長い歴史を持ち、複数の著者が独立して提起してきたが、一般的にはチェルニー予想 として知られている。1969年、ヤン・チェルニー は、任意のn 状態 完全DFA（完全な 状態遷移グラフ を持つDFA ）の最短同期語の長さの上限 は(n-1 ) 2 であると予想した。[ 3 ] n でインデックス付けされる）を示した。[ 4 ] 、 下限 からは程遠い。[ 5 ] k文字の入力アルファベット上の n 状態 DFA の場合、 David Eppstein によるアルゴリズムは、最大で 11 n 3 /48 + O ( n 2 )の長さの同期語を見つけ、時間計算量は O ( n 3 + kn 2 ) です。このアルゴリズムは、与えられたオートマトンに対して常に最短の同期語を見つけるとは限りません。Eppstein が示すように、最短の同期語を見つける問題はNP 完全 です。しかし、すべての状態遷移が状態の巡回順序 を保持する特殊なクラスのオートマタについては、常に最短の同期語を見つける時間 O( kn 2 ) の別のアルゴリズムを記述し、これらのオートマタは常に最大 ( n − 1) 2 (Černý の予想で与えられた上限) の長さの同期語を持つことを証明し、最短の同期語の長さがちょうど ( n − 1) 2 であるこの特殊な形式のオートマタの例を示しています。[ 2 ]
変換半群 は、ランク 1 の要素、つまり像の濃度が 1 の要素を含む場合、同期的である。 [ 8 ]
参考文献 ↑ Avraham Trakhtman: Synchronizing automata, algorithms, Cerny Conjecture . 2010年5月15日アクセス。 1 2 Eppstein, David (1990)、「Reset Sequences for Monotonic Automata」（PDF） 、SIAM Journal on Computing 19 （3）：500–510 、doi ：10.1137/0219033。↑ Volkov, Mikhail V. (2008), "Synchronizing Automata and the Černý Conjecture", Proc. 2nd Int'l. Conf. Language and Automata Theory and Applications (LATA 2008) , LNCS, vol. 5196, Springer-Verlag, pp. 11– 27, doi : 10.1007/978-3-540-88282-4_4 , ISBN 978-3-540-88281-7 ↑ チェルニー、ヤン( 1964)、 「Poznámka k homogénnym Experimentom s konečnými automatmi」 (PDF) 、 Matematicko-fyzikálny časopis Slovenskej Akadémie Vied 、 14 : 208–216 ↑ Shitov, Yaroslav (2019), "有限オートマタの同期語に関する最近の上限の改善" (PDF) , Journal of Automata, Languages and Combinatorics , 24 ( 2– 4): 367– 373, arXiv : 1901.06542 , MR 4023068 ↑ Adler, RL; Weiss, B. (1970), "トーラスの自己同型写像の相似性", Memoirs of the American Mathematical Society , 98 ↑ Trahtman, AN (2009), "道路の着色問題", Israel Journal of Mathematics , 172 : 51–60 , arXiv : 0709.0099 , doi : 10.1007/s11856-009-0062-5 , MR 2534238 ↑ キャメロン、ピーター (2013)、 置換群と変換半群 (PDF)
さらに読む Rystsov, IC (2004)、「Černýの予想：回顧と展望」、トゥルク同期オートマタワークショップ議事録（WSA 2004） Jürgensen, H. (2008)、「同期」、Information and Computation 、206 ( 9–10 ): 1033–1044 、doi : 10.1016/j.ic.2008.03.005 Volkov, Mikhail V. (2008)、「同期オートマタとチェルニー予想」、第2回国際言語・オートマタ理論および応用会議（LATA 2008）議事録 （PDF） 、LNCS、第5196巻、Springer-Verlag、 11～ 27 ページ 
