復雜性函數

在計算機科學中，一個詞或字符串（來自某個字母表的有限或無限的符號序列）的復雜性函數是計算該字符串的不同因子（連續符號的子串）數量的函數。更籠統地說，形式語言（一組有限字符串）的復雜性函數計算給定長度的不同詞的數量。

讓u是一個字母表中的（可能是無限的）符號序列。定義一個正整數n的函數pu(n)為來自字符串u的長度為n的不同因子（連續子串）的數量。對于在大小為k的字母表上長度至少為n的字符串u，我們顯然有這些界限分別由常數詞和不連貫詞實現，例如，Champernowne詞。對于無限的詞u，如果u最終是周期性的（一個有限的，可能是空的序列，后面是一個有限的循環），我們就有pu(n)的約束。反過來說，如果pu(n)≤n，對于某些n，那么u最終是周期性的。一個非周期性的序列是一個非最終周期性的序列。一個非周期性序列具有嚴格增加的復雜性函數（這是Morse-Hedlund定理），所以p(n)至少是n+1。如果對于每一個n，長度為n的詞的子集Sn具有這樣的特性，即Sn中的詞的漢明權重最多只有兩個不同的值，那么有限二進制詞的集合S就是平衡的。一個平衡的序列是一個因素集合是平衡的。一個平衡的序列的復雜度函數最多為n+1。一個二進制字母上的Sturmian字是一個具有復雜度函數n+1的字。當且僅當一個序列是平衡的和非周期性的，它就是斯圖爾米亞序列。一個例子是Fibonacci詞。更一般地說，在大小為k的字母表上的一個斯圖米亞字是一個具有n+k-1復雜度的字。在一個三元字母上的Arnoux-Rauzy詞具有2n+1的復雜度：一個例子是Tribonacci詞。對于遞歸詞，即那些每個因子無限次出現的詞，復雜度函數幾乎描述了因子的集合：如果s是一個具有與t相同復雜度函數的遞歸詞，那么s具有與t或δt相同的因子集合，其中δ表示字母加倍的變形a→aa。

讓L是字母表上的語言，定義正整數n的函數pL(n)為L中長度為n的不同詞的數量。因此，一個詞的復雜性函數就是由該詞的因子組成的語言的復雜性函數。一個語言的復雜度函數比一個詞的復雜度函數的約束要小。例如，它可能是有界的，但最終不是常數：普通語言的復雜度函數在奇數和偶數n≥2上分別取值3和4。有一個類似于Morse-Hedlund定理的定理：如果L的復雜性滿足pL(n)≤n，對于某些n，那么pL是有界的，并且有一個有限語言F，以便多項式或稀疏式語言是指復雜度函數p(n)被n的一個固定冪所約束的語言。一個非多項式的規則語言是指數級的：有無限多的n，對于這些n來說，p(n)在某個固定的k>1中大于k。

無限序列u的拓撲熵定義為由于復雜性函數的對數是次加性的，所以極限存在。0和1之間的每一個實數都會出現，因為某個序列的拓撲熵是適用的，它可以被認為是均勻的重復性的，甚至是xxx的遍歷性的。對于x是一個實數，b是一個≥2的整數，那么x在基數b中的復雜度函數就是以基數b書寫的x的數字序列的復雜度函數p(x,b,n)。如果x是一個無理數，那么p(x,b,n)≥n+1；如果x是有理數，那么p(x,b,n)≤C，取決于x和b的某個常量C。據猜測，對于代數無理數x，其復雜度為bn（如果所有這類數字都是正常的，就會出現這種情況），但在這種情況下，所有已知的是p的增長速度比n的任何線性函數都快。非線性復雜度函數pab(n)同樣計算了給定長度為n的不同因子的出現次數，現在我們確定的是只通過位置的互換而不同的因子。