*-Sturmian words and complexity (Q558168): Difference between revisions
From MaRDI portal
Changed an Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 07:59, 30 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | *-Sturmian words and complexity |
scientific article |
Statements
*-Sturmian words and complexity (English)
0 references
30 June 2005
0 references
Given an infinite sequence, the complexity function \(p(n,w)\) counts the number of different subwords of \(w\) with size \(n\). Since Hedlund and Morse, it is known that when one considers a binary sequence, the sequence is ultimately periodic if and only if \(p(n,w) \leq n\) for a given \(n\). Non-periodic sequences with the lowest complexity satisfy \(p(n,w)=n+1\) for every \(n\); they are called Sturmian sequences. They have zero entropy and correspond to the discrete coding of lines with irrational slope in \({\mathbb R}^2\). In this paper, the authors introduce a new complexity function \(p_{\star}(n,w)\) which counts the number of different subwords of \(w\) that appear infinitely often in \(w\). Then, \(p_{\star}(n,w) \leq p(n,w)\), with equality when \(w\) is a Sturmian sequence for instance. The authors define \({\star}\)-Sturmian sequences to be infinite words \(w\) satisfying \(| | A| _1 - | B| _1| \leq 1\) for any subword \(A\), \(B\) having the same size and appearing infinitely often in \(w\). They prove that this is equivalent with \(p_{\star}(n,w) \leq n+1\) for any \(n\). Moreover, such sequences are either Sturmian or codings of lines with rational slopes. A class of examples with explicit complexity is described. In general, such sequences can have a large complexity (examples are given with \(p(n,w) \geq 2^{n^{1-\varepsilon}}\)) but they always have a zero entropy.
0 references
Sturmian words
0 references
complexity
0 references
approximation of rational lines
0 references
infinite occurrences
0 references