zbMATH — the first resource for mathematics

Sturm sequences: Rauzy graphs and forcing. (Russian) Zbl 1236.11028
Let \(\alpha\) be an irrational number, \(0<\alpha<1\), and let \(R_{\alpha}\) be the shift mapping \(R_{\alpha}: [0,1)\to[0,1)\), \( x\mapsto x+\alpha\bmod1\). For a given \(x\in[0,1)\) define an infinite sequence \(u=(u_n)_{n=1}^{\infty}\) of zeros and ones (a Sturm sequence, or Sturmian word) in the following way: \(u_n=0\) if \(R_{\alpha}^n(x)<1-\alpha\), and \(u_n=1\) otherwise. It is known that a Sturmian word has exactly \(n+1\) factors of length \(n\). A Rauzy graph \(G_n\) is an oriented graph whose \(n+1\) vertices correspond to the \(n\)-factors of a Sturmian word, and whose \(n+2\) arcs are defined as follows: there is an arc from \(v\) to \(v'\) if \(v'\) can be obtained from \(v\) by cutting one bit on the left and adding one bit on the right. The paper establishes a complete classification of Rauzy graphs. The forcing of the \(n\)-factor \(v\) of a Sturmian word is the number of bits which follow \(v\) and which are uniquely determined by \(v\). The values of a maximal forcing and of an average one, as functions of \(n\), are expressed in terms of denominators of the continued fraction expression of \(\alpha\).

11B85 Automata sequences
37B10 Symbolic dynamics
05A05 Permutations, words, matrices
11A55 Continued fractions
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68R10 Graph theory (including graph drawing) in computer science
68R15 Combinatorics on words