Computation of multiples of Christoffel words. (Calcul de multiples de mots de Christoffel.) (French) Zbl 0827.11015

A Christoffel word \(f\) is a finite or infinite word on the alphabet \(X= \{0, 1\}\) such that for each finite prefix \(f'\) of \(f\) one has \(\rho (f')= \max\{ \rho(u)\); \(u\in X^*\), \(|u|= |f'|\) and \(\rho (u)\leq \rho (f)\}\), where \(\rho (u)= |u|_1/ |u|_0\in \mathbb{Q}^+\cup \{+\infty\}\). If \(f\) is an infinite Christoffel word, the sequence of \(\rho (f')\), \(f'\) a finite prefix of \(f\), converges to a number \(\rho (f)\). For each \(\rho\in \mathbb{R}^+\cup \{+\infty\}\), there is a unique Christoffel word \(f\) with \(\rho (f)= \rho\). The authors give an algorithm which transforms \(f\) into the Christoffel word \(g\) with \(\rho (g)= p\rho (f)\), for \(p\) prime \(\geq 5\), under certain conditions on the partial quotients of the continued fraction representing \(\rho(f)\).


11B85 Automata sequences
68R15 Combinatorics on words
68Q45 Formal languages and automata