×

On the conjugation of standard morphisms. (English) Zbl 0981.68104

Summary: Let \(A=a,b\) be an alphabet. An infinite word on \(A\) is Sturmian if it contains exactly \(n+1\) distinct factors of length \(n\) for every integer \(n\). A morphism \(f\) on \(A\) is Sturmian if \(f(X)\) is Sturmian whenever \(X\) is. A morphism on \(A\) is standard if it is an element of the monoid generated by the two elementary morphisms, \(E\) which exchanges \(a\) and \(b\), and \(\varphi\) the Fibonacci morphism defined by \(\varphi(a)=ab\) and \(\varphi(b)=a\). The set of standard morphisms is a proper subset of the set of Sturmian morphisms. In the present paper, we give a characterization of Sturmian morphisms as conjugates of standard ones. We establish that Sturmian words generated by standard morphisms are characteristic words and then we prove that a morphism \(f\) generates an infinite word having the same set of factors as a characteristic word generated by a primitive standard morphism \(g\) if and only if \(f\) is a conjugate of a power of \(g\).

MSC:

68Q45 Formal languages and automata
11B85 Automata sequences
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Allouche, J.-P., Sur la complexité des suites infinies, Bull. belg. math. soc., 1, 133-143, (1994) · Zbl 0803.68094
[2] Allouche, J.-P.; France, M.Mendès, Quasicrystal Ising chain and automata theory, J. stat. phys., 42, 809-821, (1986) · Zbl 0641.10043
[3] Bernoulli, J., Sur une nouvelle espèce de calcul, Recueil pour LES astronomes, vol. 1, 255-284, (1772), Berlin
[4] Berstel, J., Mots de Fibonacci, (), 57-78, Année
[5] Berstel, J., Recent results on Sturmian words, () · Zbl 1007.68141
[6] Berstel, J.; Séébold, P., A characterization of Sturmian morphisms, (), 281-290 · Zbl 0925.11026
[7] Berstel, J.; Séébold, P., Morphismes de Sturm, Bull. belg. math. soc., 1, 175-189, (1994) · Zbl 0803.68095
[8] Berstel, J.; Séébold, P., A remark on morphic Sturmian words, Informatique théorique et applications, 28, 255-263, (1994) · Zbl 0883.68104
[9] Bombieri, E.; Taylor, J.E., Which distributions of matter diffract?, (), 19-28, Colloque C3 · Zbl 0693.52002
[10] Borel, J.-P.; Laubie, F., Construction de mots de Christoffel, C. R. acad. sci. Paris, 313, 483-485, (1991) · Zbl 0742.11013
[11] Borel, J.-P.; Laubie, F., Quelques mots sur la droite protective réelle, J. théorie des nombres de Bordeaux, 5, 23-51, (1993) · Zbl 0839.11008
[12] Bresenham, J.E., Algorithm for computer control of a digital plotter, IBM systems J., 4, 25-30, (1965)
[13] Brown, T.C., A characterization of the quadratic irrationals, Can. math. bull., 34, 36-41, (1991) · Zbl 0688.10007
[14] Brown, T.C., Descriptions of the characteristic sequence of an irrational, Can. math. bull., 36, 15-21, (1993) · Zbl 0804.11021
[15] Coven, E.; Hedlund, G., Sequences with minimal block growth, Math. systems theory, 7, 138-153, (1973) · Zbl 0256.54028
[16] Crisp, D.; Moran, W.; Pollington, A.; Shiue, P., Substitution invariant cutting sequences, J. théorie des nombres de Bordeaux, 5, 123-138, (1993) · Zbl 0786.11041
[17] de Luca, A.; Mignosi, F., Some combinatorial properties of Sturmian words, Theoret. comput. sci., 136, 361-385, (1994) · Zbl 0874.68245
[18] Droubay, X., Palindromes in the Fibonacci word, Inform. process. lett., 55, 217-221, (1995) · Zbl 1004.68537
[19] Dulucq, S.; Gouyou-Beauchamps, D., Sur LES facteurs des suites de Sturm, Theoret. comput. sci., 71, 381-400, (1990) · Zbl 0694.68048
[20] Harju, T.; Linna, M., The equations h(w) = wn in binary alphabets, Theoret. comput. sci., 33, 327-329, (1984) · Zbl 0548.20044
[21] Hedlund, G.A., Sturmian minimal sets, Amer. J. math., 66, 605-620, (1944) · Zbl 0063.01982
[22] Hedlund, G.A.; Morse, M., Symbolic dynamics II — Sturmian trajectories, Amer. J. math., 62, 1-42, (1940) · JFM 66.0188.03
[23] Ito, S.; Yasutomi, S., On continued fractions, substitutions and characteristic sequences, Japan. J. math., 16, 287-306, (1990) · Zbl 0721.11009
[24] Laubie, F.; Laurier, É., Calcul de multiples de mots de Christoffel, C. R. acad. sci. Paris, 320, 765-768, (1995) · Zbl 0827.11015
[25] Lothaire, M., Combinatorics on words, () · Zbl 1001.68093
[26] Lunnon, W.F.; Pleasants, P.A.B., Characterization of two-distance sequences, J. Australian math. soc., 53, 198-218, (1992) · Zbl 0759.11005
[27] Markoff, A.A., Sur une question de Jean Bernoulli, Math. ann., 19, 27-36, (1882) · JFM 13.0313.01
[28] Mignosi, F., Infinite words with linear subwords complexity, Theoret. comput. sci., 65, 221-242, (1989) · Zbl 0682.68083
[29] Mignosi, F., On the number of factors of Sturmian words, Theoret. comput. sci., 82, 71-84, (1991) · Zbl 0728.68093
[30] Mignosi, F.; Séébold, P., Morphismes sturmiens et règles de Rauzy, J. théorie des nombres de Bordeaux, 5, 221-233, (1993) · Zbl 0797.11029
[31] Queffélec, M., Substitution dynamical systems — spectral analysis, () · Zbl 0642.28013
[32] Rauzy, G., Mots infinis en arithmétique, (), 165-171 · Zbl 0613.10044
[33] Séébold, P., An effective solution to the D0L-periodicity problem in the binary case, EATCS bull., 36, 137-151, (1988) · Zbl 0678.68072
[34] Séébold, P., Fibonacci morphisms and Sturmian words, Theoret. comput. sci., 88, 365-384, (1991) · Zbl 0737.68068
[35] Series, C., The geometry of markoff numbers, Math. intelligencer, 7, 20-29, (1985) · Zbl 0566.10024
[36] Stolarsky, K.B., Beatty sequences, continued fractions, and certain shift operators, Can. math. bull., 19, 473-482, (1976) · Zbl 0359.10028
[37] Venkov, B.A., Elementary number theory, (1970), Wolters-Noordhoff Groningen · Zbl 0204.37101
[38] Wen, Z.-X.; Wen, Z.-Y., Local isomorphisms of invertible substitutions, C. R. acad. sci. Paris, 318, 299-304, (1994) · Zbl 0812.11018
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.