Séparateurs dans les mots infinis engendrés par morphismes

E. Garel

IBP-Litp 1995/27: Rapport de Recherche Litp / Litp research reports
35 pages - Juin/June 1995 - French document.

PostScript : Ko /Kb

Titre / Title: Séparateurs dans les mots infinis engendrés par morphismes

Résumé : Soit x un mot infini sur un alphabet fini A. Pour tout indice n OE N, nous définissons le séparateur de x en n comme étant le plus petit facteur de x dont l'indice de la première occurrence est n et nous notons S(n) la longueur de ce séparateur. Dans cet article nous montrons que dans le cas où x est engendré par un morphisme q-uniforme pour lequel il est circulaire (au sens donné par F. Mignosi et P. Séébold), alors la suite (S(n) ) est q-régulière (au sens donné par J-P. Allouche et J. Shallit). De manière équivalente, cela revient à dire que la série formelle dont les coefficients sont les valeurs S(n) en base q est rationnelle (voir A. Salomaa et M. Soittola).

Abstract : Let x be an infinite word on a finite alphabet A.For each position n the separator of x at n, is the smallest factor of x that starts at n and that does not appear before in x. Denote by S(n) the length of the separator of x at n. We consider the problem of computing the sequence (S(n)) in the case where x is generated by iterating some morphism. We prove that, if the morphism is q-uniform and if x is circular then (S(n)) is q-regular (in the sense of Allouche and Shallit), or, in other words that the corresponding formal power series that associates S(n) to the q-ary expression of n is rational (Salomaa, Soittola).

Publications internes Litp 1995 / Litp research reports 1995