Loading article…
理論計算機科学において、単語分離問題とは、与えられた 2 つの文字列に対して異なる動作をする、つまり 2 つの文字列のうちの 1 つを受け入れ、もう 1 つの文字列を拒否する最小の決定論的有限オートマトンを見つける問題です。最悪の場合、入力文字列の長さの関数として、そのようなオートマトンがどの程度の大きさになるかは 未解決の問題です。
例
2 つの文字列 0010 と 1000 は、開始状態から 2 つの異なる状態に遷移する 3 状態オートマトンによって区別できます。これらの 2 つの状態は、後続の遷移が常に同じ状態に戻るという意味で終端状態です。このオートマトンの状態は、入力文字列の最初の記号を記録します。2 つの終端状態の 1 つが受け入れ状態で、もう 1 つが拒否状態の場合、オートマトンでは文字列 0010 と 1000 のいずれか 1 つだけを受け入れます。ただし、これらの 2 つの文字列は、状態が 3 つ未満のオートマトンでは区別できません。[1]
仮定を単純化する
この問題の限界を証明するために、一般性を失うことなく、入力が2文字のアルファベット上の文字列であると仮定することができます。なぜなら、より大きなアルファベット上の2つの文字列が異なる場合、それらを同じ長さで異なるバイナリ文字列にマッピングする文字列準同型が存在するからです。バイナリ文字列を区別するオートマトンはすべて、状態数を増やすことなく、元の文字列を区別するオートマトンに変換できます。[1]
2 つの文字列の長さが等しいと仮定することもできます。長さが異なる文字列の場合、2 つの入力長さの小さい方に対して対数値となる素数 p が常に存在し、2 つの長さはp を法として異なります。この場合、入力の長さを p を法として数えるオートマトンを使用して 2 つの文字列を区別できます。したがって、長さが異なる文字列は、状態の少ないオートマトンによって常に区別できます。[1]
歴史と限界
2つの文字列を区別するオートマトンのサイズを制限する問題は、Goralčík & Koubek (1986) によって初めて定式化され、オートマトンのサイズは常に線形以下であることが示されました。[2]その後、Robson (1989) は、必要なオートマトンサイズの上限O ( n 2/5 (log n ) 3/5 )を証明しました。 [3]これは Chase (2020) によってO ( n 1/3 (log n ) 7 )に改良されました。[4] [5]
長さnのバイナリ文字列である入力のペアが存在し、入力を区別するオートマトンのサイズはΩ(log n )でなければなりません。この下限とチェイスの上限の間のギャップを埋めることは未解決の問題です。ジェフリー・シャリットはロブソンの上限を改善した人に100ポンドの賞金を出すと発表しました。[6]
特別なケース
単語の分離問題のいくつかの特殊なケースは、少数の状態を使用して解決できることが知られています。
- 2つの2進ワードが異なる数の0または1を持っている場合、対数の数の状態を使用して、対数サイズの素数を法とするハミング重みを数えることで、それらを区別することができます。より一般的には、長さkのパターンが2つのワードで異なる回数出現する場合、O（k log n）状態を使用してそれらを区別することができます。[1]
- 2つのバイナリワードが最初または最後のk個の位置で互いに異なる場合、 k + O (1)状態を使用してそれらを区別することができます。これは、ほとんどすべてのバイナリワードのペアが対数状態数で互いに区別できることを意味します。なぜなら、ペアの多項式的に小さな割合だけが最初のO (log n )位置に違いがないからです。[1]
- 2つのバイナリワードのハミング距離が dである場合、 p = O ( d log n )となる素数pと、 2つの文字列が異なる位置iが存在し、 iはpを法として他のどの違いの位置とも等しくありません。iを法としてpと一致する位置にある入力シンボルのパリティを計算することで、 O ( d log n )の状態を持つオートマトンを使用してワードを区別することができます。[1]
参考文献
- ^ abcdef Demaine, Erik D. ; Eisenstat, Sarah; Shallit, Jeffrey ; Wilson, David A. (2011)、「単語の分離に関する注意」、形式システムの記述的複雑性: 第 13 回国際ワークショップ、DCFS 2011、ギーセン/リンブルフ、ドイツ、2011 年 7 月 25 ～ 27 日、議事録、コンピュータ サイエンスの講義ノート、vol. 6808、ハイデルベルク: Springer-Verlag、pp. 147 ～ 157、arXiv : 1103.4513、doi :10.1007/978-3-642-22600-7_12、ISBN 978-3-642-22599-4、MR 2910373、S2CID 6959459。
- ^ Goralčík, P.; Koubek, V. (1986)、「オートマトンによる単語の識別について」、オートマトン、言語、プログラミング: 第 13 回国際コロキウム、レンヌ、フランス、1986 年 7 月 15 ～ 19 日、議事録、コンピュータ サイエンスの講義ノート、第 226 巻、ベルリン: Springer-Verlag、pp. 116 ～ 122、doi :10.1007/3-540-16761-7_61、ISBN 978-3-540-16761-7、MR 0864674。
- ^ Robson, JM (1989)、「小さなオートマトンによる文字列の分離」、Information Processing Letters、30 (4): 209–214、doi :10.1016/0020-0190(89)90215-9、MR 0986823。
- ^ Chase, Z. (2020)、「単語を区切るための新しい上限」、arXiv : 2007.12097 [math.CO]。
- ^ Chase, Zachary (2021-06-15). 「単語の分離とトレースの再構築」。第53回ACM SIGACTコンピューティング理論シンポジウム議事録。STOC 2021。ニューヨーク、ニューヨーク州、米国：Association for Computing Machinery。pp. 21–31。doi : 10.1145 /3406325.3451118。ISBN 978-1-4503-8053-9。
- ^ Shallit, Jeffrey (2014)、「オートマトン理論における未解決問題: 特異な視点」、英国理論計算機科学会議 (BCTCS 2014)、ラフバラー大学(PDF)。