复杂性函数

在计算机科学中，一个词或字符串（来自某个字母表的有限或无限的符号序列）的复杂性函数是计算该字符串的不同因子（连续符号的子串）数量的函数。更笼统地说，形式语言（一组有限字符串）的复杂性函数计算给定长度的不同词的数量。

让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的不同因子的出现次数，现在我们确定的是只通过位置的互换而不同的因子。