Présenté à la conférence WORDS'2001, Palermo, Italy ( slides of the talk ).
Accepté dans Theoretical Computer Science.
Abstract.
Episturmian morphisms generalize Sturmian morphisms. Here, we study
some intrinsic properties of these morphisms: invertibility, presentation,
cancellativity, unitarity, characterization by conjugacy. Most of them
are generalizations of known properties of Sturmian morphisms. But we present
also some results on episturmian morphisms that have not already been stated
in the particular case of Sturmian morphisms: characterization of the episturmian
morphisms that preserve palindromes, new algorithms to compute conjugates.We
also study the conjugation of morphisms in the general case and show that
the monoid of invertible morphisms on an alphabet containing at least three
letters is not finitely generated.
Résumé.
Les morphismes épisturmiens généralisent les morphismes
sturmiens. Ici, nous étudions des propriétés intrinsèques
de ces morphismes : inversibilité, unitarité, régularité,
caractérisation par conjugaison. La plupart de ces résultats
sont des généralisations de résultats connus sur les
morphismes sturmiens. Mais nous présentons aussi des résultats
non encore établis pour les morphismes sturmiens : caractérisations
des morphismes épisturmiens qui préservent les palindromes,
nouveaux algorithmes pour calculer des conjugués.Nous donnons également
des résultats généraux sur la conjugaison et montrons
que le monoïde des morphismes inversibles sur un alphabet d'au moins
trois lettres n'est pas finiment engendré.
Version postscript compressé de ce rapport
Note. While proceeding with publication in TCS of this article, the author was informed that Theorem 10.4 was already published by Zhi-Xiong Wen and Yiping Zhang (Some remarks on invertible substitutions on three letter alphabet, Chin. Sci. Bulletin, 44(19):1755-1760, 1999).
@techreport{Ric2001,
author = {Richomme, G.},
title = {Conjugacy and episturmian morphisms},
institution = {LaRIA},
year = {2001},
number = {2001-03},
note = {Accepted by Theoretical Computer Science, presented
at WORDS'2001, Palermo, Italy},
}