×
Mignosi, Filippo; Séébold, Patrice

Sturmian morphisms and Rauzy’s rules. (Morphismes sturmiens et règles de Rauzy.) (French) Zbl 0797.11029

J. Théor. Nombres Bordx. 5, No. 2, 221-233 (1993).
An infinite word \(x\) over a binary alphabet \(A\) is called Sturmian if it has exactly \(n+1\) distinct factors of length \(n\) for every \(n \in \mathbb{N}\). A morphism of the free monoid of all the words over \(A\) is called Sturmian if it preserves Sturmian words over \(A\). The authors, extending an earlier sufficient condition by Márton Kósa [Problems and solutions sections of EATCS Bull. 32, 331-333 (1987)], give a criterion for Sturmian morphisms in terms of three special morphisms introduced by Kósa. The final two sections of the paper are devoted to morphisms, the definition of which is motivated by a construction due to G. Rauzy [Lect. Notes Comput. Sci. 192, 165-171 (1983; Zbl 0613.10044)] and to the proof that infinite words generated by these morphisms are rigid.
Reviewer: Š.Porubský (Bratislava)

Cited in 5 Reviews
Cited in 49 Documents

MSC:

11B85 Automata sequences
20M05 Free semigroups, generators and relations, word problems
68R15 Combinatorics on words

Keywords:

infinite binary word; Sturmian words; Sturmian morphisms

Citations:

Zbl 0613.10044
Cite Review PDF
Full Text: DOI Numdam EuDML

References:

[1] Brown, T.C., A characterization of the quadratic irrationals, Canad. Math. Bull.34 (1991), 36-41. · Zbl 0688.10007
[2] Crisp, D., Moran, W., Pollington, A., Shiue, P., Substitution invariant cutting sequences, Journal de Théorie des Nombres de Bordeaux5 (1993), 123-137. · Zbl 0786.11041
[3] Coven, E., Hedlund, G.A., Sequences with minimal block growth, Math. Systems Theory7 (1973), 138-153. · Zbl 0256.54028
[4] Dulucq, S., Gouyou-Beauchamps, D., Sur les facteurs des suites de Sturm, Theoret. Comput. Sci.71 (1990), 381-400. · Zbl 0694.68048
[5] Fraenkel, A.S., Mushkin, M., Tassa, U., Determination of [nθ] by its sequence of differences, Canad. Math. Bull.21 (1978), 441-446. · Zbl 0401.10018
[6] Hedlund, G.A., Sturmian minimal sets, Amer. J. Math66 (1944), 605-620. · Zbl 0063.01982
[7] Hedlund, G.A., Morse, M., Symbolic dynamics II - Sturmian trajectories, Amer. J. Math.62 (1940), 1-42. · JFM 66.0188.03
[8] Ito, S., Yasutomi, S., On continued fractions, substitutions and characteristic sequences, Japan. J. Math.16 (1990), 287-306. · Zbl 0721.11009
[9] Kósa, M., Problems 149-151, “Problems and Solutions”, EATCS Bulletin32 (1987), 331-333.
[10] Lothaire, M., Combinatorics on words, Addison Wesley, 1982. · Zbl 0514.20045
[11] Mignosi, F., On the number of factors of Sturmian words, Theoret. Comput. Sci.82 (1991), 71-84. · Zbl 0728.68093
[12] Rauzy, G., Mots infinis en arithmétique, in Automata on infinite words, Nivat, Perrin (Eds), , Springer-Verlag192 (1984), 165-171. · Zbl 0613.10044
[13] Séébold, P., Fibonacci morphisms and Sturmian words, Theoret. Comput. Sci.88 (1991), 365-384. · Zbl 0737.68068
[14] Series, C., The geometry of Markoff numbers, Math. Intelligencer7 (1985), 20-29. · Zbl 0566.10024
[15] Stolarsky, K.B., Beatty sequences, continued fractions, and certain shift operators, Canad. Math. Bull.19 (1976), 473-482. · Zbl 0359.10028
[16] Venkov, B.A., Elementary Number Theory, Wolters-Noordhoff, Groningen, 1970. · Zbl 0204.37101
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.