2014/04/17 by Kamae, Teturo, Kim, Dong Han
#68R15 #Computational Complexity (cs.CC) #Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1404.4416
In this article, we show that the Kamae-Xue complexity function for an infinite sequence classifies eventual periodicity completely. We prove that an infinite binary word x1x2 ⋯ is eventually periodic if and only if Σ(x1x2⋯ xn)/n3 has a positive limit, where Σ(x1x2⋯ xn) is the sum of the squares of all the numbers of appearance of finite words in x1 x2 ⋯ xn, which was introduced by Kamae-Xue as a criterion of randomness in the sense that x1x2⋯ xn is more random if Σ(x1x2⋯ xn) is smaller. In fact, it is known that the lower limit of Σ(x1x2⋯ xn) /n2 is at least 3/2 for any sequence x1x2 ⋯, while the limit exists as 3/2 almost surely for the (1/2,1/2) product measure. For the other extreme, the upper limit of Σ(x1x2⋯ xn)/n3 is bounded by 1/3. There are sequences which are not eventually periodic but the lower limit of Σ(x1x2⋯ xn)/n3 is positive, while the limit does not exist.