複雑度関数

コンピュータサイエンスにおいて、単語または文字列（あるアルファベットの有限または無限の記号の列）の複雑度関数は、その文字列の異なる要素（連続する記号の部分文字列）の数を数える関数です。より一般的には、形式言語（有限の文字列のセット）の複雑度関数は、指定された長さの異なる単語の数を数えます。

u をアルファベットの記号の（無限の可能性のある）シーケンスとします。正の整数nの関数 p _u ( n ) を、文字列 uの長さnの異なる因数（連続する部分文字列）の数として定義します。^{[1] [2] [3] [4] [5]}

長さが少なくともnの文字列uをサイズkのアルファベットで表すと、明らかに

${\displaystyle 1\leq p_{u}(n)\leq k^{n}\ ,}$

境界は定数語と選言語によって達成され、^[6]例えば、それぞれチャンパーノウン語である。^[7]無限語u に対して、u が究極的に周期的（有限で、空の可能性もあるシーケンスの後に有限のサイクルが続く）であれば、 p u ( n ) は有界である_。逆に、あるnに対してp _u ( n ) ≤ nであれば、u は究極的に周期的である。^{[3] [8]}

非周期的シーケンスは、究極的には周期的ではないシーケンスです。非周期的シーケンスは厳密に増加する複雑性関数を持ちます（これはモース-ヘドランド定理です）^{[9] [10]}ので、 p ( n )は少なくともn +1です。^[11]

有限の2進ワードの集合Sは、各nに対して長さ_nのワードの部分集合SnがSn内のワードのハミング重みが_最大で2つの異なる値を取るという性質を持つとき、バランスが取れている。バランスの取れたシーケンスとは、因子の集合がバランスが取れているシーケンスである。^[12] バランスの取れたシーケンスの複雑性関数は最大でn +1である。^[13]

2進アルファベット上のシュトゥルム語は、複雑度関数がn + 1である語である。[ 14  ]^{シーケンス}がシュトゥルム語である ためには、バランスが取れていて非周期的である必要がある。^{[2] [15]} 例としては、フィボナッチ語がある。^{[14] [16]} より一般的には、サイズkのアルファベット上のシュトゥルム語は、複雑度がn + k −1である語である。3進アルファベット上のアルヌー・ロージ語は、複雑度が2 n  + 1である。^[14]例としては、トリボナッチ語がある。^[17]

各因子が無限に出現する再帰語の場合、複雑度関数は因子の集合をほぼ特徴付ける。つまり、 sがtと同じ複雑度関数を持つ再帰語である場合、 sはtまたはδtと同じ因子の集合を持つ。ここでδは文字重複射a → aaを表す。^[18]

Lをアルファベット上の言語とし、正の整数nの関数pL(n)をL内の長さnの異なる単語の数として定義する[ 9 ]単語の複雑_度関数は、したがって^、 その単語の要素からなる言語の複雑度関数である。

言語の複雑性関数は単語の複雑性関数ほど制約を受けません。例えば、複雑性関数は有界であっても最終的には一定ではありません。正規言語の複雑性関数は、奇数n ≥ 2と偶数 n ≥ 2でそれぞれ3と4の値を取ります。モース・ヘドランド定理の類似物があります。Lの複雑性が、あるnに対してp L ( n ) ≤ nを満たす場合、 p Lは_有界であり、有限言語Fが_存在し、[ 9 ^]${\displaystyle a(bb)^{*}a}$

${\displaystyle L\subseteq \{xy^{k}z:x,y,z\in F,\ k\in \mathbb {N} \}\ .}$

多項式言語またはスパース言語とは、計算量関数p ( n ) がnの一定のべき乗で制限される言語である。多項式でない正規言語は指数関数的である。つまり、ある一定のk > 1に対してp ( n ) がk ⁿより大きいn は無限に存在する。^[19]

無限列uの位相エントロピーは次のように定義される。

${\displaystyle H_{\mathrm {top} }(u)=\lim _{n\rightarrow \infty }{\frac {\log p_{u}(n)}{n\log k}}\ .}$

極限は、複雑性関数の対数が劣加法的であるために存在する。^{[20] [21]} 0と1の間のすべての実数は、何らかのシーケンスの位相エントロピーが適用可能であるため発生し、^[22]一様回帰的であると考えられる場合もあれば、 ^[23]一意にエルゴード的であると考えられる場合もある。^[24]

x が実数でbが 2 以上の整数である場合、基数bにおけるxの複雑度関数は、基数bで書かれたxの数字列の複雑度関数p ( x , b , n ) である。xが無理数の場合、p ( x , b , n ) ≥ n +1 である。xが有理数の場合、xとbに依存する定数Cに対してp ( x , b , n ) ≤ Cである。^{[6]代数的無理数}xの場合、複雑度はb ⁿである と推測される(このような数がすべて正規分布であればそうなる) が、この場合にわかっていることは、p がnのどの線形関数よりも速く増大することだけである。^[25]

アーベル複雑度関数 p ^ab ( n )は同様に、与えられた長さnの異なる因数の出現回数を数える。ここでは位置の順列のみが異なる因数を識別している。明らかにp ^ab ( n ) ≤ p ( n )である。シュトゥルム数列のアーベル複雑度はp ^ab ( n ) = 2を満たす。 ^[26]

• Allouche, Jean-Paul; Shallit, Jeffrey (2003)。自動シーケンス: 理論、アプリケーション、一般化。ケンブリッジ大学出版局。ISBN 978-0-521-82332-6.ZBL1086.11015  。​
• Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009)。単語の組合せ論。クリストッフェル語と単語の繰り返し。CRM モノグラフ シリーズ。第 27 巻。プロビデンス、ロードアイランド州:アメリカ数学協会。ISBN 978-0-8218-4480-9.ZBL1161.68043  。​
• Berthé, Valérie ; Rigo, Michel 編 (2010)。組合せ論、オートマトン、数論。数学とその応用百科事典。第 135 巻。ケンブリッジ:ケンブリッジ大学出版局。ISBN 978-0-521-51597-9.ZBL1197.68006  。​
• Bugeaud, Yann (2012)。分布法 1 とディオファントス近似。ケンブリッジ数学論文集。第 193 巻。ケンブリッジ:ケンブリッジ大学出版局。ISBN 978-0-521-11169-0.ZBL1260.11001  。​
• Cassaigne, Julien; Nicolas, François (2010)。「因子複雑性」。Berthé , Valérie、Rigo, Michel (編)。組合せ論、オートマトン、数論。数学とその応用百科事典。第 135 巻。ケンブリッジ:ケンブリッジ大学出版局。pp. 163–247。ISBN 978-0-521-51597-9.ZBL1216.68204  。​
• ロテール、M. (2011)。単語の代数的組合せ論。数学とその応用百科事典。第90巻。ジャン・ベルステルとドミニク・ペランによる序文付き（2002年ハードカバー版の再版）。ケンブリッジ大学出版局。ISBN 978-0-521-18071-9.ZBL1221.68183  。​
• ピテアス・フォッグ、N. (2002)。Berthé, ヴァレリー;フェレンチ、セバスチャン。モーデュイ、クリスチャン。シーゲル、A. (編)。力学、算術、組み合わせ論における置換。数学の講義ノート。 Vol. 1794年。ベルリン：シュプリンガー・フェルラーク。ISBN 3-540-44141-7.ZBL1014.11015  .​