Fibonacci morphisms and Sturmian words. (English) Zbl 0737.68068

The paper solves four problems on binary morphisms proposed by M. Kósa [Bull. EATCS 32, 331-333 (1987)].
Reviewer: T.J.Harju (Turku)


68R15 Combinatorics on words
20M05 Free semigroups, generators and relations, word problems
68Q45 Formal languages and automata
Full Text: DOI


[1] Berstel, J., Mots de Fibonacci, L.I.T.P. Seminaire d’Informatique Théorique, 57-78 (1981)
[2] Berstel, J., Traces de droites, fractions continues et morphismes itérés, Rapport L.I.T.P. 87-61 (1987)
[3] Bombieri, E.; Taylor, J. E., Which distributions of matter diffract? An initial investigation, J. Physique, 47, 19-28 (1986) · Zbl 0693.52002
[4] Christol, G.; Kamae, T.; Mendès-France, M.; Rauzy, G., Suites algébriques, automates et substitutions, Bull. Soc. Math. France, 108, 401-419 (1980) · Zbl 0472.10035
[5] Dekking, F. M., Regularity and irregularity of sequences generated by automata, Bordeaux, année 1979-1980. Bordeaux, année 1979-1980, Séminaire de Théorie des Nombres (1979), exposé no 9 · Zbl 0438.10040
[6] Karhumäki, J., On the equivalence problem for binary morphisms, Inform. and Control, 50, 276-284 (1981) · Zbl 0497.68048
[7] Kósa, M., Problems and Solutions, EATCS Bulletin, 32, 331-333 (1987)
[8] Lothaire, M., Combinatorics on words (1983), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0514.20045
[9] Rauzy, G., Mots infinis en arithmétique, (Nivat, M.; Perrin, D., Automata on infinite words. Automata on infinite words, Lecture Notes in Computer Science, Vol. 192 (1985), Springer: Springer Berlin), 165-171, 12 ième école de printemps d’Informatique Théorique — Le Mont Dore (1984)- in: · Zbl 0553.10041
[10] Salomaa, A., Jewels of Formal Language Theory (1981), Pitman: Pitman London · Zbl 0487.68063
[11] Séébold, P., Sequences generated by infinitely iterated morphisms, Discrete Appl. Math., 11, 255-264 (1985) · Zbl 0583.20047
[12] Séébold, P., Propriétés combinatoires des mots infinis engendrés par certains morphismes, Thèse de Doctorat. Thèse de Doctorat, Rapport L.I.T.P. 85-16 (1985)
[13] Séébold, P., An effective solution to the DOL periodicity problem in the binary case, EATCS Bulletin, 36, 137-151 (1988) · Zbl 0678.68072
[14] Shallit, J., A generalization of automatic sequences, Theoret. Comput. Sci., 61, 1-16 (1988) · Zbl 0662.68052
[15] de Luca, A.; Varricchio, S., Some combinatorial properties of the Thue—Morse sequence and a problem in semigroups, Theoret. Comput. Sci., 63, 333-348 (1989) · Zbl 0671.10050
[16] Dulucq, S.; Gouyou-Beauchamps, D., Sur les facteurs des suites de Sturm, Theoret. Comput. Sci., 71, 381-400 (1990) · Zbl 0694.68048
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.