理論計算機科学において、単語分離問題とは、与えられた2つの文字列に対して異なる動作をする、つまり2つの文字列のうち一方を受け入れ、もう一方を拒否する最小の決定性有限オートマトンを見つける問題である。最悪の場合、そのようなオートマトンが入力文字列の長さの関数としてどの程度の大きさになるかは 未解決問題である。
例
2つの文字列0010と1000は、3状態オートマトンによって互いに区別することができる。このオートマトンでは、開始状態から2つの異なる状態に遷移するが、どちらの状態も終端状態である。つまり、これらの2つの状態からの以降の遷移は常に同じ状態に戻る。このオートマトンの状態は、入力文字列の最初の記号を記録する。2つの終端状態のうち1つが受理状態で、もう1つが拒否状態の場合、オートマトンでは文字列0010と1000のどちらか一方のみを受け入れる。しかし、これらの2つの文字列は、3状態未満のオートマトンでは区別できない。[1]
仮定を単純化する
この問題の境界値を証明するために、一般性を損なうことなく、入力が2文字のアルファベット上の文字列であると仮定することができる。なぜなら、より大きなアルファベット上の2つの文字列が異なる場合、それらを同じ長さでかつ異なる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つのバイナリワードが異なる数の0または1を持つ場合、対数の大きさの素数を法としてハミング重みを数えることで、対数状態数を用いてそれらを区別することができます。より一般的には、長さkのパターンが2つのワードに異なる回数出現する場合、O ( k log n )状態を用いてそれらを区別することができます。[1]
- 2つのバイナリワードが、最初のk個または最後のk個の位置で互いに異なる場合、 k + O (1)個の状態を用いて互いに区別することができます。これは、ほぼすべてのバイナリワードのペアが対数的な状態数で互いに区別できることを意味します。なぜなら、最初のO (log n )個の位置で違いがないペアは、多項式的にごくわずかだからです。[1]
- 2つのバイナリワードのハミング距離が dである場合、 p = O ( d log n )となる素数pと、 2つの文字列が異なる位置iが存在する。この位置iは、 pを法として他のどの差異の位置とも等しくない。入力シンボルのパリティをpを法としてiと一致する位置で計算することにより、 O ( d log n )の状態を持つオートマトンを用いてワードを区別することができる。[1]
参考文献
- ^ abcdef Demaine, Erik D. ; Eisenstat, Sarah; Shallit, Jeffrey ; Wilson, David A. (2011)、「単語の分離に関する考察」、Descriptional Complexity of Formal Systems: 13th International Workshop, DCFS 2011, Gießen/Limburg, Germany, July 25-27, 2011, Proceedings , Lecture Notes in Computer Science, vol. 6808, Heidelberg: 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), 「オートマタによる単語の識別について」, Automata, Languages and Programming: 13th International Colloquium, Rennes, France, July 15–19, 1986, Proceedings , Lecture Notes in Computer Science, vol. 226, Berlin: 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）。
