A characterization of eventual periodicity (Q2345445): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1979612752 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1404.4416 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An easy criterion for randomness / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Return time complexity of Sturmian sequences / rank | |||
Normal rank |
Latest revision as of 03:36, 10 July 2024
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