A characterization of eventual periodicity (Q2345445)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A characterization of eventual periodicity |
scientific article |
Statements
A characterization of eventual periodicity (English)
0 references
22 May 2015
0 references
For nonempty words \(w\), \(\xi\) over the binary alphabet \(\left\{ 0,1\right\} \), let \(\left| w\right| _{\xi}\) denote the number of occurrences of the factor \(\xi\) in \(w\). The measure \(\Sigma\left( w\right) =\sum_{\xi \in\left\{ 0,1\right\} ^{+}}\left| w\right| _{\xi}^{2}\) has been introduced in a previous work of the first author with \textit{Y.-M. Xue} [Sankhyā, Ser. A 77, No. 1, 126--152 (2015; Zbl 1319.65007)] as a criterion of randomness of \(w\) together with a proof of the fact that \(\liminf_{n\rightarrow\infty}\frac{\Sigma\left( x_{1}x_{2}\cdots x_{n}\right) }{n^{2}}\geq\frac{3}{2}\), for any infinite sequence \(x_{1}x_{2}\cdots\). In the current paper it is shown that \(\lim_{n\rightarrow\infty}\frac{\Sigma\left( x_{1}x_{2}\cdots x_{n}\right) }{n^{3}}\) exists and is positive if and only if the sequence \(x_{1}x_{2}\cdots\) is eventually periodic (i.e., it is of the form \(uv^{\infty}\)). Moreover, this limit is equal to \(\frac{1}{3k}\), where \(k\) is the length of the shortest period.
0 references
eventually periodic sequence
0 references
Kamae-Xue complexity
0 references
low-complexity sequences
0 references