×

Operations on Christoffel words. (Opérations sur les mots de Christoffel.) (French) Zbl 1066.11502

The slope \(\rho(f)\) of a finite word on the alphabet \(\{0,1\}\) is defined as the ratio of the number \(f_1\) of 1’s and the number \(f_0\) of 0’s. The definition is naturally extended to the case of infinite words provided the limit of the slopes of finite prefixes exists.
A Lyndon word \(f\in\{0,1\}^*\) is larger than any one of its suffixes (lexicographical order induced by \(0<1\)). The author defines Christoffel words recursively. Let \(f\) and \(g\) be two words; the determinant is \(\det(f,g)=f_0g_1-f_1g_0 (f_0=\text{the number of 0's in} f, \text{etc.})\). 0 and 1 are Christoffel words. If \(f\) and \(g\) are Christoffel words such that \(\det(f,g)=1\), then the concatenated word \(fg\) is a Christoffel word. A Christoffel word is a Lyndon word, but the converse is false.
The object of the article under review is to study the map \(f\mapsto\rho(f)\) which associates the slope \(\rho(f)\) and its continued fraction expansion to the Christoffel word \(f\). The author discusses the operation \(\oplus\) which is defined by \(\rho(f\oplus g)=\rho(f)+\rho(g)\). The operation is made consistent, and given new insight on the rather intricate algorithms which add continued fractions. The author also investigates the product of a continued fraction by an integer.
The article under review, even though fascinating, is somewhat difficult to read since the notations and concept are not always defined: one is often asked to refer to the author’s thesis [”Addition et multiplication par un entier des mots de Christoffel”, Thèse, Limoges, 1995; per bibl.].

MSC:

11B85 Automata sequences
68R15 Combinatorics on words
PDF BibTeX XML Cite
Full Text: DOI Numdam EuDML EMIS

References:

[1] Borel, J.-P., Laubie, F., Construction de mots de Christoffel, C. R. Acad. Sci. Paris313, sér. 1 (1991), 483-485. · Zbl 0742.11013
[2] Borel, J.-P., Laubie, F., Quelques mots sur la droite projective réelle, J. Théor. Nombres Bordeaux5 (1993), 23-51. · Zbl 0839.11008
[3] Brown, T.C., Description of the characteristic sequence of an irrational, Canad. Math. Bull.36 (1993), 15-21. · Zbl 0804.11021
[4] Cohen, H., Multiplication par un entier d’une fraction continue périodique, Acta arith.26 (1974), 129-148. · Zbl 0273.10031
[5] Crisp, D., Moran, W., Pollington, A., Shiue, P., Substitution invariant cutting sequences, J. Théor. Nombres Bordeaux5 (1993), 123-137. · Zbl 0786.11041
[6] Hall, M., On the sum and product of continued fractions, Ann. of Math.48 (1947), 966-993. · Zbl 0030.02201
[7] Hardy, G.H., Wright, E.M., An introduction to the theory of numbers, Clarendon press, Oxford, 4th ed., 1960. · Zbl 0086.25803
[8] Laubie, F., Prolongements homographiques de substitutions de mots de Christoffel, C. R. Acad. Sci. Paris313, sér. 1 (1991), 565-567 · Zbl 0768.11024
[9] Laubie, F., Laurier, E., Calcul de multiples de mots de Christoffel, C. R. Acad. Sci. Paris320, sér. 1 (1995), 765-768. · Zbl 0827.11015
[10] Laurier, É., Addition et multiplication par un entier des mots de Christoffel, Thèse, Limoges, 1995.
[11] Lothaire, M., Combinatorics on Words. Encyclopedia of mathematics and its applications, Cambridge university press, 1983. · Zbl 0874.20040
[12] Lyndon, R.C., Equations in free groups, Trans. Amer. math. soc. (96), 445-457. · Zbl 0108.02301
[13] Mendès France, M., Sur les fractions continues limitées, Acta Arith.23 (1973), 207-215. · Zbl 0228.10007
[14] Raney, G.N., On continued fractions and finite automata, Math. Ann.206 (1973), 265-283. · Zbl 0251.10024
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.