Toeplitz Words, Generalized Periodicity and Periodically Iterated Morphisms

J. Cassaigne, J. Karhumäki

IBP-Litp 1995/36: Rapport de Recherche Litp / Litp research reports
16 pages - Juillet/July 1995 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Toeplitz Words, Generalized Periodicity and Periodically Iterated Morphisms

Résumé : Nous étudions certains mots infinis, dits mots de Toeplitz, qui peuvent être considérés comme une généralisation des mots périodiques. Nous calculons leur complexité factorielle, et nous montrons qu'il est toujours possible de les engendrer par l'itération périodique d'un nombre fini de morphismes. De plus, nous donnons une classification des mots de Toeplitz qui intervient dans la manière dont ils peuvent être engendrés par morphismes itérés.

Abstract : We consider so-called Toeplitz words which can be viewed as generalizations of one-way infinite periodic words. We compute their subword complexity, and show that they can always be generated by iterating periodically a finite number of morphisms. Moreover, we define a structural classification of Toeplitz words which is reflected in the way how they can be generated by iterated morphisms.

Publications internes Litp 1995 / Litp research reports 1995