Name
Abstract | ||
|---|---|---|
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 $x_1x_2 cdots $ is eventually periodic if and only if $Sigma(x_1x_2cdots x_n)/n^3$ has a positive limit, where $Sigma(x_1x_2cdots x_n)$ is the sum of the squares of all the numbers of appearance of finite words in $x_1 x_2 cdots x_n$, which was introduced by Kamae-Xue as a criterion of randomness in the sense that $x_1x_2cdots x_n$ is more random if $Sigma(x_1x_2cdots x_n)$ is smaller. In fact, it is known that the lower limit of $Sigma(x_1x_2cdots x_n) /n^2 $ is at least 3/2 for any sequence $x_1x_2 cdots$, 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 $Sigma(x_1x_2cdots x_n)/n^3$ is bounded by 1/3. There are sequences which are not eventually periodic but the lower limit of $Sigma(x_1x_2cdots x_n)/n^3$ is positive, while the limit does not exist. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.tcs.2015.02.039 | Theoretical Computer Science |
Keywords | DocType | Volume |
combinatorics on words | Journal | 581 |
Issue | ISSN | Citations |
C | 0304-3975 | 0 |
PageRank | References | Authors |
0.34 | 1 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Teturo Kamae | 1 | 25 | 5.20 |
| Dong Han Kim | 2 | 119 | 18.40 |