同期ワード

コンピュータサイエンス、より正確には決定性有限オートマトン（DFA）の理論において、同期ワードまたはリセットシーケンスは、DFAの入力アルファベット内のワードであり、DFAの任意の状態を1つの同じ状態に送信します。^[1]つまり、DFAのコピーのアンサンブルがそれぞれ異なる状態で開始され、すべてのコピーが同期ワードを処理する場合、それらはすべて同じ状態になります。すべてのDFAに同期ワードがあるわけではありません。たとえば、偶数長のワード用と奇数長のワード用の2つの状態を持つDFAは、同期できません。

存在

DFA が与えられた場合、それが同期ワードを持つかどうかを判断する問題は、 Ján Černý の定理を使用して多項式時間^[2]で解決できます。単純なアプローチでは、DFA の状態のべき集合を考慮し、ノードがべき集合に属し、有向エッジが遷移関数の動作を記述する有向グラフを構築します。すべての状態のノードから単一の状態へのパスは、同期ワードの存在を示します。このアルゴリズムは状態の数に対して指数関数的です。ただし、問題の部分構造を利用する Černý の定理により、多項式アルゴリズムが得られ、すべての状態のペアに同期ワードがある場合に限り、同期ワードが存在することが示されます。

長さ

コンピュータサイエンスにおける未解決の問題:

状態を持つ DFA に同期ワードがある場合、その長さは最大である必要がありますか?

n

(n-1)^{2}

(コンピュータサイエンスにおける未解決の問題)

同期語の長さを推定する問題には長い歴史があり、複数の著者によって独立に提起されましたが、一般的にはチェルニー予想として知られています。1969年に、ヤン・チェルニーは、( n − 1) ^{2 が}、任意のn状態完全 DFA (完全な状態遷移グラフを持つ DFA )の最短同期語の長さの上限であると予想しました。 ^[3]これが本当であれば、それは厳密なものです。1964 年の論文で、チェルニーは、最短リセット語がこの長さになるオートマトン (状態の数nでインデックス付け) のクラスを示しました。 ^[4]知られている最良の上限は 0.1654 n ³で、下限からは程遠いものです。^[5]k文字の入力アルファベットに対するn状態 DFA について、 David Eppsteinによるアルゴリズムは、最大で 11 n ³ /48 + O ( n ² ) の長さの同期語を見つけ、実行時間計算量 O ( n ³ + kn ² ) で実行されます。このアルゴリズムは、特定のオートマトンに対して可能な限り最短の同期語を常に見つけるわけではありません。Eppstein も示しているように、最短の同期語を見つける問題はNP 完全です。ただし、すべての状態遷移が状態の循環順序を保存する特殊なクラスのオートマトンについては、時間 O( kn ² ) で常に最短の同期語を見つける別のアルゴリズムを説明し、これらのオートマトンは常に最大で ( n − 1) ^{2 (チェルニーの予想で与えられた境界) の長さの同期語を持つことを証明し、この特殊な形式のオートマトンで最短の同期語の長さがちょうど (}n − 1) ²である例を示しています。^[2]

道路の色分け

道路彩色問題は、同期可能なDFAを形成するために、k文字の入力アルファベット（kは各頂点の出次数）の記号で正則有向グラフの辺にラベルを付ける問題である。1970年にベンジャミン・ワイスとロイ・アドラーは、強く連結された非周期的な正則有向グラフはどれもこの方法でラベル付けできると予想し、2007年にアブラハム・トラハトマンによってその予想が証明された。^[6]^[7]

変換半群は、ランク1の要素、つまり像の濃度が1である要素を含む場合、同期している。^[8] DFAは、区別された生成子セットを持つ変換半群に対応する。

参考文献

^ Avraham Trakhtman: 同期オートマトン、アルゴリズム、Cerny 予想。2010 年 5 月 15 日にアクセス。
^ ab 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)、「同期オートマトンとチェルニー予想」、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特に19ページを参照
^ チェルニー、ヤン (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)、「トーラスの自己同型の類似性」、アメリカ数学会誌、98。
^ Trahtman, AN (2009)、「道路の色分け問題」、イスラエル数学ジャーナル、172 : 51–60、arXiv : 0709.0099、doi : 10.1007/s11856-009-0062-5、MR 2534238
^ キャメロン、ピーター (2013)、順列群と変換半群(PDF)。

さらに読む

Rystsov, IC (2004)、「チェルニーの予想：回顧と展望」、Proc. Worksh. Synchronizing Automata、トゥルク (WSA 2004)。
Jürgensen, H. (2008)、「同期」、情報と計算、206 (9–10): 1033–1044、doi : 10.1016/j.ic.2008.03.005
Volkov, Mikhail V. (2008)、「同期オートマトンとチェルニー予想」、Proc. 2nd Int'l. Conf. Language and Automata Theory and Applications (LATA 2008) (PDF)、LNCS、vol. 5196、Springer-Verlag、pp. 11–27

[trakht-syn-1] Avraham Trakhtman: 同期オートマトン、アルゴリズム、Cerny 予想。2010 年 5 月 15 日にアクセス。

[eppstein-2] Eppstein, David (1990)、「Reset Sequences for Monotonic Automata」(PDF)、SIAM Journal on Computing、19 (3): 500–510、doi :10.1137/0219033。

[3] Volkov, Mikhail V. (2008)、「同期オートマトンとチェルニー予想」、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特に19ページを参照

[cerny-4] チェルニー、ヤン (1964)、「Poznámka k homogénnym Experimentom s konečnými automatmi」(PDF)、Matematicko-fyzikálny časopis Slovenskej Akadémie Vied、14 : 208–216（スロバキア語）。

[5] Shitov, Yaroslav (2019)、「有限オートマトンにおける同期語の最近の上限の改善」(PDF)、Journal of Automata, Languages and Combinatorics、24 (2–4): 367–373、arXiv : 1901.06542、MR 4023068

[6] Adler, RL; Weiss, B. (1970)、「トーラスの自己同型の類似性」、アメリカ数学会誌、98。

[7] Trahtman, AN (2009)、「道路の色分け問題」、イスラエル数学ジャーナル、172 : 51–60、arXiv : 0709.0099、doi : 10.1007/s11856-009-0062-5、MR 2534238

[8] キャメロン、ピーター (2013)、順列群と変換半群(PDF)。

存在

長さ

道路の色分け

関連: 変換半群

参考文献

さらに読む

関連するトピック

コンピュータサイエンス

決定性有限オートマトン

多項式時間

指数関数的