The complexity of generalized Sturmian sequences
This paper (no abstract) begins like this: \bigskip Let \(\{b_i\}_{n=1}^\infty\) be a sequence with finite state and let \[ P_n(\{b_i\}_{n=1}^\infty)= \#\{(b_j,b_{j+1},\cdots,b_{j+n-1}) |j=1,2,\cdots\}. \] We call \(P_n(\{b_i\}_{n=1}^\infty)\) the complexity of \(\{b_i\}_{n=1}^\infty\). \bigskip I wish the author had written instead, that if \(b\) is an infinite sequence of symbols, its complexity \(P_n(b)\) is the number of distinct substrings of length \(n\) it contains. The reader who will survive the cumbersome notation will find the proof of the following interesting result. Let \(x_1,\ldots,x_k\) be real numbers greater than 2, and such that the numbers \[ 1, x_1^{-1}, (x_1x_2)^{-1},\ldots, (x_1\cdots x_k)^{-1} \] are independent over the rationals. Further, let \[ {\mathcal F}(n)=\lfloor x_1\lfloor x_2 \cdots \lfloor x_k n\rfloor \cdots \rfloor \rfloor \] where \(n\) is a positive integer, and \(\lfloor \cdot\rfloor\) is the floor function. Then the complexity of the sequence \({\mathcal F}(n+1)-{\mathcal F}(n)\) is equal to \((n+1)^k\). \bigskip This result could have acquired considerable strength if placed into a broader context, particularly with respect to symbolic dynamics.
- ON INTEGER SEQUENCES GENERATED BY LINEAR MAPS
- Complexity of sequences with values in a finite set: some examples
- Spécialisation de la suite de Sturm
- Minimum complexity of automatic non sturmian sequences
- Complexité de suites engendrées par des récurrences unipotentes
- Return time complexity of Sturmian sequences
- Generalizations of Sturmian sequences associated with \(\boldsymbol{N}\)-continued fraction algorithms
This page was built for publication: The complexity of generalized Sturmian sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1922164)
