Access to the full text of this article requires a subscription.
  • If you are a subscriber, please sign in 'My Account' at the top right of the screen.

  • If you want to subscribe to this journal, see our rates

  • You can purchase this item in Pay Per ViewPay per View - FAQ : 30,00 € Taxes included to order
    Pages Iconography Videos Other
    6 0 0 0


Comptes Rendus Mathématique
Volume 346, n° 15-16
pages 813-818 (août 2008)
Doi : 10.1016/j.crma.2008.06.013
Received : 18 February 2008 ;  accepted : 18 June 2008
On the triplex substitution – combinatorial properties
Sur la substitution triplexe – propriétés combinatoires
 

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 

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).

The full text of this article is available in PDF format.
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).

The full text of this article is available in PDF format.

 Research supported by NSFC No. 10501035, 10631040, 10571140 and 10671150.



© 2008  Académie des sciences@@#104156@@