*-Sturmian words and complexity (Q558168): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
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 |
Revision as of 15:14, 1 July 2023
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