کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
433908 | 689650 | 2015 | 8 صفحه PDF | دانلود رایگان |
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⋯x1x2⋯ is eventually periodic if and only if Σ(x1x2⋯xn)/n3Σ(x1x2⋯xn)/n3 has a positive limit, where Σ(x1x2⋯xn)Σ(x1x2⋯xn) is the sum of the squares of all the numbers of occurrences of finite words in x1x2⋯xnx1x2⋯xn, which was introduced by Kamae–Xue as a criterion of randomness in the sense that x1x2⋯xnx1x2⋯xn is more random if Σ(x1x2⋯xn)Σ(x1x2⋯xn) is smaller. In fact, it is known that the lower limit of Σ(x1x2⋯xn)/n2Σ(x1x2⋯xn)/n2 is at least 3/2 for any sequence x1x2⋯x1x2⋯, while the limit exists as 3/2 almost surely for the (1/2,1/2)(1/2,1/2) product measure. For the other extreme, the upper limit of Σ(x1x2⋯xn)/n3Σ(x1x2⋯xn)/n3 is bounded by 1/3. There are sequences which are not eventually periodic but the lower limit of Σ(x1x2⋯xn)/n3Σ(x1x2⋯xn)/n3 is positive, while the limit does not exist.
Journal: Theoretical Computer Science - Volume 581, 24 May 2015, Pages 1–8