*-Sturmian words and complexity (Q558168): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 4 users not shown) | |||
Property / review text | |||
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. | |||
Property / review text: 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. / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68R15 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05A05 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 37B10 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 2184624 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Sturmian words | |||
Property / zbMATH Keywords: Sturmian words / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
complexity | |||
Property / zbMATH Keywords: complexity / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
approximation of rational lines | |||
Property / zbMATH Keywords: approximation of rational lines / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
infinite occurrences | |||
Property / zbMATH Keywords: infinite occurrences / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2322480417 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Complexity of sequences defined by billiard in the cube / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Représentation géométrique de suites de complexité $2n+1$ / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Complexity of trajectories in rectangular billiards / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Descriptions of the Characteristic Sequence of an Irrational / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Sequences with minimal block growth / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Les transformations de Chacon : combinatoire, structure géométrique, lien avec les systèmes de complexité $2n+1$ / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5752638 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4022829 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Modified complexity and *-Sturmian word / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Sequences with subword complexity \(2n\) / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The continued fraction expansion of α with μ(α) = 3 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 13:13, 10 June 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
0 references