×

Sequences generated by infinitely iterated morphisms. (English) Zbl 0583.20047

Define an endomorphism \(\mu\) of the free monoid \(A=\{a,b\}^*\) by \(\mu (a)=ab\), \(\mu (b)=ba\). This morphism defines iteratively an infinite word, \(\mu^ w(a)\), which is called the Morse sequence. It is shown that up to permuting the letters a and b the Morse sequence is the only infinite sequence having no overlapping factors which can be generated by an endomorphism of \(A\).
Reviewer: T.J.Harju

MSC:

20M05 Free semigroups, generators and relations, word problems
68Q42 Grammars and rewriting systems
68Q45 Formal languages and automata
20M35 Semigroups in automata theory, linguistics, etc.
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Arson, S., Démonstration de l’existence de suites asymétriques infinies, Mat. sb., 44, 769-777, (1937) · Zbl 0018.11503
[2] Berstel, J., Sur LES mots sans carré définis par un morphisme, (), 16-25 · Zbl 0425.20046
[3] Berstel, J., Mots sans carré et morphismes itérés, Discrete math., 29, 235-244, (1980) · Zbl 0444.20050
[4] Berstel, J., Mots de Fibonacci, LITP - Séminaire d’informatique théorique, 57-78, (1980)
[5] Crochemore, M., An optimal algorithm for computing repetitions of a word, Inform. process. lett., 12, 244-250, (1981) · Zbl 0467.68075
[6] Dekking, F.M., On repetitions of blocks in binary sequences, J. combin. theory (A), 20, 292-299, (1976) · Zbl 0325.05010
[7] Fife, E.D., Binary sequences which contain no bbb, Trans. amer. math. soc., 261, 1, 115-136, (1980) · Zbl 0464.05018
[8] Gottschalk, W.; Hedlund, G., A characterisation of the Morse minimal set, (), 70-74 · Zbl 0134.42203
[9] Harju, T., Morphisms that avoid overlapping, (1983), University of Turku
[10] Karhumäki, J., On cubic-free ω-words generated by binary morphisms, Discrete applied math., 5, 279-297, (1983) · Zbl 0505.03022
[11] de Luca, A., A combinatorial property of Fibonacci words, Inform. process. lett., 12, 4, 193-195, (1981) · Zbl 0468.20049
[12] Morse, M.; Hedlund, G., Unending chess, symbolic dynamics and a problem in semi-group, Duke math. J., 11, 1-7, (1944) · Zbl 0063.04115
[13] Pansiot, J.J., The Morse sequence and iterated morphisms, Inform. process. lett., 12, 68-70, (1981) · Zbl 0464.68075
[14] Pansiot, J.J., Mots infinis de Fibonacci et morphismes itérés, RAIRO informatique théorique, 17, 131-135, (1983) · Zbl 0521.20042
[15] Thue, A., Über unendliche zeichenreihen, N. vid. selsk. skr. I. math. nat. kl., christ., 7, 1-22, (1906) · JFM 39.0283.01
[16] Thue, A., Über die gegenseitige lage gleicher teile gewisser zeichenreihen, Vidensk. I. math. nat. kl., 1, 1-67, (1912) · JFM 44.0462.01
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.