Substitutions par des motifs en dimension 1

Pattern subsitutions in dimension

Institut de mathématiques de Luminy, CNRS UMR 6206 / FRUMAM, case 907, 163 avenue de Luminy, 13288 Marseille Cedex 9, France; pytheas@iml.univ-mrs.fr

Reçu : 20 Janvier 2006
Accepté : 3 Janvier 2007

Résumé

Une substitution est un morphisme de monoïdes libres : chaque lettre a pour image un mot, et l'image d'un mot est la concaténation des images de ses lettres. Cet article introduit une généralisation de la notion de substitution, où l'image d'une lettre n'est plus un mot mais un motif, c'est-à-dire un “mot à trous”, l'image d'un mot étant obtenue en raccordant les motifs correspondant à chacune de ses lettres à l'aide de règles locales. On caractérise complètement les substitutions par des motifs qui sont définies sur toute suite biinfinie, et on explique comment les construire. On montre que toute suite biinfinie qui est point fixe d'une substitution par des motifs est substitutive, c'est-à-dire est l'image, par un morphisme lettre à lettre, d'un point fixe de substitution (au sens usuel).

Abstract

A substitution is a morphism of the free monoid: each letter is mapped to a word, and the image of a word is the concatenation of the images of its letters. This paper introduces a generalization of the notion of substitution, where the image of a letter is not a word but a pattern, i.e., a “word with holes”: the image of a word is obtained by connecting the patterns corresponding to each of the letters by means of local rules. We completely characterize pattern substitutions which are defined on every biinfinite sequence, and we explain how to build them. We show that every biinfinite sequence which is a fixed point of a pattern substitution is substitutive, i.e., it is the image, by a letter to letter morphism, of a fixed point of a substitution (in the usual meaning).