The complexity of generalized Sturmian sequences
type: Item
instance of: scholarly article
title: The complexity of generalized Sturmian sequences
zbMATH Open document ID: 0869.11018
author: Shin-ichi Yasutomi
published in: Tokyo Journal of Mathematics
publication date: 1996-12-12T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 11B83
Mathematics Subject Classification ID: 37E99
Mathematics Subject Classification ID: 28D99
zbMATH DE Number: 927040
zbMATH Keywords: algebraic dynamics
zbMATH Keywords: infinite sequence of symbols
zbMATH Keywords: complexity
zbMATH Keywords: substrings
zbMATH Keywords: symbolic dynamics
zbMATH Keywords: generalized Sturmian sequences
reviewed by: Franco Vivaldi
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3836/tjm/1270043226
OpenAlex ID: W2042688329
DOI: 10.3836/TJM/1270043226
description: scientific article; zbMATH DE number 927040