×

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)\).

MSC:

11B85 Automata sequences
68R15 Combinatorics on words
68Q45 Formal languages and automata
PDF BibTeX XML Cite