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

Laubie, François; Laurier, Éric

C. R. Acad. Sci., Paris, Sér. I 320, No. 7, 765-768 (1995).

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

Reviewer: C.Reutenauer (Montreal)

MSC:

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

Keywords:

multiple; Christoffel word; infinite Christoffel word; algorithm; continued fraction

Citations:

Zbl 0768.11024; Zbl 0742.11013