On the triplex substitution – combinatorial properties - 21/08/08

Doi : 10.1016/j.crma.2008.06.013

Bo Tan ^a , Zhi-Xiong Wen ^a , Yiping Zhang ^b
^a Department of Mathematics, Huazhong University of Science and Technology, Wuhan 430074, PR China
^b Department of Mathematics, Wuhan University, Wuhan 430072, PR China

Bienvenue sur EM-consulte, la référence des professionnels de santé.
L’accès au texte intégral de cet article nécessite un abonnement.

pages	6
Iconographies	0
Vidéos	0
Autres	0

Abstract

If a substitution τ over a three-letter alphabet has a positively linear complexity, that is, ( ) with , there are only 4 possibilities: , , 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 , , . 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).

Le texte complet de cet article est disponible en PDF.

Résumé

Si une substitution τ sur un alphabet de trois lettres a une complexité positivement linéaire, cʼest-à-dire ( ) où , alors il nʼy a que quatre possibilités : , , 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 , , . 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).