一个词的临界指数

编辑
本词条由“匿名用户” 建档。

在数学和计算机科学中,一个有限字母上的有限或无限符号序列的临界指数描述了一个连续的子序列可以被重复的最大次数。例如,Mississippi的临界指数是7/3,因为它包含长度为7和周期为3的字符串ississi。如果w是字母表A上的一个无限词,x是A上的一个有限词,那么对于正实数α,如果w的一个因子y=xax0,其中x0是x的前缀,a是α的整数部分,长度|y|=α|x|,则称x以指数α出现在w中:我...

一个词的临界指数

编辑

在数学和计算机科学中,一个有限字母上的有限或无限符号序列的临界指数描述了一个连续的子序列可以被重复的xxx次数。例如,Mississippi的临界指数是7/3,因为它包含长度为7和周期为3的字符串ississi。如果w是字母表A上的一个无限词,x是A上的一个有限词,那么对于正实数α,如果w的一个因子y=xax0,其中x0是x的前缀,a是α的整数部分,长度|y|=α|x|,则称x以指数α出现在w中:我们说y是一个α-幂。如果单词w不包含任何β≥α的因子,那么它就是无α幂的。w的临界指数是w具有α幂的α的最高值,或者等同于w无α幂的α的下限值。

一个词的临界指数的例子

编辑

Fibonacci词的临界指数是(5+√5)/2≈3.618。Thue-Morse序列的临界指数是2。这个词包含任意长的方块,但在任何因子xxb中,字母b不是x的前缀。

一个词的临界指数

重复阈值一个有n个字母的字母表A的重复阈值是A上无限词的最小临界指数:显然这个值RT(n)只取决于n。对于n=2,任何长度为4的二进制词都有一个指数2,由于Thue-Morse序列的临界指数是2,所以二进制字母的重复阈值是RT(2)=2。已知RT(3)=7/4,RT(4)=7/5,对于n≥5我们有RT(n)≥n/(n-1)。据猜测,后者是真值,这一点在5≤n≤14和n≥33的情况下已被证实。

内容由匿名用户提供,本内容不代表vibaike.com立场,内容投诉举报请联系vibaike.com客服。如若转载,请注明出处:https://vibaike.com/163847/

(2)
词条目录
  1. 一个词的临界指数
  2. 一个词的临界指数的例子

轻触这里

关闭目录

目录