On the triplex substitution – combinatorial properties ⁎

If a substitution τ over a three-letter alphabet has a positively linear complexity, that is, Pτ(n)=C1n+C2 (n⩾1) with C1,C2⩾0, there are only 4 possibilities: Pτ(n)=3, n+2, 2n+1 or 3n. The first three cases have been studied by many authors, but the case 3n remained unclear. This leads us to consider the triplex substitution , b↦acb, c↦acc. Studying the factor structure of its fixed point, which is quite different from the other cases, we show that it is of complexity 3n. We remark that the triplex substitution is also a typical example of invertible substitution over a three-letter alphabet. To cite this article: B. Tan et al., C. R. Acad. Sci. Paris, Ser. I 346 (2008).

RésuméSi une substitution τ sur un alphabet de trois lettres a une complexité positivement linéaire, c'est-à-dire Pτ(n)=C1n+C2 (n⩾1) où C1,C2⩾0, alors il n'y a que quatre possibilités : Pτ(n)=3, n+2, 2n+1 ou 3n. Les trois premiers cas ont été étudiés par différents auteurs, mais le cas 3n reste non entièrement élucidé. Nous considérons donc la substitution triplexe , b↦acb, c↦acc. Analysant la structure des facteurs de son point fixe nous montrons que sa complexité est 3n. La substitution triplexe est un exemple typique de substitution inversible sur un alphabet de trois lettres. Pour citer cet article : B. Tan et al., C. R. Acad. Sci. Paris, Ser. I 346 (2008).